G. Wiesenekker. GWD a draughts program.
Copyright (C) 1993-1994  G. Wiesenekker
E-mail: wiesenekker@sara.nl

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

WELCOME

Murphy's Draughts Program Law:
Bugs in draughts programs usually show up during computer draughts 
championships.

INSTALLATION (UNIX ONLY)

Edit the Makefile and choose your favourite C-compiler and CFLAGS.

Type 'make gen'.
  This compiles gen.
Type 'make pat'
  This generates the positional code.
Type 'make gwd'.
  This compiles gwd.
Type 'make check'.
  This solves a problem and checks the output against an output generated at 
  my site.
  Only the 'time=' things should be different, not the 'stats='.

You are now ready to use the program. To play against it, type
'touch game.txt' followed by 'gwd black game.txt' and play some moves.
If you type '?' you get a list of legal moves. When entering moves,
only the first few characters which make the move unique have to 
be entered.  'quit' exits the program.

If this worked, try to choose CACHE_BITS (defines the size of the hash table
for the alpha beta) and SCORE_CACHE_BITS (defines the size of the hash table
used for the static evaluation) in draughts.c as large as possible (say such 
that the total sizes of the hash tables equals half of the physical memory 
in your machine).

It is very easy to add positional code to the draughts program. You just add
patterns to the file 'gencode.dat' and add the defines to 'pat.h' and 
the functions (if necessary) to 'patfunc.c'. The program 'gencode' will 
generate from 'gencode.dat' branch optimized C-code to check for these 
patterns and add the defines or call the functions.
You only have to define the patterns and functions for white, the program 
will automatically apply the patterns and functions for black.
See the files 'gencode.dat', 'pat.h' and 'patfunc.c' for examples.
In gencode.dat
'xx' stands for 'field should be empty'.
'??' stands for 'field can contain anything'.

You can use the following macro's in functions:
W(X)   : returns true if field X is white.
B(X)   : returns true if field X is black.
M(X)   : returns true if field X is a man.
C(X)   : returns true if field X is a crown.
WM(X)  : returns true if field X is a white man.
BM(X)  : returns true if field X is a black man.
WC(X)  : returns true if field X is a white crown.
BC(X)  : returns true if field X is a black crown.
The macro's NOTW(X), NOTB(X) etc. return true if field X is not white, 
not black etc.
EMP(X) : returns true if field X is empty.
ANY(X) : returns true if field X is not empty.
WTOT   : returns the total number of white pieces.
BTOT   : returns the total number of black pieces
WMTOT  : returns the total number of white men.
BMTOT  : returns the total number of black men.
WCTOT  : returns the total number of white crowns.
BCTOT  : returns the total number of black crowns.

READ THIS TOO

The purpose of this distribution is to provide you with the source
code of a working draughts program, so that you can improve it.
You can use it 'sec', but it plays poorly, and because
it is designed to play in computer draughts tournaments, the user interface
is not that friendly e.g.

Possible GWD FAQ

Q: Why is it called GWD?
A: Gijsbert Wiesenekker Draughts (and the name resembles a Dutch curse).

Q: GWD gives strange error messages when I do something wrong.
A: Correct. The error messages are only understandable by someone who takes
   a look at the code.

Q: GWD prints a weird malloc error when I start it up.
A: Probably the hash tables are too big. At startup GWD prints
   the sizes of the hash tables in bytes.
   Edit draughts.c and change CACHE_BITS and SCORE_CACHE_BITS to a lower value.
   Recompile and try again.

Q: How can I undo a move? 
A: Quit the program; Edit the file with the moves; Restart the program

Q: How can I change the starting position?
A: GWD reads the starting position from the file 'brd.txt'. You can change
   the starting position by editing this file.

Q: GWD now uses 90 minutes for the first 60 moves, and than 60 minutes
   for the next 40 moves. How can I make it play with different time
   limits?
A: Edit util.c and change the GAME_TIME1 and GAME_TIME2 defines.
   Recompile.
   
