Author: Guido
Date: 03:22:42 12/30/00
Go up one level in this thread
On December 29, 2000 at 11:46:05, Steven J. Edwards wrote: >Briefly, I have calculated the number of distinct positions after N ply for N >equals zero upto nine. Can someone extend this series, or has anyone already >done so? > >1,20,400,5362,72078,822518,9417683 > >See: > >http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=057745 > >-- Steven > >chessnotation@earthlink.net I was interested in this problem some years ago, but I tried only for 8x8 checkers and not for chess. I found that for checkers the total number of distinct positions, i.e. the sum of the series, with 12+12 pieces was 9697697 + 1 (initial position) and that the maximum number of plies without captures or promotions was 65! For this computation I developed an algorithm to add new positions to the list (IMHO it's necessary to maintain a list of positions!) and in the same time to maintain an ordered list. This is necessary in order to check and eliminate duplicated positions finding them by binary search, as CPU time and memory are strong constraints in this problem. Duplication of positions is also the (only?) principal way of pruning the tree. Chess has the disadvantage that capture is not obliged and that the squares are 64 and not 32, so the number of positions must be very high. It would be interesting to try with a number of plies > 9 because the series growths rapidly at the beginning but at a certain number of plies must start to decrease until zero. When number of positions starts to decrease it would be possible (surely not easy!) to try extrapolating the sum of the series and the maximum number of plies, but I fear that computers don't have at present sufficient memory for this. Regards Guido
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.