Unit 4: Game Playing
Some of the earliest and most recognizable AI applications are games like chess and tic-tac-toe, the most famous being the chess match between Garry Kasparov and Deep Blue. In this unit, we will discuss the development of game-playing applications, as well as the relationship between game-playing and searching algorithms. The unit will also provide you with some best practices for building game programs.
This unit has been designed to teach you how to design algorithms for game-playing applications. For our purposes, you will find tic-tac-toe, which uses features of search and constraint satisfaction, the simplest. We suggest that as an informal exercise, you create a tic-tac-toe application and then play against it, noting the algorithm's success rates and determining which modifications will need to be implemented in order to improve its performance.
Completing this unit should take you approximately 10 hours.
4.1: Background: Game Playing in AI
Read this history of artificial intelligence.
Review these slides. Game playing provided numerous applications that motivated the development of AI techniques, such as search and problem-solving techniques. In addition, it served as a popular benchmark for demonstrating progress and improvements of AI research.
4.2: Applicability of Search
Read section 2.5 for a discussion of how to program searching and implement those ideas in Java programs for game playing. Min-max is a search strategy for two-person games whereby a move is selected by choosing the child node that has either the maximum (a player strives to maximize his/her advantage) or minimum (a player strives to minimize the other player's advantage). Alpha-Beta search is an improvement of min-max searching by eliminating, or pruning, branches from the search tree.
Read these slides, which discuss the application of ideas presented so far on two-person games, like tic-tac-toe, checkers, and chess. The states of a board game are the board positions or configurations of the game pieces, such as pieces on the chessboard. The states are represented by the nodes of a tree. The game moves, or operators, are represented by the arcs of a tree. The goal state is a goal node, i.e., the board configuration that depicts the winning position of the game pieces. In many games, the size of the search tree can be very large and the complexity of the search can be high. Heuristics are used to guide the search, increase efficiency, and improve game-playing ability.
Read these slides. MinMax and Alpha-Beta are fundamental search algorithms used in game playing.