Strategy optimization for deductive games

Shan Tai Chen, Shun-Shii Lin, Li Te Huang, Sheng Hsuan Hsu

Research output: Contribution to journalArticle

7 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)757-766
Number of pages10
JournalEuropean Journal of Operational Research
Volume183
Issue number2
DOIs
Publication statusPublished - 2007 Dec 1

Fingerprint

Game
Optimization
Guess
Branching
Backtracking
Search Problems
Strategy
Clustering
Sufficient
Lower bound
Necessary
Experimental Results
Theorem

Keywords

  • Algorithm
  • Bulls and cows
  • Mastermind
  • Pigeonhole principle
  • Search strategies

ASJC Scopus subject areas

  • Information Systems and Management
  • Management Science and Operations Research
  • Statistics, Probability and Uncertainty
  • Applied Mathematics
  • Modelling and Simulation
  • Transportation

Cite this

Strategy optimization for deductive games. / Chen, Shan Tai; Lin, Shun-Shii; Huang, Li Te; Hsu, Sheng Hsuan.

In: European Journal of Operational Research, Vol. 183, No. 2, 01.12.2007, p. 757-766.

Research output: Contribution to journalArticle

Chen, Shan Tai ; Lin, Shun-Shii ; Huang, Li Te ; Hsu, Sheng Hsuan. / Strategy optimization for deductive games. In: European Journal of Operational Research. 2007 ; Vol. 183, No. 2. pp. 757-766.
@article{6d300cfb21404b0c98e3d3267163379b,
title = "Strategy optimization for deductive games",
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",
author = "Chen, {Shan Tai} and Shun-Shii Lin and Huang, {Li Te} and Hsu, {Sheng Hsuan}",
year = "2007",
month = "12",
day = "1",
doi = "10.1016/j.ejor.2006.08.058",
language = "English",
volume = "183",
pages = "757--766",
journal = "European Journal of Operational Research",
issn = "0377-2217",
publisher = "Elsevier",
number = "2",

}

TY - JOUR

T1 - Strategy optimization for deductive games

AU - Chen, Shan Tai

AU - Lin, Shun-Shii

AU - Huang, Li Te

AU - Hsu, Sheng Hsuan

PY - 2007/12/1

Y1 - 2007/12/1

N2 - 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.

AB - 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.

KW - Algorithm

KW - Bulls and cows

KW - Mastermind

KW - Pigeonhole principle

KW - Search strategies

UR - http://www.scopus.com/inward/record.url?scp=34250026665&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34250026665&partnerID=8YFLogxK

U2 - 10.1016/j.ejor.2006.08.058

DO - 10.1016/j.ejor.2006.08.058

M3 - Article

VL - 183

SP - 757

EP - 766

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 2

ER -