Author: Robert Hyatt
Date: 22:16:06 02/20/99
Go up one level in this thread
On February 20, 1999 at 17:03:02, Eugene Nalimov wrote: >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... > >You must take into account that 8080 was *slow* (it wasn't even >the geniume 8080, it was Soviet copy of it - KR580IK80A). I don't >remember its clock speed, but must be something like 2MHz, with >average instruction taking at least 4 ticks. So, 500K instructions >per second (actually less), and those instructions were mostly 8-bit. > >My book stored at least 6k moves. Assuming that I wanted to get >a move from the book in less than one second, and assuming that >all other book search stuff will take 0 instructions, move >generator must be able to finish its work in ~80 instructions. >Personally I could not write such a generator... > >Of course, Gameboy's processor can be much faster. But Gameboy >(BTW, what is it?) aslo has a plently of ROM, so relation >(CPU speed) / (book size) must be roughly the same. > >Eugene I remember. I programmed both the 8080 from Intel, then Zilog's replacement (the z80). I still have a z80 in my office, in the electronic chess board I built long ago (running at 4mhz).
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.