Author: Edward Seid
Date: 08:35:29 09/28/03
I've finished my first chess program :) It attempts to 'solve' the Pawn Game using brute force MiniMax (implemented as NegaMax). Starting from the root node, it traverses the entire game tree and evaluates every terminal position. Currently, the evaluation function only scores true terminal positions (a pawn on the 7th, stalemate-win, or stalemate-draw). I should note that this is the most inefficient way to do things. The next step is to add alpha-beta, then move ordering (move advanced pawns first, then captures first), then a more advanced evaluation function to assess unstoppable passers. If I ever figure out hashing, I'll add transposition tables which I think should help out a lot due to the symmetry of a full 8 vs 8 Pawn Game. To recap the rules of the Pawn Game, a game is won if 1- a pawn reaches the last rank (in reality, a pawn on the 7th rank is enough to ensure a win), 2- capture all of opponent's pawns, or 3- 'stalemate' the opponent, while having at least one legal move left for yourself. Here are a few test positions and my results. [D]8/6p1/3p4/8/3P2P1/6P1/8/8 w - - This position is actually illegal, but useful for testing the correctness of the evaluation function, node count and assessment of the stalemate positions. Eval: White Wins Node Count: 13 [D]8/6pp/8/8/8/8/6PP/8 w - - Eval: Black Wins Node Count: 26,166 [D]8/6pp/8/8/8/8/5P1P/8 w - - Eval: White Wins Node Count: 85,570 [D]8/5p1p/8/8/8/8/5PPP/8 w - - Eval: White Wins Node Count: 1,111,796 [D]8/6pp/8/8/8/8/5PPP/8 w - - Eval: White Wins Node Count: 33,436,418 [D]8/5ppp/8/8/8/8/5PPP/8 w - - Eval: Draw Node Count: 4,584,150,608 [D]8/pp4pp/8/8/8/8/PP4PP/8 w - - Eval: ??? Node Count: ??? This position ran for 14 hours on my P4/3.06 GHz notebook without finishing. As I don't want to burn out the flimsy fan that typically comes with notebook computers, I halted the test. I hope to solve this in a reasonable time when I add alpha-beta pruning. So that's the status of my project now. I'm going to polish up the code a bit, then proceed to implement alpha-beta pruning. Anyone interested in a copy of my console program written in VB.NET (.NET Framework required), feel free to send an email.
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.