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.