Author: Tony Werten
Date: 08:10:40 09/18/03
Go up one level in this thread
On September 18, 2003 at 11:02:38, Tony Werten wrote: >On September 18, 2003 at 10:32:44, Omid David Tabibi wrote: > >>On September 18, 2003 at 10:02:33, Edward Seid wrote: >> >>>I'm learning how to program by reading Deitel's Visual Basic.NET How to Program. >>> I'm eager to try out my new skills on a chess-related project. >>> >>>The Pawn Game - as presented by GM Lev Alburt in Comprehensive Chess Course, Vol >>>1 >>> >>>[D]8/pppppppp/8/8/8/8/PPPPPPPP/8 w - - 0 0 >>> >>>The game is won by: >>>1- capturing all of the opponent's pawns >>>2- reaching the last rank first >>>3- 'stalemating' the opponent, while still having at least one move for yourself >>> >>>The game is drawn if: >>>1- both sides' pawns are blocked so that neither side can make any moves >>> >>>The programming exercise I've assigned to myself it to try to solve this game >>>using brute-force minimax. My question to you... can this game be solved on >>>today's typical desktop computer using brute-force? >>> >>>I've been thinking about this and have made the following observations: >>>1- while classical chess has a branching factor of around 30, the Pawn Game >>>branching factor is 16 in the initial position, and around 8 in the >>>'middlegame', and goes down with each capture. >>>2- the longest 'game' is certainly less than 81 ply, and is probably around >>>60-65 (81 ply is calculated by the impossible scenario of each side taking 40 >>>ply each to march all pawns to the 7th rank + 1 ply to promote) >>> >>>I'm not planning to use anything fancy like hashtables or board rotation. I'd >>>be happy if I'm successful in coding a 10x12 board representation (practice for >>>writing a classical chess engine in the future), a valid pawn move generator, >>>and a correct implementation of the minimax algorithm. >>> >>>I'm very curious what the solution to this game is. Is it a win/loss/draw for >>>White? Of the 16 possible White moves, which ones win/lose/draw? How long is >>>the longest game? How long is the shortest game? What is the distribution of >>>wins amongst the 3 methods of winning? >>> >>>Any thoughts or suggestions are appreciated. >> >>The branching factor is at most 8 (initial position) and in the 'middlegame' >>about 4. It seems to me that the average game would be no more than 32 moves, >>and I think 50 would be a realistic upper bound. >> >>So, assuming a branching factor of 4, and game length of 50 plies, there are >>about 4 ^ 50 = 1267650600228229401496703205376 positions to search. Assuming you >>can search 100 million positions per second, it will take you about >>401969368413314 _years_ to finish the computation! > >Your off by a factor of a couple of billion since there are only >29019905518636890 possible different positions. Sorry, that's only the 16 pawns, we need 15, 14 etc as wel so 43090162739794170 positions. Tony > >At most a little less than 10 years of computation. (Pure minimax that is) > >Tony > >> >>However, there will be a huge hash table hit rate (about 99% I guess), and you >>can also benefit from many symmetrical positions (which arise by mirroring >>another position). So, I think this position is solvable by brute force. Good >>luck!
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.