Massachusetts Institute of Technology: Leslie Kaelbling and Tomás Lozano-Pérez's "Constraint Satisfactory Problems (CSP) and Games"

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.