Note: [1] This article is a revised version of a contribution with the same title to the Computer Games Workshop 2007 held in Amsterdam, The Netherlands, June 15-17, 2007. The revised version has been subjected to the Journal’s normal refereeing procedure.
Note: [2] Graduate Institute of Information and Computer Education, National Taiwan Normal University, No. 88, Sec. 4, Ting-Chow Rd., Taipei, Taiwan, R.O.C.
Note: [3] Department of Computer Science, Chung Cheng Institute of Technology, National Defense University, Taoyuan, Taiwan, R.O.C.
Note: [4] Department of Computer Science and Information Engineering, National Taiwan Normal University, No. 88, Sec. 4, Ting-Chow Rd., Taipei, Taiwan, R.O.C. Email: linss@csie.ntnu.edu.tw
Abstract: The Mastermind game is well-known around the world. In recent decades, several approaches have been adopted for solving Mastermind in the worst case. An optimal strategy has finally been proposed by Koyoma and Lai in 1993 by using an exhaustive search for finding the optimal strategy in the expected case. In this paper, a more efficient backtracking algorithm with branch-and-bound pruning (BABBP) for Mastermind in the expected case is introduced, and an alternative optimal strategy is obtained eventually. Furthermore, the novel approach may be presumably applied to other games with some modifications in order to speed up the search.
DOI: 10.3233/ICG-2007-30303
Journal: ICGA Journal, vol. 30, no. 3, pp. 143-149, 2007
