Computer Chess Club Archives




Subject: Re: A seperate process for the chess engine - How do I do this?

Author: Eugene Nalimov

Date: 22:30:48 02/19/99

Go up one level in this thread

On February 19, 1999 at 19:35:14, John Coffey wrote:

>I am using Microsoft Visual C++ with MFC to develope my front end.  I figure
>that I need a way to spawn my engine in a seperate process, and then somehow
>communicate between the two.  Can anyone please tell me how to do this?
>John Coffey

For Win32 multithreading perogramming I'd recommend
  Jeffrey Richter
  Advanced Windows, Third edition
  Microsoft Press
  ISBN 1-57231-548-2

>P.S.  I am learning how to program on the Gameboy.  I might have an opportunity
>to work for company that developes Gameboy games.  I think that it would be fun
>to write a chess program for that platform.  (Getting a publisher to publish it
>is another matter.)    Of course there are some severe limitations:  4 to 8 mhz
>clock speed.  8 K of RAM (so I assume no hash tables.)   No disk access, so I
>would expect a pretty small opening book.  I am trying to figure out a way to
>store an opening book as one byte per move.  I expect that I would have about 1
>megabyte of ROM space, so maybe half of that could be devoted to openings.
>Any suggestions on programming on such a limited platform?

It looks that you still have a lot of space for constants,
so you can use not only 0x88 moves generator (as I did in
8080 program), but even mailobox one.

Maybe you can use part of video RAM? In the same program I
used 4 out of 8 possible colors, so I had exta 8Kb. I stored
enire opening book there.

I don't know, can you use my algorithm or not, but book was
created the following way:
1. There was a compiler that read the text file (not PGN,
   there was no PGN In those times) with the book in the
   memory. It converted each move into 2 bytes "from, to".
2. Then it sorted opeining lines (order can be any, that's
   not important). By sorting it guaranteed that lines with
   common prefix will be near each other.
3. For each line it stored # of moves that are common with
   the previous one. Common moves themselves were removed.
     Simple example: if file contains 6 lines
       e2e4 e7e5 d2d4
       c2c4 e7e5
       e2e4 e7e5 f1g3 g7g6
       e2e4 c7c5
       c2c4 c7c5
       e2e4 e7e5 f1g3 b7b6
     Than at that phase opening book will contain
       <0> e2e4 e7e5 d2d4 <end> <2> f1g3 g7g6 <end>
       <3> b7b6 <end> <1> c7c5 <end> <0> c2c4 e7e5 <end>
       <1> c7c5 <end>
   At that moment I also built table of the N most common
   moves (used for book compression). In my case N was 160.
   Please note that table must be built here, not on the
   input book, as distribution of moves had changed.
4. After that you can compress the book. Access to it always
   will be strictly linear, so you can use Huffman encoding.
   Or use some variation of my schema (8080 is not very good
   in bit manipulation, so I use 8-bit bytes):
   - byte either is "from" square, in that case it has value
     0..63, and it is followed by "to" square.
   - it can be "beginning of the next line", if it value is
     64..95. In that case (value - 64) is # of moves common
     with previous line (that mean that if there are more than
     31 common moves, you'd have to store moves starting from
     32nd in the second line, too).
   - or byte can be in the range 96..255. In that case it was
     used to index the constant table of the most common moves
     that was built in step 3.

Book is ready. How you search move there:

1. Search was always linear - that was not a problem for me, as
   even 8080 easily could do such search in a fraction of second,
   as book was completely in memory.
2. Program decoded next line and stored it as the array of 2-bytes
   integers (from, to).
3. If there was direct match - first N moves in the line were equal
   to the moves played so far - that mean that we can take move N+1
   from the line and store it as one of the candidates.
4. If there was no direct match, maybe there was a transposition?
   Do a quick check - perform XOR of first N+1 moves from the line
   with N moves from the actual game. If result is legal move (there
   is our piece on "from" square, and it can move to "to" square),
   perform long check - for each move from the line check, was it
   made in the real game, or maybe it is our "candidate" move? Long
   check is O(N**2) when implemented naively, but quick check almost
   always cuts wrong matches.
     Example: let's assume that line is
       e2e4 e7e5 g2g3
     And actual game is
       g2g3 e7e5
     In that case our XOR will produce
       e2e4 XOR e7e5 XOR g2g3 XOR g2g3 XOR e7e5
     Almost each move will participate twice - one time from the
     the line, and one time from the actual game, so that moves
     will "annihilate" each other. Result of the XOR will be "e2e4",
     as it alone has no matching. It's legal move, so we have to
     perform long check.
5. Of course it's possible to make some speedup. If current line
   did not match, and nect line has with it common prefix that is
   longer than actual # of moves, it's not necessary to try it.
   It's not necessary even to decode it - you can just skip all
   the bytes while you'll find beginning of the line woth shorter
   common prefix.
6. At the end of the scan you'll have list of the candidate moves.
   I just made the random one.
7. I think I really made 2 passes over the opening book - first
   searched for direct matches, second for transposition. This way
   I guaranteed that program will not find transposition in the
   lopsided opening. But here I'm not sure...

I don't know if that will be really helpful - you can use 80
times more space for the opening book than I had. Also I doubt
you'll hand-edit opening book.


This page took 0.22 seconds to execute

Last modified: Thu, 15 Apr 21 08:11:13 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.