Computer Chess Club Archives


Search

Terms

Messages

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

Author: Vincent Diepeveen

Date: 16:02:10 02/21/99

Go up one level in this thread


On February 20, 1999 at 16:43:32, Robert Hyatt wrote:

>On February 20, 1999 at 01:30:48, Eugene Nalimov wrote:
>
>>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.
>>
>>Eugene
>
>
>
>by far the easiest way to store opening book moves in a small program is
>this:  take your move generator and debug it carefully, so that for the
>same position, you _always_ get the same set of moves (legal or psuedo-legal
>doesn't matter here) in the exact same order.  Since no position can have
>more than 256 moves, just store the 'index' of the move.  Then to get the
>book move, you generate the complete move list, and index into the list to
>the indicated move...

Correct this is what i do for Diep book.

There are no positions in chess with over 218 possibilities, so
8 bits a move is *very safe* to use.

Further you can use some simple form of repetition (first x bits in
header) which says how many moves this game shares with previous game.

That is if your book is not is gonna get a binary sorted book, but simply
a set of games.

Good luck with it, and keep us informed about the progress of the program!

Vincent Diepeveen










This page took 0 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.