Reply
 
LinkBack Thread Tools Display Modes
  #1   Report Post  
Old September 5th 06, 06:26 PM posted to rec.games.chess.computer,rec.games.chess.misc
external usenet poster
 
First recorded activity by ChessBanter: Sep 2006
Posts: 6
Default 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; i5; i++)
{
if (army[i] base_army[i]) ab += army[i] -
base_army[i];
}
if (ab 8)
continue; /* Impossible army */

for (i=0; i5; 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; i5; i++)
{
if (ARMY[i] base_army[i]) AB +=
ARMY[i] - base_army[i];
}
if (AB 8)
continue; /* Impossible army */

for (i=0; i5; 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;
}

  #2   Report Post  
Old September 5th 06, 06:45 PM posted to rec.games.chess.computer,rec.games.chess.misc
external usenet poster
 
First recorded activity by ChessBanter: Sep 2006
Posts: 6
Default Position upper bound 169 bits WITH PROOF

A quick correction, 24 above should be 6*2^4 = 96, adding 2 bits

  #3   Report Post  
Old September 5th 06, 07:35 PM posted to rec.games.chess.computer,rec.games.chess.misc
external usenet poster
 
First recorded activity by ChessBanter: Aug 2006
Posts: 157
Default 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

  #4   Report Post  
Old September 16th 06, 05:05 PM posted to rec.games.chess.computer,rec.games.chess.misc
external usenet poster
 
First recorded activity by ChessBanter: Sep 2006
Posts: 6
Default 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?

  #5   Report Post  
Old May 17th 14, 05:38 PM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: May 2014
Posts: 4
Default Position upper bound 169 bits WITH PROOF

On Wednesday, September 6, 2006 3:26:07 AM UTC+10, Full Decent wrote:[i]
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; i5; i++)
{
if (army[i] base_army[i]) ab += army[i] -
base_army[i];
}
if (ab 8)
continue; /* Impossible army */

for (i=0; i5; 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; i5; i++)
{
if (ARMY[i] base_army[i]) AB +=
ARMY[i] - base_army[i];
}
if (AB 8)
continue; /* Impossible army */

for (i=0; i5; i++)
{
S += ARMY[i];
P *= fact(ARMY);
}

/*
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;
}


Actually - I feel if you broke the board into two sets, one of 48 squares and one of 64, you could then use base-n to describe the pieces...
So for the pawns you have 3 states, which are an empty square, a white pawn or a black pawn, so that is 48 to the power of 3, or 110,592 combinations....
For the other 5 types of pieces there are also 2 colors, and empty squares, they can exist on 64 squares, so again it is 64 to the power of 11 (5*2 + the empty square) - this yields 73,786,976,294,838,206,464 states, multiplying the two you get a number which can be stored in 83-bits... my math could be out - but I'd be more inclined to follow this approach...
(this would only be the physical board state, not the castling status, or any other information...)


  #8   Report Post  
Old July 8th 14, 12:22 AM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Jul 2014
Posts: 1
Default Position upper bound 169 bits WITH PROOF

FYI, there is some light discussion on the topic at https://codegolf.stackexchange.com/q...rd-compression that tries approaches used Huffman encoding.

On Sunday, June 1, 2014 10:03:50 AM UTC-4, wrote:
On Wednesday, May 21, 2014 9:41:01 PM UTC+10, Richard Delorme wrote:

Le 17/05/2014 18:38, a �crit :




Actually - I feel if you broke the board into two sets, one of 48




squares and one of 64, you could then use base-n to describe the




pieces... So for the pawns you have 3 states, which are an empty




square, a white pawn or a black pawn, so that is 48 to the power of




3, or 110,592 combinations...








No, this is 3 to the power of 48. But this include too many cases, with




up to 48 black pawns or 48 white pawns.








For the other 5 types of pieces there are also 2 colors, and empty




squares, they can exist on 64 squares, so again it is 64 to the power




of 11 (5*2 + the empty square) - this yields 73,786,976,294,838,206,464




states, multiplying the two you get a number which can be stored in




83-bits... my math could be out - but I'd be more inclined to follow




this approach... (this would only be the physical board state, not the




castling status, or any other information...)








Same here, this is 11 to the power of 64.




Aye I realised my error when I tried to implement, good call, and outstanding post by the O.P.

Reply
Thread Tools
Display Modes

Posting Rules

Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On


Similar Threads
Thread Thread Starter Forum Replies Last Post
Bobby Fischer has been reinstated in the USCF [email protected] rec.games.chess.politics (Chess Politics) 88 September 4th 06 08:02 PM
Bobby Fischer has been reinstated in the USCF [email protected] rec.games.chess.misc (Chess General) 89 September 4th 06 08:02 PM


All times are GMT +1. The time now is 11:28 PM.

Powered by vBulletin® Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
Copyright ©2004-2019 ChessBanter.
The comments are property of their posters.
 

About Us

"It's about Chess"

 

Copyright © 2017