Strategy optimization for deductive games |
| |
| Authors: | Shan-Tai Chen Shun-Shii Lin Li-Te Huang Sheng-Hsuan Hsu |
| |
| Affiliation: | 1. Department of Computer Science, Chung Cheng Institute of Technology, National Defense University, Tao-Yuan, Taiwan, ROC;2. Department of Computer Science and Information Engineering, National Taiwan Normal University, No. 88, Sec. 4, Ting-Chow Road, Taipei 117, Taiwan, ROC;3. Department of Computer Science, Chinese Culture University, Taipei, Taiwan, ROC |
| |
| Abstract: | This paper presents novel algorithms for strategy optimization for deductive games. First, a k-way-branching (KWB) algorithm, taking advantage of a clustering technique, can obtain approximate results effectively. Second, a computer-aided verification algorithm, called the Pigeonhole-principle-based backtracking (PPBB) algorithm, is developed to discover the lower bound of the number of guesses required for the games. These algorithms have been successfully applied to deductive games, Mastermind and “Bulls and Cows.” Experimental results show that KWB outperforms previously published approximate strategies. Furthermore, by applying the algorithms, we derive the theorem: 7 guesses are necessary and sufficient for the “Bulls and Cows” in the worst case. These results suggest strategies for other search problems. |
| |
| Keywords: | Algorithm Bulls and cows Mastermind Pigeonhole principle Search strategies |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
