Pheromone-Based Pre-processing to Improve Move Generation in Board Games

We propose a method to improve generating moves in board games. The basic idea comes from swarm intelligence. The board game program runs Pheromone-based Pre-processing algorithm (PP) to construct two heuristic game trees apart from the game search tree, and learns from winners’ moves by laying pheromone trails on heuristic game trees before game starts. Then the program picks moves on the basis of their pheromone quantity to start game tree search when playing games. The results of our experiments show that the method is efficient and promising.

Authors and Affiliations

1. College of Computer Science, Zhejiang University, Hangzhou, 310027, P.R. China

   Shenyi Chen, Hui Qian & Miaoliang Zhu

Editors and Affiliations

1. State Key Lab of CAD&CG, Zhejiang University, 310027, Hangzhou, China

   Zhigeng Pan

2. School of Mathematical and Computer Sciences, Heriot Watt University, EH14 4AS, Edinburgh, Scotland

   Ruth Aylett

3. Fraunhofer IGD, Joachim-Jungius-Strasse 11, 18059, Rostock, Germany

   Holger Diener

4. State Key Lab of CAD&CG, Zhejiang University, 310027, Hangzhou, P.R. China

   Xiaogang Jin

5. Digital Storytelling Dept, ZGDV e.V., Rundeturmstr. 10, P.O. Box, 64283, Darmstadt, Germany

   Stefan Göbel

6. School of Management, Shenzhen University, 518060, Shenzhen, P.R. China

   Li Li

Reprints and permissions

© 2006 Springer-Verlag Berlin Heidelberg

Policies and ethics