Author: Anthony Cozzie
Date: 09:33:58 09/18/03
Go up one level in this thread
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. 1. NPS will be _extreme_. I would predict such a program could search over 50 million positions/second. Make_move is trivial: no attack tables, no castling flags, etc. The program is tiny, so *everything* is in L1, etc. A piece list & a 0x88 board should be lightning fast. For example, make_move just looks like: board[f] = board[i]; board[i] = 0; wf |= Rank(i) == 7; bf |= Rank(i) == 2; which is like 5 cycles, even on a PIV. Move generation is almost as simple. 2. Branch factor is reaonably small: Probably 8-10 or so on average. 3. A transposition table will help you out a LOT -- both with move ordering and pruning -- and be fairly easy to implement as well. 4. a few simple "interior node recognizers" will help a lot: If(white has pawn on 7th & white's turn) -> white wins If(White has pawn on 7th & black's turn & black doesn't have pawn on 2nd) -> white wins Those two would probably reduce tree size by a factor of 10 or more, and more complex ones can be done as well. anthony
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.