Selection Search for Mean and Temperature of Multi-Branch Combinatorial Games

Article type: Research Article

Authors: Kao, Kuo-Yuan^{a; 1} | Wu, I-Chen^{b; 2} | Shan, Yi-Chang^{b; 2} | Yen, Shi-Jim^{c; 3}

Affiliations: [a] Penghu, Taiwan | [b] Hsinchu, Taiwan | [c] Hualien, Taiwan

Note: [1] Department of Information Management National Penghu University, Penghu, Taiwan. Email: stone@npu.edu.tw

Note: [2] Department of Computer Science and Information Engineering, National Chiao Tung University, Hsinchu, Taiwan. Email: icwu@csie.nctu.edu.tw, ycshan@java.csie.nctu.edu.tw.

Note: [3] Department of Computer Science & Information Engineering, National Dong Hwa University, Hualien, Taiwan. Email: sjyen@mail.ndhu.edu.tw

Abstract: This paper shows a new algorithm to calculate the mean and temperature of multi-branch combinatorial games. The algorithm expands gradually, one node at a time, the offspring of a game. After each step of expansion, the lower and upper bounds of the mean and temperature of the game are re-calculated. As the expanding process continues, the range between the lower and upper bounds is little by little narrowed. The key feature of the algorithm is its ability to generate a path of which the outcome is most likely to reduce the distance between the lower and upper bounds.

DOI: 10.3233/ICG-2012-35303

Journal: ICGA Journal, vol. 35, no. 3, pp. 157-176, 2012