Threaded Chess

Dave Hein

I wrote a chess program that uses multiple cogs to evaluate moves. The main cog generates a list of moves, and then each cog gets moves from the list and looks up to four moves ahead to determine the value of the move. The program is written in C, and it uses pthreads to run the additional cogs. On the Prop, the program can run 5 pthreads along with the main thread. The main limitation is hub memory since each thread requires about 1.5K of memory to evaluate four moves deep. The threaded version runs about 5 times faster than the single-threaded version. At a depth of 4 moves, it takes about 1 to 3 minutes per move. In the single-threaded mode it would take 5 to 15 minutes per move.

The program can also be compiled to run on a PC. On a PC I use 1 pthread, which works well for a dual-core x86 processor, and runs about twice as fast as the single-threaded version. The PC also allows running 5 levels deep.

The program can be built and run under SimpleIDE. Moves are entered as "d2-d4". Castling is indicated by entering the move for the king. Pawn promotion is always to a queen. I haven't implemented all the rules for a stalemate. The program currently ends the game in a stalemate after 200 moves.

Heater.

Well done. Is that then six cogs looking for moves?
Looks like my Propeller is going to trounce me and I'll end up throwing the whole kit out the window. Thanks a bunch:)

Dave Hein

Yes, there are six cogs looking for moves. The main cog generates the list of moves, and then all six cogs read moves from the list and evaluate them. I use a lock to prevent cogs from fighting over the same move. I originally tried using a mutex lock, but there seems to be a problem with that.

Try level 1. That's pretty easy to beat. The prop will gladly capture a pawn with it's queen not realizing that it could lose it's queen on the next move. Level 2 is more challenging. I've beaten it most of the time at that level, except for a few times when I wasn't really paying attention. I haven't won yet at level 3, but I haven't played too many games at that level yet. Level 4 should be a real challenge, and level 5 on a PC might be tough to beat. However, it does do some silly things at the end game where it randomly moves the king around without moving pawns that could eventually be promoted to queens.

KeithE

Do you have any form of transposition tables? I've thought about trying to write a chess engine, but never did anything about it other than putting a Belle style move generator into an FPGA at one point. It might be fun to have the prop compete with dedicated chess computers if that could be automated. Or perhaps extend the rules to include not just time, but power consumption.

I also wonder if the prop could be used to implement something like this autosensory board (expired? patent) - http://www.google.com/patents/US5082286

For anyone wanting to look into chess programming, this old thesis might be of interest - http://marcelk.net/thesis/marcelk-thesis.pdf

Totally off topic but a while back you were looking at Pico C. Did you try running that on the propeller? Any idea if it would fit? It might be a nice learning tool for people. If it makes any sense we could start a new thread.

Dave Hein

I'm not familiar with transposition tables, but I looked it up, and it appears to be a method that stores the results of previous moves in a hash table. That would seem to take a lot of memory. I'm currently running with a margin of around 100 bytes in the thread stacks. I'm actually monitoring the remaining stack space after each move to ensure that I haven't run out of space in the stacks. So I don't think transposition tables would work with the Prop. It might be useful for the PC version.

One thing I haven't done yet is to implement alpha-beta cutoff. This could speed things up by an order of magnitude or more, and it might allow me to go another level deeper. As I was developing the program I printed out the number of moves that were being evaluated, and it would do something on the order of 100 million evaluations per move when going 5 levels deep.

I briefly looked at Pico C about 9 months ago. I got it running on the Prop in XMMC mode. I'll post the source code and makefile in another thread tonight if I can get it running again.

David Betz

This is very cool. It should be able to go even deeper on P2 since it has 126k of hub memory. Probably can get all 8 COGs running too!

jazzed

Great project Dave. Looking forward to trying this.

JonnyMac

I'm not a chess player but am interested in learning how to use C with the Propeller so I enjoy scanning programs from expert programmers. This line made me laugh:

stacks[i][j] = 0xdeadbeef;

Nicely played, sir.

Dave Hein

I pre-filled the stacks with a value that wouldn't normally be used so I can determine their maximum levels later on. I like to use hex numbers that spell something like 0xfeedface or 0xBADF00D for magic words.

I've tested level 3, and I was able to beat it by trading pieces until we were mostly left with pawns. I was then able to promote a pawn to a queen without much resistance from the program. Actually, I decided to force it into a stalemate instead of going for the win, and I found that I don't terminate the game properly. I'll have to fix that.

Now it's time to try level 4.

Heater.

0xdeadbeef goes back a long way in computer history to the Amiga and before. It was (is) a common "sentinel" marking the end of memory areas, arrays, stacks and so on.

But, slaps head, I have never seen it written in C before. That 0x as in ox as in beef connection never occured to me.

It shows up nicely if you only have a seven segment display for the user interface, dEAdbEEF, as in my old home made 6809 board.

Tor

IBM used that too..
http://www.urbandictionary.com/define.php?term=0xDEADBEEF

-Tor

KeithE

I heard a rumor that a certain company spun a chip because an engineer put 0xdeadbabe onto a bus under certain circumstances. But searching for that constant it appears that it's being used in some software.

Anyways, if you want some propeller chess competition to see how your program evolves I found that u-Max will build on a Quickstart board. Just reduce HASHSIZE for memory size, and other things for speed. (It's slow even on an x86 with the defaults.) I don't know how difficult it would be to get tournaments going. Too bad you probably can't fit it onto the same propeller chip as your program ;-)

http://home.hccnet.nl/h.g.muller/maximax.txt (make sure to look at http://home.hccnet.nl/h.g.muller/max-src2.html as well)

Have you ever visited http://talkchess.com? Some top chess programmers hang out there. Most are interested in very high performance multiprocessor systems.

Rayman

Nice looking chess program Dave. Thanks for posting it.

Keith, micro-max looks interesting. Don't know why they are trying to reduce the number of characters though.... Reminds me of Toledo chess a bit.

Dave's looks a lot easier to decipher... License is better too...

jazzed

KeithE wrote: »

Anyways, if you want some propeller chess competition to see how your program evolves I found that u-Max will build on a Quickstart board. Just reduce HASHSIZE for memory size, and other things for speed. (It's slow even on an x86 with the defaults.) I don't know how difficult it would be to get tournaments going.

Interesting idea.

It shouldn't be too hard to communicate with two terminals or programs and translate the commands from one program to another using a script like tcl/expect.

KeithE

Since Dave has this running on PCs, he can probably do a lot of debugging and play testing there. And he could get other people that are obsessed by computer chess but don't care about Propellers to run it as well. That is a great feature to have. I wasn't really thinking straight before. I guess that testing on the propeller could happen later. It probably can't be avoided for multiple reasons. (e.g. Threading bugs, time management,...) It all depends on how much time someone would want to spend on it.