Author: Tim Foden
Date: 14:11:47 09/28/03
Go up one level in this thread
On September 28, 2003 at 11:35:29, Edward Seid wrote:
>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
GLC (pawngame version) agrees that white wins...
3 0.000 +Mate02 19 g5 g6 2. d5
>[D]8/6pp/8/8/8/8/6PP/8 w - -
>Eval: Black Wins
>Node Count: 26,166
GLC agrees...
10 0.010 -Mate05 1089 h3 h6 2. g3 g6 3. h4 h5 4. g4 hxg4 5. h5 gxh5
>[D]8/6pp/8/8/8/8/5P1P/8 w - -
>Eval: White Wins
>Node Count: 85,570
GLC disagrees on this one...
12 0.010 -Mate06 1309 f3 g5 2. h3 h6 3. h4 gxh4 4. f4 h5 5. f5 h3 6. f6
h2
Are you sure you got the en-passant rules correct?
>[D]8/5p1p/8/8/8/8/5PPP/8 w - -
>Eval: White Wins
>Node Count: 1,111,796
GLC agrees...
7 0.000 +Mate04 697 g4 h6 2. f4 f6 3. f5 h5 4. gxh5
>[D]8/6pp/8/8/8/8/5PPP/8 w - -
>Eval: White Wins
>Node Count: 33,436,418
GLC agrees...
7 0.000 +Mate04 977 f4 h5 2. h4 g6 3. g3 g5 4. fxg5
>[D]8/5ppp/8/8/8/8/5PPP/8 w - -
>Eval: Draw
>Node Count: 4,584,150,608
GLC agrees...
9 0.000 +0.000 3625 f4 f5 2. h3 h6 3. g4 g6 4. gxf5 gxf5 5. h4 h5
>[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.
GLC thinks black wins here...
19 0.140 -Mate09 131218 a3 b5 2. g3 g6 3. h3 a5 4. a4 bxa4 5. g4 g5 6. h4
gxh4 7. b3 axb3 8. g5 h5 9. gxh6 b2
Also note this post from Johan de Koning where he thinks he may have a solution
from the initial position: http://www.talkchess.com/forums/1/message.html?317981
Cheers, Tim.
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.