John White's QUERG DRAUGHTS
Querg Draughts is a strong draughts (checkers) program written in
C. Querg Draughts is stronger than ANY other Atari ST draughts program
known to the author.
Querg Draughts is NOT in the Public Domain. The ownership of this
program is here asserted by the author, John White, of Wokingham,
England.
TO START THE PROGRAM:
RUN the program by double-clicking on "DRAUGHTS.PRG" in MEDIUM
RESOLUTION. A screen display with white text on black background will
be presented, with the black draughts men set up at the bottom of the
screen.
The board is labelled according to the standard draughts
convention (see diagram in The Rules Of Draughts, below). The current
level of search is preset to 5 secs.
TO MAKE YOUR MOVE:
You are always assumed to start as black, who moves first. This
can be altered (see below).
To enter a move, just click with the left mouse button on any
piece, then click on the square to which you wish to move it.
Only legal moves will be accepted. If you change your mind after
clicking on a piece, click on it again to cancel the move.
Multiple jumps can be made by clicking on each vacant square to
which the jumping piece will move in succession. The program is clever
enough to know how often you need to keep jumping, and when the
multiple jump is over.
OTHER OPTIONS:
Click on the appropriate pop-down menu item to obtain other
options.
"About Me" - Provides information about the current version
of Querg Draughts. Quote this in the event of any query.
"New Game" - Sets up board for a new game, using the current
time level.
"Display Board" - This is used for debugging purposes, and acts
solely to refresh the screen display. Click on this if you think the
program is not recognising the board set-up correctly (should never be
needed).
"Switch Sides" - Forces program to move at once for the opposing
side. Can also be used at the beginning of a game to make the program
play as black instead of white.
"Clear Board" - Clears board of all pieces. You then move
automatically to:
"Edit Board" - Board set-up. This facility allows pieces to be
entered on the board, either after the board has been cleared (see
"Clear Board"), or onto an existing board position.
Click on any square repeatedly to cycle from black man > black
king > white man > white king > empty. Then click on other squares to
enter other pieces. Note that you will not be able to set up a black
man on squares 29 to 32 (the promotion squares) or a white man on
squares 01 - 04.
Press ESCAPE key to exit from this facility. Only legal set-ups
will be permitted - there must be at least one piece, and not more
than 12 pieces, for each side.
"Quit" - Ends the program. You will be asked to confirm ("Another
Game (Y/N)?"). Type in N to end the program.
You can also end the program by closing the current window by
clicking on the top left box.
"Levels" - These adjust the AVERAGE time per move (individual
moves will be quicker or slower). Naturally, the more time the
computer has to think, the stronger it becomes! Preset to 5 secs,
Level can range from 0.5 secs (plays very low standard) to 4 mins
(very strong indeed). The program will play to these time constraints,
dynamically adjusting its search depth according to how much time
remains. Time saved as a result of 'instant' moves is added to the
next move. Consequently, all available time is used up in searching
for better moves no matter how many pieces remain on the board.
Mysterious moves occur for two reasons. First, this is a very
strong draughts program and, at longer search times, Querg Draughts
may give up three or even four pieces in a row to make a smashing
counter-attack! Second, very rarely, the program may embark on a very
complex tactical sequence, giving up a piece then, on the next move,
suddenly decide that maybe it wasn't such a great idea after all. This
is an example of what is known technically as the "horizon effect".
The following levels may be set:
Level Time Approx depth of search
0 0.5 sec 3
1 1 sec 4
2 2 sec 4
3 5 sec 5
4 10 sec 5
5 20 sec 6
6 40 sec 7
7 1 min 8
8 1.5 min 8
9 2 min 9
10 4 min 10
(Search depths apply to 8 MHz Atari ST).
"Help" - Help. Provides an instant memory jog for the information
given in these instructions.
SCREEN INFORMATION:
The Move - the moves made by the computer, including multiple
captures where appropriate.
Time - the time taken for the current move, and the average time
taken for the stated number of moves. The latter shoud be within the
time allowed for the current level.
Score - the program's estimate of the score for the CURRENT move
(not for the position reached in the game).
Iteration - the depth to which the program has searched on its
current move. A value of zero means that an instant, forced move was
made.
MISCELLANEOUS BEEPS:
Cancel - you have clicked twice on the starting square for a
piece which has moved, cancelling the move. Click on another piece (or
the same one again) to make a legal move.
Illegal Move - click on the OK button to cancel this dialogue
box.
3-Fold Repeat Draw - computer has detected a repetition of
positions three times (not necessarily in a row), and is claiming a
draw. However, you can still play on.
50 Move Draw - computer has recognised 50 moves played by both
sides without a piece being taken or a man moved, and is claiming a
draw. Again, it is possible to play on.
THE RULES OF DRAUGHTS
Draughts is an ancient game, known in the Egypt of the Pharaohs,
but with its rules formalised in Europe in the 12th Century. It is
known on the Continent as Dames or Damenspiel, and in North America as
Checkers. It was especially popular in Scotland, and many of its
standard book openings have Scottish names.
Draughts is a very good game for a computer. Very recently, the
world (human) champion Dr. Tinsley just managed to win a series of
games against Schaeffer's "Chinook" draughts program running on a
custom-built special computer.
The Objective.
The objective of draughts is to prevent your opponent from having
any legal moves, usually achieved by capturing all his pieces.
Sometimes the game is won when the enemy pieces are blocked so that
they cannot move.
A draw may be declared if the same position occurs three times in
a game (not necessarily in sequence) with the same side to move each
time. A draw may also be declared if 50 moves are made by both sides
without a piece being taken or a man moved (ie, king moves only). A
draw only occurs if it is claimed.
The Board.
Draughts is played on a standard chess board, but making use only
of the dark-coloured squares, numbered according to the standard
draughts convention. Each player starts with twelve 'men', set up as
shown on the opening board screen display. By convention, black always
moves first.
The standard board notation:
..32..31..30..29
28..27..26..25..
..24..23..22..21
20..19..18..17..
..16..15..14..13
12..11..10..09..
..08..07..06..05
04..03..02..01..
The Moves.
Men can be moved diagonally one square forward only onto an
unoccupied square of the same colour. Black plays towards the top of
the screen, white towards the bottom. When a man reaches the opposite
side of the board, it becomes promoted to a 'king'.
Kings can move diagonally one square only, in any of the four
directions possible, onto an unoccupied square of the same colour.
Captures become possible if a man or king can jump diagonally
over a man or king of the opposing side onto a vacant square of the
same colour in the same direction. The captured piece is removed from
the board. If a capture is possible, it MUST be made. If several
captures are possible, the player on the move can elect which capture
to make. (Note: the rule of 'huffing' is not permitted in Querg
Draughts. Huffing is a rule permitted in some draughts circles, where
a player refuses to make a compulsory capture, and loses instead the
piece which should have made the capture).
Multiple captures are also possible, where a man or king can jump
over several enemy men or kings (or both) in one turn. Again, multiple
captures are mandatory, but the player on the move does not have to
make the sequence with the greatest number of jumps - any starting
jump will be permitted so long as all the pieces which can be captured
from the starting jump are taken.
Each man is removed from the board after it has been jumped over
in a multiple capture. Therefore a jumping piece cannot circle around
over an enemy piece, jumping it in both directions.
If a man reaches the opposite side of the board, as a result of
jumps, it becomes a king and the turn ends. It is NOT then permitted
to make further jumping captures as a king on the same turn.
SIMPLE STRATEGIES:
Draughts is a game of tactics and of strategy. It is less complex
than chess, but is still very challenging. A strong player will always
beat a weak player - luck is not involved.
Promote Men - men should be advanced to promote them to kings as
quickly as possible.
Control Centre - beginners always make the mistake of moving
their pieces to the side of the board, in the naive belief that they
will be safer. But a piece on the edge of the board exercises only
half of its mobility and of its ability to control squares.
Centre Kings - kings should be advanced to the centre of the
board as quickly as possible after promotion.
Avoid Tactical Traps - can the other side force you to make a
capture, in a way that permits him to make a multiple capture?
Exchange When Winning - the winning side should exchange off
pieces.
Hold Double Corner - in the endgame, when mostly kings remain,
the losing side should head its king(s) for the 'double corners' at
the top left and bottom right of the board.
Know How to Win Ending - there is a standard formula for two
kings to drive an enemy king out of the double corner. Set up a
position with one black king and two white kings, then observe the
program in action to learn the technique.
WHAT YOU DO NOT SEE:
Beneath the surface of Querg Draughts is some sophisticated A.I.
programming.
The program uses the principle known as "Iterative Deepening" to
find its moves. An iterative (sequential) sequence is used whereby the
program looks ahead initially 1 move (Iteration=1) for itself, and
reorders the list of legal moves in order of value.
Then it looks ahead 2 moves (I move, you move, iteration =2) and
moves the best-yet-found to the head of the list. Then it searches at
iterations 3,4,5... up to the level set, still reordering the list of
legal moves it can make. At iteration 6, for example, the computer
considers the sequence: I move - you move - I move - you move - I move
- you move.
But this is not all! Sequences of forced captures are searched to
'quiescence' - until no more captures can be made - regardless of the
current level of search. There are various ways of doing this, but
Querg Draughts uses the immensely powerful technique of not counting a
capture as a move in its search to a set iteration level. Thus, at an
iteration of 6, Querg is typically looking ahead for most moves to 10
moves deep. This combination of iterative deepening and quiescence
search gives a stunningly strong tactical draughts program.
Pre-programmed book moves are employed to find the best move - on
the basis of best human play - early in the game when the range of
possibilities is small, and again in certain parts of the ending.
These book moves are compressed using an algorithm described by the
author in ICCA Journal, (1990)Vol. 13(1) pp 22-26.
Special endgame routines are also employed when fewer than 6 men
remain on the board, and to chase a lone enemy king. These are briefly
announced by the program before use ("Endgame Routines ON" and "King
Chase ON").
For experienced computer chess programmers, Querg Draughts uses
the following heuristics:
iterative deepening with quiescence search and alpha-beta pruning (an
alpha-beta window was deemed inappropriate for a game with forced
captures). Chopper for forced moves, sorted killer moves, TECH-style
evaluation in mid game, full evaluation at all ply in ending.
Dedicated endgame routines. Repetition of positions/50 move rule is
handled for the program side only at ply=1, using full storage of up
to 50 positions with a hash index.
IN CONCLUSION:
I hope you enjoy playing Querg Draughts. I had a lot of fun
writing it. I hardly ever beat it at levels 6 and above!
John White. December 1992.
"See the draughts players dressed in black,
All suffering from the same lurg;
Moaning, groaning, 'alas, alack -
We've all been zapped by Querg!'".
John White's QUERG DRAUGHTS
Querg Draughts is a strong draughts (checkers) program written in
C. Querg Draughts is stronger than ANY other Atari ST draughts program
known to the author.
Querg Draughts is NOT in the Public Domain. The ownership of this
program is here asserted by the author, John White, of Wokingham,
England.
TO START THE PROGRAM:
RUN the program by double-clicking on "DRAUGHTS.PRG" in MEDIUM
RESOLUTION. A screen display with white text on black background will
be presented, with the black draughts men set up at the bottom of the
screen.
The board is labelled according to the standard draughts
convention (see diagram in The Rules Of Draughts, below). The current
level of search is preset to 5 secs.
TO MAKE YOUR MOVE:
You are always assumed to start as black, who moves first. This
can be altered (see below).
To enter a move, just click with the left mouse button on any
piece, then click on the square to which you wish to move it.
Only legal moves will be accepted. If you change your mind after
clicking on a piece, click on it again to cancel the move.
Multiple jumps can be made by clicking on each vacant square to
which the jumping piece will move in succession. The program is clever
enough to know how often you need to keep jumping, and when the
multiple jump is over.
OTHER OPTIONS:
Click on the appropriate pop-down menu item to obtain other
options.
"About Me" - Provides information about the current version
of Querg Draughts. Quote this in the event of any query.
"New Game" - Sets up board for a new game, using the current
time level.
"Display Board" - This is used for debugging purposes, and acts
solely to refresh the screen display. Click on this if you think the
program is not recognising the board set-up correctly (should never be
needed).
"Switch Sides" - Forces program to move at once for the opposing
side. Can also be used at the beginning of a game to make the program
play as black instead of white.
"Clear Board" - Clears board of all pieces. You then move
automatically to:
"Edit Board" - Board set-up. This facility allows pieces to be
entered on the board, either after the board has been cleared (see
"Clear Board"), or onto an existing board position.
Click on any square repeatedly to cycle from black man > black
king > white man > white king > empty. Then click on other squares to
enter other pieces. Note that you will not be able to set up a black
man on squares 29 to 32 (the promotion squares) or a white man on
squares 01 - 04.
Press ESCAPE key to exit from this facility. Only legal set-ups
will be permitted - there must be at least one piece, and not more
than 12 pieces, for each side.
"Quit" - Ends the program. You will be asked to confirm ("Another
Game (Y/N)?"). Type in N to end the program.
You can also end the program by closing the current window by
clicking on the top left box.
"Levels" - These adjust the AVERAGE time per move (individual
moves will be quicker or slower). Naturally, the more time the
computer has to think, the stronger it becomes! Preset to 5 secs,
Level can range from 0.5 secs (plays very low standard) to 4 mins
(very strong indeed). The program will play to these time constraints,
dynamically adjusting its search depth according to how much time
remains. Time saved as a result of 'instant' moves is added to the
next move. Consequently, all available time is used up in searching
for better moves no matter how many pieces remain on the board.
Mysterious moves occur for two reasons. First, this is a very
strong draughts program and, at longer search times, Querg Draughts
may give up three or even four pieces in a row to make a smashing
counter-attack! Second, very rarely, the program may embark on a very
complex tactical sequence, giving up a piece then, on the next move,
suddenly decide that maybe it wasn't such a great idea after all. This
is an example of what is known technically as the "horizon effect".
The following levels may be set:
Level Time Approx depth of search
0 0.5 sec 3
1 1 sec 4
2 2 sec 4
3 5 sec 5
4 10 sec 5
5 20 sec 6
6 40 sec 7
7 1 min 8
8 1.5 min 8
9 2 min 9
10 4 min 10
(Search depths apply to 8 MHz Atari ST).
"Help" - Help. Provides an instant memory jog for the information
given in these instructions.
SCREEN INFORMATION:
The Move - the moves made by the computer, including multiple
captures where appropriate.
Time - the time taken for the current move, and the average time
taken for the stated number of moves. The latter shoud be within the
time allowed for the current level.
Score - the program's estimate of the score for the CURRENT move
(not for the position reached in the game).
Iteration - the depth to which the program has searched on its
current move. A value of zero means that an instant, forced move was
made.
MISCELLANEOUS BEEPS:
Cancel - you have clicked twice on the starting square for a
piece which has moved, cancelling the move. Click on another piece (or
the same one again) to make a legal move.
Illegal Move - click on the OK button to cancel this dialogue
box.
3-Fold Repeat Draw - computer has detected a repetition of
positions three times (not necessarily in a row), and is claiming a
draw. However, you can still play on.
50 Move Draw - computer has recognised 50 moves played by both
sides without a piece being taken or a man moved, and is claiming a
draw. Again, it is possible to play on.
THE RULES OF DRAUGHTS
Draughts is an ancient game, known in the Egypt of the Pharaohs,
but with its rules formalised in Europe in the 12th Century. It is
known on the Continent as Dames or Damenspiel, and in North America as
Checkers. It was especially popular in Scotland, and many of its
standard book openings have Scottish names.
Draughts is a very good game for a computer. Very recently, the
world (human) champion Dr. Tinsley just managed to win a series of
games against Schaeffer's "Chinook" draughts program running on a
custom-built special computer.
The Objective.
The objective of draughts is to prevent your opponent from having
any legal moves, usually achieved by capturing all his pieces.
Sometimes the game is won when the enemy pieces are blocked so that
they cannot move.
A draw may be declared if the same position occurs three times in
a game (not necessarily in sequence) with the same side to move each
time. A draw may also be declared if 50 moves are made by both sides
without a piece being taken or a man moved (ie, king moves only). A
draw only occurs if it is claimed.
The Board.
Draughts is played on a standard chess board, but making use only
of the dark-coloured squares, numbered according to the standard
draughts convention. Each player starts with twelve 'men', set up as
shown on the opening board screen display. By convention, black always
moves first.
The standard board notation:
..32..31..30..29
28..27..26..25..
..24..23..22..21
20..19..18..17..
..16..15..14..13
12..11..10..09..
..08..07..06..05
04..03..02..01..
The Moves.
Men can be moved diagonally one square forward only onto an
unoccupied square of the same colour. Black plays towards the top of
the screen, white towards the bottom. When a man reaches the opposite
side of the board, it becomes promoted to a 'king'.
Kings can move diagonally one square only, in any of the four
directions possible, onto an unoccupied square of the same colour.
Captures become possible if a man or king can jump diagonally
over a man or king of the opposing side onto a vacant square of the
same colour in the same direction. The captured piece is removed from
the board. If a capture is possible, it MUST be made. If several
captures are possible, the player on the move can elect which capture
to make. (Note: the rule of 'huffing' is not permitted in Querg
Draughts. Huffing is a rule permitted in some draughts circles, where
a player refuses to make a compulsory capture, and loses instead the
piece which should have made the capture).
Multiple captures are also possible, where a man or king can jump
over several enemy men or kings (or both) in one turn. Again, multiple
captures are mandatory, but the player on the move does not have to
make the sequence with the greatest number of jumps - any starting
jump will be permitted so long as all the pieces which can be captured
from the starting jump are taken.
Each man is removed from the board after it has been jumped over
in a multiple capture. Therefore a jumping piece cannot circle around
over an enemy piece, jumping it in both directions.
If a man reaches the opposite side of the board, as a result of
jumps, it becomes a king and the turn ends. It is NOT then permitted
to make further jumping captures as a king on the same turn.
SIMPLE STRATEGIES:
Draughts is a game of tactics and of strategy. It is less complex
than chess, but is still very challenging. A strong player will always
beat a weak player - luck is not involved.
Promote Men - men should be advanced to promote them to kings as
quickly as possible.
Control Centre - beginners always make the mistake of moving
their pieces to the side of the board, in the naive belief that they
will be safer. But a piece on the edge of the board exercises only
half of its mobility and of its ability to control squares.
Centre Kings - kings should be advanced to the centre of the
board as quickly as possible after promotion.
Avoid Tactical Traps - can the other side force you to make a
capture, in a way that permits him to make a multiple capture?
Exchange When Winning - the winning side should exchange off
pieces.
Hold Double Corner - in the endgame, when mostly kings remain,
the losing side should head its king(s) for the 'double corners' at
the top left and bottom right of the board.
Know How to Win Ending - there is a standard formula for two
kings to drive an enemy king out of the double corner. Set up a
position with one black king and two white kings, then observe the
program in action to learn the technique.
WHAT YOU DO NOT SEE:
Beneath the surface of Querg Draughts is some sophisticated A.I.
programming.
The program uses the principle known as "Iterative Deepening" to
find its moves. An iterative (sequential) sequence is used whereby the
program looks ahead initially 1 move (Iteration=1) for itself, and
reorders the list of legal moves in order of value.
Then it looks ahead 2 moves (I move, you move, iteration =2) and
moves the best-yet-found to the head of the list. Then it searches at
iterations 3,4,5... up to the level set, still reordering the list of
legal moves it can make. At iteration 6, for example, the computer
considers the sequence: I move - you move - I move - you move - I move
- you move.
But this is not all! Sequences of forced captures are searched to
'quiescence' - until no more captures can be made - regardless of the
current level of search. There are various ways of doing this, but
Querg Draughts uses the immensely powerful technique of not counting a
capture as a move in its search to a set iteration level. Thus, at an
iteration of 6, Querg is typically looking ahead for most moves to 10
moves deep. This combination of iterative deepening and quiescence
search gives a stunningly strong tactical draughts program.
Pre-programmed book moves are employed to find the best move - on
the basis of best human play - early in the game when the range of
possibilities is small, and again in certain parts of the ending.
These book moves are compressed using an algorithm described by the
author in ICCA Journal, (1990)Vol. 13(1) pp 22-26.
Special endgame routines are also employed when fewer than 6 men
remain on the board, and to chase a lone enemy king. These are briefly
announced by the program before use ("Endgame Routines ON" and "King
Chase ON").
For experienced computer chess programmers, Querg Draughts uses
the following heuristics:
iterative deepening with quiescence search and alpha-beta pruning (an
alpha-beta window was deemed inappropriate for a game with forced
captures). Chopper for forced moves, sorted killer moves, TECH-style
evaluation in mid game, full evaluation at all ply in ending.
Dedicated endgame routines. Repetition of positions/50 move rule is
handled for the program side only at ply=1, using full storage of up
to 50 positions with a hash index.
IN CONCLUSION:
I hope you enjoy playing Querg Draughts. I had a lot of fun
writing it. I hardly ever beat it at levels 6 and above!
John White. December 1992.
"See the draughts players dressed in black,
All suffering from the same lurg;
Moaning, groaning, 'alas, alack -
We've all been zapped by Querg!'".