Author: Vincent Diepeveen
Date: 07:39:44 09/18/03
Go up one level in this thread
On September 18, 2003 at 10:32:44, Omid David Tabibi wrote: in 10x10 international checkers you also only have a lot of endgames with just 'pawns'. number of average possibilities is 10 there. Napoleon (my draughts program) searched 40 ply fullwidth already years ago with a good hashtable there. I am always amazed by chinook getting such small depths (20 ply at a simple 8x8 checkers board is just 32 squares starting with an endgame of 12 versus 12 men, whereas in 10x10 international checkers there is not only more rules but also more possibilities thanks to having 20 vs 20 men and 50 squares). Perhaps their problem is every line ending in EGTBs too. Now this is even more limited 8 vs 8 at 48 squares with rules directly stopping the search, so this is really peanuts with hashtables. Best regards, Vincent >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! > >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.