Author: Uri Blass
Date: 08:44:41 09/18/03
Go up one level in this thread
On September 18, 2003 at 11:25:01, Ricardo Gibert 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) > > >Unless I've suffered from a brain fart, a 42 ply game is impossible, while a 41 >ply game is trivial to construct. You may be right about logical game but when both sides do mistakes it is possible to construct longer game 1. a3 a6 2. b3 b6 3. c3 c6 4. d3 d6 5. e3 e6 6. f3 f6 7. g3 g6 8. h3 h6 9. a4 a5 10. b4 b5 11. c4 c5 12. d4 d5 13. e4 e5 14. f4 f5 15. g4 g5 16. h4 h5 17. hxg5 hxg4 18. exf5 exf4 19. dxc5 dxc4 20. bxa5 bxa4 21. a6 a3 22. c6 c3 23. f6 f3 24. g6 g3 25. a7 a2 26. c7 c2 27. g7 g2 28.f7 f2 29.a1Q 57 plies of course evaluation can detect unstoppable passed pawns so if you detect it by evaluation the game is clearly shorter and I do not believe that you can get even 40 plies and after 20 plies the branching factor becomes very small because all the move except 1 or 2 may be detected as losing by evaluation so I guess that it is practically solvable even without hash tables. I guess that the first 20 plies may take 3^20 nodes and the last plies may take not much more than it Uri
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.