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

文化大學機構典藏 CCUR > 理工學院 > 工學院 > 資訊工程學系 > 期刊論文 > Item 987654321/2666

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: https://irlib.pccu.edu.tw/handle/987654321/2666

题名:	Computing, artificial intelligence and information management - Strategy optimization for deductive games
作者:	Chen, Shan-Tai Lin, Shun-Shii Huang, Li-Te Hsu, Sheng-Hsuan
贡献者:	資科系
关键词:	algorithm bulls and cows mastermind pigeonhole principle search strategies
日期:	2007
上传时间:	2009-11-13 11:44:02 (UTC+8)
摘要:	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.
關聯:	EUROPEAN JOURNAL OF OPERATIONAL RESEARCH Volume: 183 Issue: 2 Pages: 757-766
显示于类别:	[資訊工程學系] 期刊論文

文件中的档案:

档案	描述	大小	格式	浏览次数
index.html		0Kb	Text	979	检视/开启

在CCUR中所有的数据项都受到原著作权保护.