Author: KarinsDad
Date: 12:36:27 03/10/00
Go up one level in this thread
On March 09, 2000 at 11:19:46, Vincent Diepeveen wrote: >Hello, > >[if you react on this posting please send a copy also by email to >diep@xs4all.nl as i don't check CCC regurarly] > >For hashing in 64 bits there are > 2^64 possible outcomes. > >That's not much compared to the number of >positions as estimated in an ICCAJ some time ago: 10^43 >was that outcome. > >Now for a few mathematicians the number of theoretical >positions will be interesting, but not for us all. > >More interesting are different numbers: > - practical 'alfabeta with nullmove' number > - human number of acceptible positions > >So in short, how many positions can i expect that a search of my program >can ever search, including the nonsense positions? > >First i started with a simple experiment. Is it possible to have more >than 16 non-pawn pieces on the board? > >Theoretical: yes >Practical: no, as when there are 2 queens on the board usual already some > captures have been done reducing the number of pieces first. > >For example one leaf seen by DIEP is e4 d5 ed5 c6 dc (lot of different moves) >cb7 and then bxa8Q. So the most obvious 'ALL' nodes are not having 2 queens. >Any position having over 16 pieces can be proven a nonsense or artificial >position in advance. Lines like e4 d5 ed5 c6 dc6 and then capturing further >to queen is not smart to allow. > >Even middlegambits from white side: e4 e5 d4 ed c3 dc3 Bc4 cb2 has bxb2 as >best move. Qd5 is a nonsense move because of bxc1Q > >So there we have perhaps for the alfabeta tree a SINGLE position with >2 queens, but still not over 16 pieces, as we chopped off a piece at c1. > >So far i haven't seen a single interesting over 16 piece position which is >derived from good moves of at least 1 side, without being cutoffed by >nullmove. > >Obvoiusly a fullwidth search will simply search all chess positions. >Nullmove chops off all that nonsense quite drastically (lucky). > >Yet if i start calculating how many chess positions there are, using next >scheme to store a position: > >64 bits 1 = piece 0= no piece > >We can do that for 32 pieces at maximum determining whether >they are a pawn or not a pawn and we already know the number of >pieces on the board, so when we miss a few pawns, then we can >risk having more than 16 pieces anyway: > >32 bits (total 96 now) 1 = pawn 0 = not a pawn >32 bits (total 128 now) 1 = white 0 = black > >We already know what are pawns. What we now need are >at maximum 16 pieces left. We know what pieces are >white. we know what pieces are black, so first we >describe the kings: > >white king first: 3 bits (total 131 bits now) >black king second: 3 bits (total 134 bits now) >So now we have at maximum 14 pieces left with each >as possible value: queen,rook,bishop,knight. We >already know what color it is. So we can >describe that in 2x14 = 28 bits (total 134+28 = 162 bits) You still need side to move (1 bit), castling status per side (2 bits per side) and EP status (1 bit), so 6 more bits (of course, these can be minimized within your schema, but then you increase the complexity of the schema). You also need draw by rep (2 bits just for how many times we've repeated, let alone the actual positions previously found) and 50 move rule stuff (7 bits), but we can ignore these two for now. Total 162 + 6 for side to move/castling/EP = 168 bits. >So we can describe an entire position in 162 bits at >maximum using an extremely simple scheme. > >Note that describing all positions can be done in not >many bits more by using 5 pieces and 5^max pieces, >so a smart mathematician can figure out that we hardly >need more than 162 bits for *any* chess position. > >2^162 = 10^48 > >Now there was already an estimate of 2^43 on the total >number of positions. Yet there is an easier way which is >a lot harder to store though. > >The basic stupidity in all these schemes is that they don't >take into account the limited number of squares that pawns >can be on. > >Let's first do a naive calculation, only for pawns. >There are 48 squares and 8 white pawns and 8 black pawns >at maximum: > >48! / (32!8!8!) = 2.9 * 10^16 > >this number is of course pure nonsense as it includes also white pawns >on a5..h5 and all black pawns at a4..h4, now i guess this is an illegal >to reach position, but many other theoretical perhaps >possible positions which practical never will happen are included. > >Now we can reduce a lot less for the remaining 16 pieces. >However if we have all pawns on the board, then >we have only 48 squares left to put our pieces at. > >If there are less pawns on the board, then the number will be higher, but >the total number of possible positions will be a lot less anyway. > >48! / 32!(2!^6) = 7.3 ^ 10^23 > >If we multiply the 2 numbers then i get to something like 2 * 10^40 > >Now this is already a lot less than 10^43 as put in ICCAJ. > >If i however do a 'human' estimation, then we talk about magnitudes less: >a king of mine can never be at about 48 different squares. i have at most >a few choices in opening/middlegame. Say 20 choices sounds like a fair >number? > >All other squares are nonsense for my king for sure. > >How many positions do we have with all white pieces behind all black pieces? > >In other words: what is the maximum of pieces behind the enemy pieces that >we practical see in games? > >3 perhaps? > >How many white pieces go ever over the 4th rank? > >Quite a number you'll say. Yes! But at most 1 at the time. > >Actually, 10^30 already sounds like a nonsense number in my ears. At best, you could reduce the board by 50% per piece or 2^32. So, 2^168 becomes 2^136 (less then your 10^30). Great!!!! How do we do that? Do we assume that all colors on a given side of the board are the same and hence, we only have to indicate which ones (the "3 perhaps" you mentioned out of ~16 locations) are? Well, that takes up at least 16 bits (~4 bits per piece to indicate which of the ~15 locations it is plus 4 bits to indicate that no more of my pieces are on the opposing side) in order to save 16 bits. e.g. 0101 piece 5 is my color 1010 piece 10 is my color 1110 piece 14 is my color 0000 there are no more pieces of my color on the opposing side You save 0 bits (16-16), assuming that we would not have a position with more than 3 pieces on the opposing side of the board and that there are not more than 15 pieces on the opposing side of the board. Well, this method does not work. Do we have an alternative method? Do we assume that all pawn/pawn column pairs are white/black? What happens when we have a pawn column or a pawn/pawn/pawn column position? Again, no easy answers. What you are effectively attempting to do is prune the number of positions down to some reasonable number found in any reasonable game. Although this may be a good goal, there are no easy programatic ways to do this (at least that I have found and I have been working on the store all possible positions within 160 bits problem for a long time). The other problem is that just when you thought you had them all, some person will set a program to play at a lower setting (with some "personality" flag set to avoid captures) and get into some wierd position you did not think about and the algorithm (and the program) blows up. KarinsDad :) PS. I will send an Email of this response to you when I get home tonight.
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.