Author: Uri Blass
Date: 05:46:33 09/25/03
Go up one level in this thread
On September 25, 2003 at 04:55:52, Tim Foden wrote: >On September 25, 2003 at 03:24:27, Johan de Koning wrote: > >>On September 24, 2003 at 03:34:14, Tim Foden wrote: >>>On September 24, 2003 at 01:58:35, Johan de Koning wrote: >> >>Well, I'm not going to hack more code to create a game playing loop. >>It was a bit stupid of me to create Kingless basics. All that was needed was >>paralyzing the Kings and creating a PG specific search, leaving the interface >>and all the utility code unchanged. > >Yes, this is what I did in GLC. > >>But more importantly, it seems pointless to play this game on an 8x8 board. > >True enough :) > >>The initial position will be solved tomorrow, and a small opening book will >>suffice to win all games. That's assuming White does win, based on the seqence >>sofar: =-=+=+= for symmetrical baseline positions 1 through 7. > >It does seem likely to be the case. > >>>On the 7-7 position, I decided that the lack of left/right symmetry was hurting, >>>so I stopped that too. :) >> >>It is perfectly symmetrical if you disregard the a-file. :-) > >Yes, but I couldn't be bothered to change my hash symmetry code to do it. :) > >>But I don't think symmetry gains much, since the root moves in the "other half" >>spawn small subtrees. Maybe it helps a lot if you apply *all* translations and >>mirrors to the transposition table. > >Yes, this is what I've done. I generate 2 hash keys (horizontally reflected), >and load/store in the transposition table using the lowest valued key. > >In my tests it made nearly a 2x speedup. I guess that you may get clearly more than 2x speedup by better hash. For example your hash can ignore the a file if there are white pawn at a4 black pawn at a5 and no pawns at the b files. There is a lot to gain by hash tables. even without considering the case of irrelevant files because of blocked pawns. A good idea may be to translate the files of the pawns to different files when the following conditions exist: 1)there are no empty connected files except last files. 2)there are always pawns in the a file 3)the set of connected left files is always bigger or equal than the set of the connected right files It is easy to prove that the fibonezy sequence is the right sequence to give the number of possibilities for 1 and 2 when we know the first and the last file (3 can at most reduce the number of possibility to half of them so I will ignore it). let denote f(n) the number of possibility for files with pawns when only files 1-n have pawns and files 1 and file n have to have pawns and no 2 files in a row without pawns. It is easy to see that we have f(1)=1 f(2)=1 f(3)=2 It is easy to see that f(n)=f(n-1)+f(n-2) because f(n-2) is the nmber of possibilities that file 1,n have pawns and file 2 have no pawns(so file 3 needs to have pawns) and f(n-1) is the number of possibility that files 1,2,n have pawns. we get f(4)=3,f(5)=5,f(6)=8,f(7)=13,f(8)=21 1+1+2+3+5+8+13+21=54 so we have only 54 possibilities for files with pawns out of files a-h note also that 54=f(10)-1 so the fibonezy sequence control the number of possibilities and even if we add more files the number of relevant possibilities for files without pawns is f(n+2)-1 This sequence grow exponentialy as n increase but not by factor of 2 (I do not remember the exact formula at this momemt but it has some sqrt in it when the sum of 2 powers of irrational numbers gives rational number). 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.