標題: XT Domineering: A new combinatorial game
作者: Kao, Kuo-Yuan
Wu, I-Chen
Shan, Yi-Chang
資訊工程學系
Department of Computer Science
關鍵字: Domineering;Combinatorial theory;Combinatorial games;Infinitesimals;Nim
公開日期: 1-十月-2012
摘要: This paper introduces a new combinatorial game, named XT Domineering, together with its mathematical analysis. XT Domineering is modified from the Domineering game in which 1 x 2 or 2 x 1 dominos are allowed to be placed on empty squares in an m x n board. This new game allows a player to place a 1 x 1 domino on an empty square s while unable to place a 1 x 2 or 2 x 1 domino in the connected group of empty squares that includes s. After modifying the rule, each position in the game becomes an infinitesimal. This paper calculates the game values of all sub-graphs of 3 x 3 squares and shows that each sub-graph of 3 x 3 squares is a linear combination of 8 elementary infinitesimals. These pre-stored game values can be viewed as a knowledge base for playing XT Domineering. Instead of searching the whole game trees, a simple rule for determining the optimal outcome of any sum of these positions is presented. (C) 2011 Elsevier B.V. All rights reserved.
URI: http://dx.doi.org/10.1016/j.knosys.2011.11.008
http://hdl.handle.net/11536/16819
ISSN: 0950-7051
DOI: 10.1016/j.knosys.2011.11.008
期刊: KNOWLEDGE-BASED SYSTEMS
Volume: 34
Issue: 
起始頁: 55
結束頁: 63
顯示於類別:期刊論文


文件中的檔案:

  1. 000309093000008.pdf