Computing, artificial intelligence and information management - Strategy optimization for deductive games

CCUR > College of Natural Science and Engineering > College of Engineering > Department of Computer Science and Information Engineering > journal articles > Item 987654321/2666

Please use this identifier to cite or link to this item: https://irlib.pccu.edu.tw/handle/987654321/2666

Title:	Computing, artificial intelligence and information management - Strategy optimization for deductive games
Authors:	Chen, Shan-Tai Lin, Shun-Shii Huang, Li-Te Hsu, Sheng-Hsuan
Contributors:	資科系
Keywords:	algorithm bulls and cows mastermind pigeonhole principle search strategies
Date:	2007
Issue Date:	2009-11-13 11:44:02 (UTC+8)
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. (c) 2006 Elsevier B.V. All rights reserved.
Relation:	EUROPEAN JOURNAL OF OPERATIONAL RESEARCH Volume: 183 Issue: 2 Pages: 757-766
Appears in Collections:	[Department of Computer Science and Information Engineering] journal articles

Files in This Item:

File	Description	Size	Format
index.html		0Kb	Text	936	View/Open