Q: GWD asks 'GameTimeUsed? (min) ' when 5 moves have been played.
A: Correct. GWD was designed to play in computer chess tournaments,
   so you have to synchronize the internal clock
   of the computer with the external clock (especially
   useful if you missed the 'bleep' when GWD announced it's move).
   Edit util.c and change the 
   'if ((ngame_moves > 0) and (ngame_moves % 5) == 0)' to 'if (FALSE)'.

etc. etc.

HOW TO STUDY THE CODE

The chess program zzzzzz is documented very well.
Study zzzzzz.h first, then zzzzzz.c and util.c. You are advised to study the 
the references as well.
Although the code is written reasonably well, there are some places 
where it is clear that Hm-the-tournament-is-next-week-and-that-
option-still-does-not-work-thoughts troubled my brain.
Some comments about my coding style:
Fields of a struct are usually prefixed with the name of the struct.
Braces are placed like
{
}
If if-then-else is used inside a loop, I use continue, rather than
else to avoid excessive indentation.

PROGRAM OPTIONS
Note: an a MAC (which has no command line interface) you can enter these
options and commands in the file 'arg.txt'.

Commandline options:
-DepthMax n
   set the maximum search depth to n.
-TimeLimit t
   Set the time limit to t seconds per move (not used when playing a game
   against GWD. Then the time limit is calculated from the GAME_TIME and
   NGAME_MOVES parameters in util.c).
-GameTimeUsed t
   Set the GameTimeUsed to t minutes (only used when playing a game against
   GWD. Useful when you entered a wrong move, and have to edit the file 
   with the moves played sofar to undo the move).
-NoPos
   Disable the positional evaluation
-NoEndgame
   Disable the endgame databases.
-NoAppend
   Do not append the move played to the file with moves (useful when debugging).

The possible commands are:

pos posfile
  Reads in the positions on the file posfile and prints the pseudo legal 
  moves for white and black and the static evaluation for white and black.
  Useful when debugging the move generation and the static evaluation
  function.

anal gamefile
  Reads in the moves in the file gamefile and evaluates each position of 
  the game.

solve problemfile
  Reads the problems (the position and the best move) from
  the file problemfile, and compares it to the move GWD would
  have played in that position. After processing all problems the number
  of problems solved is printed.
  Try 'gwd solve std.txt' for an example.
  
batch gamefile
  reads the moves played sofar from the file gamefile, and appends a move
  to the gamefile. This can be used for automatic play. See the file
  job1 for an example.

white gamefile
  Play a game against GWD. GWD plays white. The moves played sofar will
  be read from the file gamefile. New moves will be appended to the 
  gamefile. To undo a move: quit the program; edit the gamefile and 
  restart the program with 'gwd -GameTimeUsed xx white gamefile', where
  xx stands for the time (in minutes) used sofar.
black gamefile
  Same for black.

gen
  Generates endgame databases. Which endgame databases to generate is
  read from the file 'endgame.dat'. To generate for example all
  3 piece endgame databases, this file should contain:
X X 0
O X 0
X O 0
O O 0
XX X 1
XX O 1
XO X 1
XO O 1
OO X 1
OO O 1
X XX 1
O XX 1
X XO 1
O XO 1
X OO 1
O OO 1
  A '0' indicates that the endgame database is already generated,
  a '1' indicates that it should be generated.
  You have to generate the endgame databases at least twice to make 
  sure that transpositions to other endgames are handled correctly. So:

  a.out gen >out2
  do
    mv out2 out1
    a.out gen >out2
  until out1=out2

  If you have enough computer memory and time, you can also generate 
  higher endgame databases. Do not forget to set ENDGAME_BITS to a 
  higher value and to change the (if (WTOT + BTOT) > 3) in
  set_endgame_pointer.

endgame endgamefile
  Reads endgame positions and the colour to move from the file endgamefile
  and prints the minimax variation.
  Try 'gwd endgame endgame.txt' for an example.

try
  GWD has a neural network based parameter optimizer. 
  It works like this (see also Van Tiggelen, ICCA journal Volume 14,
  no. 3 (1991) pp. 115-118).
  You choose a number of parameters sets for your evaluation function,
  and solve a number of problems with these parameter sets, e.g.
  1 2 3 4 20%
  2 1 3 4 10%
  1 2 4 3 15%.
  You then train a neural network which has as input neurons the number of
  parameters of your evaluation function, and as output the 
  percentage of problems solved. Then you ask the neural network:
  'How can I get 90%'. The neural network tells you: try 4 3 2 1.
  With these parameters, you solve the problems again. Alas, you find 
  that 4 3 2 1 gives 5%, not 90%! This is because the neural network
  is not yet a good model for your evaluation function parameter 
  dependence. But you can still add this result to the training set and
  train the neural network again and ask it how to get 90% etc. etc.
  Now this part of the code depends heavily on routines from Numerical
  Recipes in C, which are !@#$%^ copyrighted (This really puts a blame 
  on this outstanding book), so I have to write these routines myself.
  (that is read the references, study the algorithms, check if PD anything
  is available (fortunately, there is), if not implement it in C,
  debug it etc. etc). This rewrite will take some time, so I have disabled
  this feature in the current version (it will be included in the 
  next version) and replaced it by the option 'try'. This option
  will read from the file "init.txt" a number of parameter sets,
  solve a number of problems on the file "opt.txt" with these sets and
  output the results to the file "results.txt".
  E.g. the file "init.txt" could contain (only parameter sets with
  negative percentages solved are read. Parameter sets with positive
  percentages are skipped)
  -1.0 1 2 3 4
  -1.0 2 1 3 4
  -1.0 1 2 4 3
  And after the run the file "results.txt" contains
  0.20 1 2 3 4 (i.e. 20%)
  0.10 2 1 3 4
  0.15 1 2 4 3

BUGS
  Please report any bugs and questions to wiesenekker@sara.nl.
  Remember: this distribution is primarily meant to provide you 
  with the source code for a draugths program, not with user-friendly,
  strong draugths program.
