Research and Implementation of Dots-and-Boxes Chessboard Based on the Game Strings-and-Coins - Advanced Research on Computer Education, Simulation and Modeling - page 14

Research and Implementation of Dots-and-Boxes
Chessboard Based on the Game Strings-and-Coins
Dongming Li, Shuqin Li, and Hua Bao
Department of Computer Science Beijing Information & Science Technology University,
Beijing China 100192
[e-mail]
Abstract. The model of computer game system is important for us to make
careful analyses of games; generally this model includes description of the board,
rules of the game, searching method and estimation value. Dots-and-Boxes is a
familiar paper and pencil game for two players, while Strings-and-Coins is a
game invented by Elwin Berlekamp to generalize Dots-and-Coins to general
graphs. In this paper we made a detailed analysis trying to talk about if the two
games are equivalent and to discuss how to describe the Dots-and-Coins chess-
board by generalizing Strings-and-Coins graphs. Because of the advantage of
Stings-and-Coins that it can be played on any graph, it can simplify certain
Dots-and-Boxes observations and is convenient to recognize the chain or cycle
formed in the process of playing game, compared with other descriptions of
board, this way is effective in improving the efficiency of programs.
Keywords: computer game; dots and boxes; description of chessboard; Strings
and Coins.
1 Introduction
Computer gambling, which is also called Machine Gambling, has a simple definition
that it tries to make machines think like human while playing chess. Computer gam-
bling is one of the important research fields of artificial intelligence (AI) and an
important aspect of proving the level of AI [1]. In 1997, an artificial intelligence mile-
stone, IBM's Deep Blue conquered Kasparov, the international champion of chess, this
match is a classic competition between human and computer, it indicates that computer
gambling can achieve the level of world champion.
There are many Computer gambling like Dots-and-Boxes, Gobang, Chinese Chess
and Go. In this paper we took a deep research on the description of Dots and Boxes
chessboard.
2 Stings-and-Coins and Dots-and-Boxes
The Fig.1 indicates the description of Dots and Boxes board, and we can see that it is a
6*6 dots matrix or 5*5 boxes matrix, also it can have another size, the rules of the game