(How to Write a Chess-Playing Program, Part 1
: Page 1 of 1 )
In a battle with a chess-playing computer program, a human often asks himself the question: "What is the nature of its intelligence?" In this article I will try to give the answer by demonstrating how to develop a chess program. Programming chess is not actually a very difficult task: To choose the right move, a human player tries to look ahead a few moves, predicting possible replies from his opponent. Computer chess tries to mimic this behavior with the help of search algorithm, which is the brain of any chess program.
The first part of this two-part series provides some background in game theory and uncovers some of the most popular search algorithms. In the second part this knowledge is applied practically: I will show how to develop a chess program.
Theory
In the theory of games, chess belongs to the class of two-person perfect information zero-sum games. This means that:
At any time all moves of each player are known.
The loss of one player is the gain of the other.
From the viewpoint of a single player, one player makes moves trying to maximize the likelihood of a positive outcome for this person, while the other tries to minimize this likelihood. Due to this the first player (the one who makes the first move) is called Max and the second is called Min. The whole process of playing a game can be represented as a game tree. Nodes of this tree represent game states and edges represent players' moves. Let us consider the game tree of tic-tac-toe as an example:
Figure 1
Each leaf of the tree stands for the final state and defines the outcome of the game. (The last term in bold is defined by the theory of zero-sum games as the win or loss of player Max). We will understand the value of each node to be the outcome of the game which starts from this node.
2008 International Mathematica Conference Dr. Dobb's interviews Wolfram Research's Theo Gray, co-founder and Director of User Interfaces, and Roger Germundsson, Director of Research and Development, about the upcoming 2008 International
Mathematica Conference.
How Do You Do Nightly Builds and Tests when there is No Overnight? Software Production in a Geographically Distributed Environment
Attend this Webcast and find out how to overcome common build-test-deploy challenges that affect all members of a distributed team, including:
<ul>
<li> Communication difficulties, because of time-zone and cultural differences</li>
<li> Workflow challenges, like lack of documented procedures and build and test handoff problems</li>
<li> Slow build and test cycles, broken builds, and other factors that hamper distributed team productivity</li>
</ul>
Thursday, September 25, 2005 " 11am PT / 2pm ET
</p>
In this volume of Best of BYTE, we explore the emergence of some heuristic algorithms. Although we have only scratched the surface of this intriguing subject, we hope we've suggested the potential of the synthesis of heuristics and algorithms.
