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.
Eugene
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.