1. Game-Playing Subsystem : Introduction

 

1.1 Objectives

These goals were established for this portion of the project:
  • The system must understand the basic rules of chess.
  • The system must know when the game is over for wins, losses, and draws.
  • The system must always choose moves that will maximize the strength of its own position. This includes finding all checkmate combinations within some pre-specified depth of search.
  • The system must choose each move in two minutes or less.

1.2 System Overview

The chess player divides neatly into two parts.

The first is a "rules engine" for the game of chess. Here, structures are defined for representing boards and moves. Several functions are implemented that allow the system to "understand" the rules of chess. The highest-level interface to this logic is a function named moves, which returns a list of all of the moves available from a given position.

The second part uses this list of moves and attempts to determine a "best" move from a given position. A standard alpha-beta minimax lookahead is used, with some extensions. In particular, the depth of lookahead is determined for each subtree by the degree to which that subtree look interesting. Lines involving captures or dynamic changes in the strength of one player's position will be explored more fully than lines that only involve relatively static moves. At the leaves of the search tree, an heuristic evaluation function is applied.

Part 2 of this document addresses each of these areas in detail.

1.3 Review of Similar Projects

Computer chess is well-studied problem that has been approached in many different ways. The earliest "automated" chess player was probably Alan Turing's TUROCHAMP - an algorithmic method for scoring positions that amounted to a one-ply lookahead search.

By 1958, Alex Bernstein and Alex de V. Roberts had written a program that could play an actual, live game against a human on an IBM 704. Interestingly, it used a decision-rule method for determining which branches of the game tree to explore.

Research in this area has been continuous. Many additional advancements have been made since then, until in 1997, IBM's Deep Blue defeated the reigning world champion in a six-game match, representing the ultimate achievement for a game-playing machine.

These examples are just a very small sampling of the variety of attempts made to build machines that play chess. A more detailed history of this area of study can be found in David Levy's Chess and Computers.

[Table of Contents] [Next Section]