Entry
Delphi: Game: Two person: How to create a chess playing machine using Delphi?
Jun 2nd, 2002 15:16
Knud van Eeden,
Steps: Overview:
1. Create a board
1.1 Divide it in 8 x 8 fields
1.1.1 Represent the fields in 2 different colors
1.2 Create chess pieces
1.2.1 Bishop
1.2.2 Knight
1.2.3 King
1.2.4 Pawn
1.2.5 Queen
1.2.6 Rook
1.3 Represent the chess pieces in 2 different colors
1.4 Show the board on the screen
2. Let the player choose between playing:
2.1 Another player
2.2 Against the computer
3. Successively let one player play, then the other, until
stop/win/draw
3.1 Algorithms
3.1.1 Each position of pieces has a numeric value (e.g. -100000 if
chessmate against you, +1000 when you can take a tower, ...)
3.1.2 Check the possibilities systematically
3.1.2.1 using a treewalk: depth first search
3.1.2.1.1 Use the minimax method to decide which possibility to
choose
3.1.2.1.1.1 Use the alphabeta pruning to reduce the amount of
possibilities you have to check
3.1.2.2 using a treewalk: breadth first search
3.1.2.2.1 Use the minimax method to decide which possibility to
choose
3.1.2.2.1.1 Use the alphabeta pruning to reduce the amount of
possibilities you have to check
3.2 Datastructures
3.2.1 To store the result use for example
3.2.1.1 Arrays
3.2.1.2 Linked lists
3.2.1.3 Trees
3.2.1.4 Graphs
3.3 Show the moves on the board
3.3.1 Get the new move
3.3.2 Remove the old move
3.3.3 Set the new move
3.3.4 Show the in between moves
3.4 Store the results
3.4.1 File input
3.4.2 File output
3.5 Use libraries
3.5.1 previous moves
3.5.2 opening moves
3.5.2 end moves
4. Pronounce the endresult
---
// libary: game: two person: structure: general [kn, ri, su, 02-06-2002
22:20:25]
procedure PROCGame( gamenameS : string; playername1S : string;
playername2S : string );
// e.g. PROCGame( 'Chess', 'Knud', 'Kasparov' );
// e.g. PROCGame( 'Checkers', 'Knud', 'Berliner' );
// e.g. PROCGame( 'BackGammon', 'Knud', 'Berliner' );
// [book: see also: author: McGregor, Jim / Watt, Alan - title:
advanced programming techniques for the BBC micro - publisher: Addison-
Wesley - year: 1983 - ISBN 0-201-14059-4 - p. 14 'Program structure for
playing a board game']
begin
PROCGameInitialize;
PROCGameHelpInstructions;
PROCGameWhoIsGoingToPlay;
PROCGameBoardCreate;
PROCGameBoardShow;
repeat
if ( turnS == playername1S ) then begin
PROCGamePlayer1;
end;
else begin
PROCGamePlayer2;
end;
PROCGameBoardShow;
until FNGameEndReachedB;
PROCGameWinnerPronounce;
end;
//
procedure PROCGameInitialize;
begin
end;
//
procedure PROCGameHelpInstructions;
begin
end;
//
procedure PROCGameWhoIsGoingToPlay;
begin
end;
//
procedure PROCGameBoardCreate;
begin
end;
//
procedure PROCGameBoardShow;
begin
end;
//
procedure PROCGamePlayer1;
begin
end;
//
procedure PROCGamePlayer2;
begin
end;
//
function FNGameEndReachedB;
begin
result := ...;
end;
//
procedure PROCGameWinnerPronounce;
begin
end;
---
[book: source: author: Newman, James R. - title: the world of
mathematics - publisher: Simon and Schuster, New York - year: 1956 - p.
2126 'A chess playing machine, by Claude E. Shannon (published in
1949)']
The problem of setting up a computer for playing chess can be divided
into
three parts:
1. a code must be chosen so that chess positions and the chess pieces
can
be represented by numbers
2. a strategy must be found for choosing the moves to be made
3. a strategy must be translated into a sequence of elementary computer
orders, or a program
---
A suitable code for the chessboard and the chess pieces is shown in the
figure.
| 1 2 3 4 5 6 7 8
-+------------------------
8| -4 -2 -3 -5 -6 -3 -2 -4
|
7| -1 -1 -1 -1 -1 -1 -1 -1
|
6|
|
5|
|
4|
|
3|
|
2| +1 +1 +1 +1 +1 +1 +1 +1
|
1| +4 +2 +3 +5 +6 +3 +2 +4
figure:
code for a chess playing machine is plotted on a chessboard.
Each square can be designated by two digits, one representing the
horizontal row and the other the vertical row.
Pieces are also coded in numbers.
---
Each square on the board has a number consisting of two digits, the
first
digit corresponding to the 'rank' or horizontal row, the second to
the 'file'
or vertical row.
Thus e.g. the square in the topleft corner of the board would be
represented by (8,1), and the square in the bottomright by (1,8).
---
Each different chess piece also is designated by a number:
A pawn is numbered 1
A knight is numbered 2
A bishop is numbered 3
A rook is numbered 4
A queen is numbered 5
A king is numbered 6
---
White pieces are represented by positive numbers and black pieces by
negative ones.
---
The positions of all the pieces on the board can be shown by a sequence
of 64 numbers, with zeros to indicate the empty squares.
For example this would be the 64 numbers representing the start of the
game:
-4, -2, -3, -5, -6, -3, -2, -4, -1, -1, -1, -1, -1, -1, -1, -1, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, +1, +1, +1, +1, +1, +1, +1, +1,
+4, +2, +3, +5, +6, +3, +2, +4
or similarly written in row column form:
-4, -2, -3, -5, -6, -3, -2, -4
-1, -1, -1, -1, -1, -1, -1, -1
0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 0, 0
+1, +1, +1, +1, +1, +1, +1, +1
+4, +2, +3, +5, +6, +3, +2, +4
PS Thus all the moves of the game (say player one makes totally P1
moves and
player 2 makes totally P2 moves can be stored in (P1 + P2) rows of 64
columns,
or similarly in an array of (P1 + P2) times an array of (8, 8).
Thus any chess position can be recorded as a series of numbers and
stored
in the numerical memory of the computing machine.
---
A chess move is specified by giving the number of the square on which
the
piece stands and of the one to which it is moved
(e.g. from (row, column) equal to (1,2) to (2,3))
Ordinarily two numbers would be sufficient to describe a move, but to
take
care of the special case of promotion of a pawn to a higher piece a
third
number is necessary. This number indicates the piece to which the pawn
is
converted. In all other moves the third number is zero.
Thus a knight move from square 01 to 22 is encoded into 01, 22, 0.
The move of a pawn from 62 to 72, and its promotion to a queen is
represented
by 62, 72, 5.
---
The second main problem is that of deciding on a strategy of play.
A straightforward process must be found for calculating a reasonably
good
move for any given chess position.
This is the most difficult part of the problem.
The programmer can employ here the principles of correct play that have
been
evolved by expert chess players.
These empirical principles are a means of bringing some order to the
maze
of possible variations of a chess game.
Even the high speeds available in electronic computers are hopelessly
inadequate to play perfect chess by calculating all possible variations
to the end of the game.
In a typical chess position there will be about 32 possible moves with
32 possible replies, already this creates 32 times 32 or 1024
possibilities,
or thus about 10^3 possibilities.
Most chess games last 40 moves or more for each side. So the total
number
of possible variations in an average game is thus about
(total amount of possibilities on a given position)^(total amount of
moves),
or thus (10^3)^(40) or about 10 to the power 120.
A machine calculating one variation each millionth of a second would
require over 10^95 years to decide on its first move!
---
Other methods of attempting to play perfect chess seem equally
impracticable,
we resign ourselves, therefore, to having the machine play a reasonably
skillful game, admitting occasional moves that may not be the best.
This, of course, is precisely what human players do: no one plays a
perfect
game.
---
In setting up a strategy on the machine, one must establish a method of
numerical evaluation for any given chess position.
A chess player looking at a position can form an estimate as to which
side, White or Black, has the advantage.
Furthermore, his evaluation is roughly quantitive.
He may say 'White has a rook for a bishop, and advantage of about two
pawns'. Or 'Black has sufficient mobility to compensate for a sacrificed
pawn'. These judgements are based on a long experience and are
summarized
in the principles of chess expounded in chess literature.
---
For example it has been found that:
a queen is worth nine pawns
a rook is worth five pawns
a bishop is worth three pawns
a knight is worth three pawns.
As a rough approximation, a position can be evaluated by merely ADDING
UP
the total forces for each side, measured in terms of the pawn units.
For example, for the starting position of the game, you have for White
the
evaluation:
(1 rook worth 5 pawns) +
(1 knight worth 3 pawns) +
(1 bishop worth 3 pawns) +
(1 queen worth 9 pawns) +
(1 bishop worth 3 pawns) +
(1 knight worth 3 pawns) +
(1 rook worth 5 pawns) +
(8 pawns)
Thus its value is 5 + 3 + 3 + 9 + 3 + 3 + 5 + 8 = +39 pawns.
Similarly for Black the value is -39 pawns.
---
There are however numerous other features which must be taken in
account:
The mobility of the pieces
The placement of the pieces
The weakness of the king protection
The nature of the pawn formation
and so on...
These too can be given numerical weights and combined in the evaluation,
and it is here that the knowledge and experience of the chess masters
must be enlisted.
---
Assuming that a suitable method of position evaluation has been decided
upon, how should a move be selected?
The simplest process is to consider all possible moves in the given
position, and choose one that gives the best immediate evaluation.
Since, however, chess players generally look more than one move ahead,
one
must take account of the opponent's various possible responses to each
projected move.
Assuming that the opponent's reply will be the one giving the best
evaluation
from his point of view, we would choose the move that would leave us as
well off as possible after his best reply.
Unfortunately with the computer at present available, the machine would
not
explore all the possibilities for more than two moves ahead for each
side,
so a strategy of this type would play a poor game by human standards.
Good chess players frequently play combinations four or five moves deep,
and occasionally world champions have seen as many as 20 moves ahead.
This is possible only because the variations they consider are highly
selected. They do not investigate all lines of play, but only the
important
ones.
The amount of selection exercised by chess masters in examining possible
variations has been studied experimentally by the Dutch chess master and
psychologist A. D. De Groot.
He showed various typical positions to chess masters and asked them to
decide on the best move, describing aloud their analyses of the
positions
as they thought them through.
By this procedure the number and depth of the variations examined could
be determined.
In one typical case a chess master examined 16 variations, ranging in
depth
from one Black move to five Black and four White moves. The total
number of position considered was 44.
Clearly it would be highly desirable to improve the strategy for the
machine
by including such a selection process in it.
Of course one could go too far in this direction.
Investigating one particular line of play for 40 moves would be as bad
as investigating all lines for just two moves.
A suitable compromise would be to examine only the important possible
variations, that is, forcing moves, captures and main threats, and carr
out
the investigation of the possible moves far enough to make the
consequences
of each fairly clear.
It is possible to set up some rough criteria for selecting important
variations,
not as efficiently as a chess master, but sufficiently well to reduce
the
number of variations appreciably and thereby permit a deeper
investigation
of the moves actually considered.
---
The final problem is that of reducing the strategy to a sequence of
orders,
translated into the machine's language.
This is a relatively straight forward but tedious process, and we shall
only
indicate som of the general features.
The complete program is made up of nine sub-programs and a master
program
that calls the sub-programs into operation as needed.
Six of the sub-programs (one for each of the 6 possible pieces: rook,
knight, bishop, queen, king,
pawn) deal with the movements of the various kinds of pieces.
In effect they tell the machine the allowed moves for these pieces.
Another sub-program enables the machine to make a move 'mentally'
without
actually carrying it out:
that is, with a given position stored in its memory it can construct the
position that would result if the move were made.
The seventh sub-program enables the computer to make a list of all
possible
moves in a given position.
The last sub-program evaluates any given position.
The master program correlates and supervises the application of the
sub-programs.
It starts the seventh sub-program making a list of possible moves, which
in turn calls the in previous sub-programs to determine where the
various pieces could move.
The master program then evaluates the resulting positions by means of
the
eight sub-program and compares the result according to the process
described
above.
After comparison of all the investigated variations, the one that gives
the
best evaluation according to the machine's calculations is selected.
This move is translated into standard chess notation and typed out by
the machine.
---
As described so far, the machine would always make the same move in the
same position.
If the opponent made the same moves, this would always lead to the same
game.
Once the opponent won a game, he could win everytime thereafter by
playing
the same strategy, taking advantage of some particular position in which
the machine chooses a weak move.
One way to vary the machine's play would be to introduce a statistical
element.
Whenever it was confronted with two or more possible moves that were
about
equally good according to the machine's calculations, it would choose
from
them at random.
This if it arrived at the same position a second time, it might choose a
different move.
---
Another place where statistical variation could be introduced is in the
opening game.
It would be desirable to have a number of standard openings, perhaps a
few hundred, stored in the memory of the machine (or in a file).
For the first few moves, until the opponent deviated from the standard
responses of moves, the machine would play by memory.
This could hardly be considered cheating, since that is the way chess
masters play the opening.
---
The chief weakness of the machine is that it will not learn by its
mistakes.
The only way to improve its play is by improving the program.
Some thought has been given in designing a program that would develop
its own improvements in strategy with increasing experience in play.
Although it appears to be theoretically possible, the methods thought of
so far do not seem to be very practical.
One possibility is to devise a program that would change the terms and
coefficients involved in the evaluation function on the basis of games
the
machine had already played. Small variations might be introduced in
these
terms, and the values would be selected to give the greatest percentage
of wins.
---
[book: see also: author: Herik, Jaap van den / Diepen, Peter van -
title: schaken voor computers - publisher: Academic service - year:
1987 - ISBN 90-6233-271-4]
[book: see also: author: Horowitz, Ellis / Sahni, Sartaj - title:
fundamentals of datastructures in Pascal - publisher: Computer Science
Press - year: 1987 - ISBN 0-88175-165-0 - p. 248 'Game trees']
[book: see also: author: Levy, David - title: computer chess
compendium - publisher: Springer Verlag - year: 1988 - ISBN 0-387-91331-
9]
[book: see also: author: Liffick, Blaise - title: the BYTE book of
Pascal - publisher: McGraw-Hill - year: 1979 - p. 107 'Creating a chess
player, by Peter W. Frey and Larry R. Atkin']
[book: see also: author: McGregor, Jim / Watt, Alan - title: advanced
programming techniques for the BBC micro - publisher: Addison-Wesley -
year: 1983 - ISBN 0-201-14059-4 - p. 258 'Board games and game trees
(recursion, generate the game tree, mutually recursive functions for
minimaxing, exhaustive lookahead, decision tables, static evaluation
function, tree pruning, alpha beta pruning, alpha cut off, beta cut
off)']
[book: see also: author: Newman, James R. - title: the world of
mathematics - publisher: Simon and Schuster, New York - year: 1956 - p.
2124 'A chess playing machine, by Claude E. Shannon']
---
[Internet: see also: http://www.google.com/search?
hl=en&ie=UTF8&oe=UTF8&q=Creating+a+chess+player+Peter+Frey+Larry+Atkin :
COMPUTER CHESS METHODS: then click on 'View as HTML' to see several
evaluation algorithms in Pascal]
[Internet: see also:
http://www.faqts.com/knowledge_base/view.phtml/aid/16799/fid/175]
