howdy all, I''m thinking of implimenting a checkers game with the computer making it''s moves based on the negamax variation of the min-max algorithm. I have a decent idea of how everything would work, but my question is this: are consumer pc''s powerful enough and with enough memory to build the entire tree? consider the minimum pc would be an 800 mghz w/256 MB of ram. would this be plausible? thanks for any insight. Joe My Homepage Freeservers.com sucks. Angelfire.lycos.com is cool.

No, you can''t come even close to building the entire tree. And since most of the time none of the nodes you can search are clear victories, you''ll have to create a score for how good a position is, so if the program cannot find a victory by looking ahead, at least it tries to improve his score on the table.

Currently it would not be possible to store checkers (or most games) from start to end.

You wouldnt have enough RAM + HD space, and the processor wouldn''t be fast enough to handle the calculations within your life time.

Still, there''s nothing wrong with looking ahead 4-8 moves and taking the best one.

good luck,
Will

You may want to take a look at Chinook: http://www.cs.ualberta.ca/~chinook/ (which was at one time the best checkers playing program available. current desktop programs claim to be better now, which is very possible) This URL: http://www.cs.ualberta.ca/~chinook/databases/total.php shows the total number of positions - 500,995,484,682,338,672,639 - I doubt you could make a tree that big with 800 MHz with 256 MB of RAM.

I programmed a checkers playing program a while ago in DOS (not sure if it works on today''s machines) that you may want to check out: http://www.jasondoucette.com/ai.html, but there''s no source code, and I didn''t use hash tables making its play rather poor. It was programmed very quickly for a simple univeristy course, which did not even require something this complicated. I wish I had time to make it properly... maybe someday.

Jason Doucette
www.jasondoucette.com