Author: Robert Hyatt
Date: 13:43:32 02/20/99
Go up one level in this thread
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...
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.