標題: Material Symmetry to Partition Endgame Tables
作者: Saffidine, Abdallah
Jouandeau, Nicolas
Buron, Cedric
Cazenave, Tristan
交大名義發表
National Chiao Tung University
公開日期: 2014
摘要: Many games display some kind of material symmetry. That is, some sets of game elements can be exchanged for another set of game elements, so that the resulting position will be equivalent to the original one, no matter how the elements were arranged on the board. Material symmetry is routinely used in card game engines when they normalize their internal representation of the cards. Other games such as CHINESE DARK CHESS also feature some form of material symmetry, but it is much less clear what the normal form of a position should be. We propose a principled approach to detect material symmetry. Our approach is generic and is based on solving multiple relatively small sub-graph isomorphism problems. We show how it can be applied to CHINESE DARK CHESS, DOMINOES, and SKAT. In the latter case, the mappings we obtain are equivalent to the ones resulting from the standard normalization process. In the two former cases, we show that the material symmetry allows for impressive savings in memory requirements when building endgame tables. We also show that those savings are relatively independent of the representation of the tables.
URI: http://dx.doi.org/10.1007/978-3-319-09165-5_16
http://hdl.handle.net/11536/134705
ISBN: 978-3-319-09165-5
978-3-319-09164-8
ISSN: 0302-9743
DOI: 10.1007/978-3-319-09165-5_16
期刊: COMPUTERS AND GAMES, CG 2013
Volume: 8427
起始頁: 187
結束頁: +
Appears in Collections:Conferences Paper