|
Main
Date: 05 Sep 2006 10:26:07
From: Full Decent
Subject: Position upper bound 169 bits WITH PROOF
|
Hello, I have not found any proofs for the upper bound on the number of chess positions, so here is mine, clocking in at 169 bits. Will Entriken - 2006 Encoding chess positions with about 164 bits. This paper describes how to encode any legal chess position in less than 169 bits. It appears that this approach has not been considered, so I am publishing it. ==Denote the armies== Each player has an army that may be written as : <- A - > <- B -> K P P P P X X X X Q R R N N B B Where - X may be one of [QRNB] - A + B <= 8 - Any peice starting with X is optional We will be looping through every possible combination of each players' armies. While doing this, we will keep a note of the following for each army: - A = The number of pawns (since pawns can only be placed on the 8x6 rectangle) - S = The size of the army (to determine the number of empty squares) - P = The product of the factorial of the number of each type of piece (how indistinguishable is the set?) ==Placement== For any two armies, we have [A, S, P, a, s, p] and are able to calculate how many ways those pieces can be placed on the board. This number is: 48! * (64-A-a)! / (48-A-a)! / (64-S-s)! / P / p. 48! (64-A-a)! --------- * --------- (48-A-a)! (64-S-s)! --------------------- P * p ==Results== Possible positions: 23937533792747905898433845980097921846050276105440 log_2: 164.033 log_10: 49.379 Therefore, given a chess position, this method can assign a number between 1 and 239...440 to it. This is reversable as well. ==Extras== I did not count positions multiple times when it is ambiguous whether any castling is possible. Also, certain positions may have up to 5 en passantable pawns. These ineficiencies cost an extra: Possible positions: 24 (factor) log_2: 4.584 log_10: 1.380 White is always to act. If black is to act, invert the board. Those positions are the same. ==Conclusion== Therefore we now have a fast, reversible way to encode a position into 169 bits and a mathematically proven upper bound on the number of chess positions. ==Appendix== Thjis is the counting program I used. It requires the GNU GMP library and compiles with gcc -o ub -lgmp ub.c #include <stdlib.h > #include <stdio.h > #include <gmp.h > int fact (int i) { return (i<=1) ? 1 : i*fact(i-1); } int main() { int base_army[5] = {0,1,2,2,2}; /* Armies attainable without pawns or promotion */ int army[5]={0}; /* PAWNS, QUEENS, ROOKS, BISHOPS, KNIGHTS */ int ab; /* Number of pawns + promoted pieces */ int s; /* Size of the army */ int p; /* Prod(Fact(Count(each peice))) */ int ARMY[5]={0}; /* ... and for the other player */ int AB; int S; int P; int i; mpz_t facts[65]; /* precompute fact(0..64) */ mpz_t total; mpz_t current; mpz_init(total); mpz_init(current); for(i=0; i<=64; i++) { mpz_init(facts[i]); mpz_fac_ui(facts[i], i); } for(army[0]=0; army[0]<=8; army[0]++) for(army[1]=0; army[1]<=9; army[1]++) for(army[2]=0; army[2]<=10; army[2]++) { for(army[3]=0; army[3]<=10; army[3]++) for(army[4]=0; army[4]<=10; army[4]++) { ab = 0; s = 1; /* Count the King */ p = 1; if (army[0]+army[1]+army[2]+army[3]+army[4] > 16) continue; /* Quick impossible check */ for (i=0; i<5; i++) { if (army[i] > base_army[i]) ab += army[i] - base_army[i]; } if (ab > 8) continue; /* Impossible army */ for (i=0; i<5; i++) { s += army[i]; p *= fact(army[i]); } for(ARMY[0]=0; ARMY[0]<=8; ARMY[0]++) for(ARMY[1]=0; ARMY[1]<=9; ARMY[1]++) for(ARMY[2]=0; ARMY[2]<=10; ARMY[2]++) for(ARMY[3]=0; ARMY[3]<=10; ARMY[3]++) for(ARMY[4]=0; ARMY[4]<=10; ARMY[4]++) { AB = 0; S = 1; P = 1; if (ARMY[0]+ARMY[1]+ARMY[2]+ARMY[3]+ARMY[4] > 16) continue; for (i=0; i<5; i++) { if (ARMY[i] > base_army[i]) AB += ARMY[i] - base_army[i]; } if (AB > 8) continue; /* Impossible army */ for (i=0; i<5; i++) { S += ARMY[i]; P *= fact(ARMY[i]); } /* printf("army[]=%d%d%d%d%d -- ", army[0],army[1],army[2],army[3],army[4]); printf("ARMY[]=%d%d%d%d%d -- ", ARMY[0],ARMY[1],ARMY[2],ARMY[3],ARMY[4]); printf("a=%d, s=%d, p=%d\tA=%d, S=%d, P=%d\n", army[0], s, p, ARMY[0], S, P); */ mpz_set_ui(current, 1); mpz_mul(current, current, facts[48]); mpz_divexact(current, current, facts[48 - army[0] - ARMY[0]]); mpz_mul(current, current, facts[64 - army[0] - ARMY[0]]); mpz_divexact(current, current, facts[64 - S - s]); mpz_divexact_ui(current, current, P); mpz_divexact_ui(current, current, p); mpz_add(total, total, current); } } printf("%d/990\n", army[0]*10*11 + army[1]*11 + army[2]); mpz_out_str(stdout, 10, total); puts(""); } mpz_out_str(stdout, 10, total); puts(""); return 0; }
|
|
|
Date: 16 Sep 2006 09:05:36
From: Full Decent
Subject: Re: Position upper bound 169 bits WITH PROOF
|
Anders Thulin wrote: > Full Decent wrote: > > Hello, I have not found any proofs for the upper bound on the number of > > chess positions, > > Published in some old issue of ICCA, I think. 1991? > > Those that have been mentioned in the groups seem to end up around 160 bits. > (See old postings), but there have been quite a number of ideas how to > decrease that in various circumstances. > > -- > Anders Thulin ath*algonet.se http://www.algonet.se/~ath I found out that the article you are referring to is in Sept 1996 of ICCA, but I can't find that journal anywhere. Do any of these people claiming 160bits have proof?
|
|
Date: 05 Sep 2006 18:35:04
From: Anders Thulin
Subject: Re: Position upper bound 169 bits WITH PROOF
|
Full Decent wrote: > Hello, I have not found any proofs for the upper bound on the number of > chess positions, Published in some old issue of ICCA, I think. 1991? Those that have been mentioned in the groups seem to end up around 160 bits. (See old postings), but there have been quite a number of ideas how to decrease that in various circumstances. -- Anders Thulin ath*algonet.se http://www.algonet.se/~ath
|
|
Date: 05 Sep 2006 10:45:32
From: Full Decent
Subject: Re: Position upper bound 169 bits WITH PROOF
|
A quick correction, 24 above should be 6*2^4 = 96, adding 2 bits
|
|