Abstract
The classical area of AI application is the board games. This chapter introduces the two most prominent AI approaches used in developing board game agents – the MinMax algorithm and Machine Learning and explains their usage in playing games like tic-tac-toe, checkers, othello, chess, go, etc., against human opponents. The game tree is essentially a directed graph, where the nodes represent the positions in the game and the edges the moves. Even a simple board game like tic-tac toe (noughts and crosses) has as many as 255,168 leaf nodes in the game tree. Traversing the complete game tree becomes an NP-hard problem. Alpha-beta pruning is used to estimate the short-cuts through the game tree. The board game strategy depends on the evaluation function, which is a heuristic indicating how good the player's current move is in winning the game. Machine learning algorithms try to evolve or learn the agent's game playing strategy based on the evaluation function.
TopBackground
Playing games intelligently and trying to win against human champions has been a grand challenge for Artificial Intelligence from its inception. Chess, in particular, has been referred to as the Drosophila of AI. The first study in computer chess was published by Claude Shannon in 1950 (Shanon, 1950). However, the first working AI programs were for playing checkers (Samuel, 1960; Samuel, 1967). In the 1970s and 1980s, computer-games research concentrated on chess and the brute-force search approach (Schaeffer, 2002). The triumph of AI in computer games came in the 1990s when to everyone’s surprise AI programs began to defeat the reigning world champions. In 1994, the program CHINOOK won the World Man–Machine Championship (Schaeffer, 1997). Three year later, IBM’S DEEP BLUE defeated the World Chess Champion Garry Kasparov (Hsu, 2002) and LOGISTELLO won against the Othello Champion Takeshi Murakami (Buro, 1997). Finally, in 2011, IBM’s WATSON defeated the world champions in the quiz game of Jeopardy.
Key Terms in this Chapter
Ply: Refers to the number of levels in the game tree including the root level.
Artificial Intelligence: It is a branch of computer science concerned with making computers do things that require intelligence when done by human beings.
MiniMax Algorithm: It is a winning search strategy through the nodes and branches of the game tree. It is based on the principal that the algorithm's opponent will try to minimize whatever value the algorithm tries to maximize.
Zero-Sum Game: It is a situation in which one player’s win implies the other’s loss. The sum of the scores in the win-loss or the draw is always zero.
Machine Learning: Refers to the activity or ability of computer programs to learn without being explicitly programmed given an adequate amount of data.
Game Tree: It is a graph consisting of nodes and edges that represent all the possible legal moves of a (board) game. The nodes are positions in a game and the edges are moves.
Neural Network: A network consisting of several layers of nodes and connections with weights which models the information processing operation of the human brain. Neural networks are used in Machine Learning as universal function approximators.
Board Game: It is a game in which two or more players take turns in placing or moving pieces on a pre-marked surface or board, according to a set of rules.