Back to this subject again. I have been working on a means of shrinking down the amount of storage required for chess positions. The only stipulation I have is that the position must be a guaranteed mate. In this scheme I developed I store not only the chess positions but castling rights, enpassant, checks,captures, promotions, first move of the pv and ce value. Following is an example of my binary storage method result.
The 52 positions are:
5nQ1/1k6/8/8/8/8/8/2K5 w - - bm Qg7+; ce 32748;
5n1Q/1k6/8/8/8/8/8/2K5 w - - bm Qg7+; ce 32748;
5n2/1k6/7Q/8/8/8/8/2K5 w - - bm Qg7+; ce 32748;
5n2/1k6/6Q1/8/8/8/8/2K5 w - - bm Qg7+; ce 32748;
5n2/1k6/8/6Q1/8/8/8/2K5 w - - bm Qg7+; ce 32748;
5n2/1k6/8/8/6Q1/8/8/2K5 w - - bm Qg7+; ce 32748;
5n2/1k6/8/8/8/6Q1/8/2K5 w - - bm Qg7+; ce 32748;
5n2/1k6/8/8/8/8/8/2K3Q1 w - - bm Qg7+; ce 32748;
5n2/1k6/5Q2/8/8/8/8/2K5 w - - bm Qg7+; ce 32748;
5n2/1k6/8/4Q3/8/8/8/2K5 w - - bm Qg7+; ce 32748;
5n2/1k6/8/8/3Q4/8/8/2K5 w - - bm Qg7+; ce 32748;
5n2/1k6/8/8/8/2Q5/8/2K5 w - - bm Qg7+; ce 32748;
5n2/1k6/8/8/8/8/8/Q1K5 w - - bm Qg7+; ce 32748;
1Qn5/6k1/8/8/8/8/8/5K2 w - - bm Qb7+; ce 32748;
Q1n5/6k1/8/8/8/8/8/5K2 w - - bm Qb7+; ce 32748;
2n5/6k1/Q7/8/8/8/8/5K2 w - - bm Qb7+; ce 32748;
2n5/6k1/1Q6/8/8/8/8/5K2 w - - bm Qb7+; ce 32748;
2n5/6k1/8/1Q6/8/8/8/5K2 w - - bm Qb7+; ce 32748;
2n5/6k1/8/8/1Q6/8/8/5K2 w - - bm Qb7+; ce 32748;
2n5/6k1/8/8/8/1Q6/8/5K2 w - - bm Qb7+; ce 32748;
2n5/6k1/8/8/8/8/8/1Q3K2 w - - bm Qb7+; ce 32748;
2n5/6k1/2Q5/8/8/8/8/5K2 w - - bm Qb7+; ce 32748;
2n5/6k1/8/3Q4/8/8/8/5K2 w - - bm Qb7+; ce 32748;
2n5/6k1/8/8/4Q3/8/8/5K2 w - - bm Qb7+; ce 32748;
2n5/6k1/8/8/8/5Q2/8/5K2 w - - bm Qb7+; ce 32748;
2n5/6k1/8/8/8/8/8/5K1Q w - - bm Qb7+; ce 32748;
2k5/8/8/8/8/8/1K6/5Nq1 b - - bm Qg2+; ce 32748;
2k5/8/8/8/8/8/1K6/5N1q b - - bm Qg2+; ce 32748;
2k5/8/8/8/8/7q/1K6/5N2 b - - bm Qg2+; ce 32748;
2k5/8/8/8/8/6q1/1K6/5N2 b - - bm Qg2+; ce 32748;
2k5/8/8/8/6q1/8/1K6/5N2 b - - bm Qg2+; ce 32748;
2k5/8/8/6q1/8/8/1K6/5N2 b - - bm Qg2+; ce 32748;
2k5/8/6q1/8/8/8/1K6/5N2 b - - bm Qg2+; ce 32748;
2k3q1/8/8/8/8/8/1K6/5N2 b - - bm Qg2+; ce 32748;
2k5/8/8/8/8/5q2/1K6/5N2 b - - bm Qg2+; ce 32748;
2k5/8/8/8/4q3/8/1K6/5N2 b - - bm Qg2+; ce 32748;
2k5/8/8/3q4/8/8/1K6/5N2 b - - bm Qg2+; ce 32748;
2k5/8/2q5/8/8/8/1K6/5N2 b - - bm Qg2+; ce 32748;
q1k5/8/8/8/8/8/1K6/5N2 b - - bm Qg2+; ce 32748;
5k2/8/8/8/8/8/6K1/1qN5 b - - bm Qb2+; ce 32748;
5k2/8/8/8/8/8/6K1/q1N5 b - - bm Qb2+; ce 32748;
5k2/8/8/8/8/q7/6K1/2N5 b - - bm Qb2+; ce 32748;
5k2/8/8/8/8/1q6/6K1/2N5 b - - bm Qb2+; ce 32748;
5k2/8/8/8/1q6/8/6K1/2N5 b - - bm Qb2+; ce 32748;
5k2/8/8/1q6/8/8/6K1/2N5 b - - bm Qb2+; ce 32748;
5k2/8/1q6/8/8/8/6K1/2N5 b - - bm Qb2+; ce 32748;
1q3k2/8/8/8/8/8/6K1/2N5 b - - bm Qb2+; ce 32748;
5k2/8/8/8/8/2q5/6K1/2N5 b - - bm Qb2+; ce 32748;
5k2/8/8/8/3q4/8/6K1/2N5 b - - bm Qb2+; ce 32748;
5k2/8/8/4q3/8/8/6K1/2N5 b - - bm Qb2+; ce 32748;
5k2/8/5q2/8/8/8/6K1/2N5 b - - bm Qb2+; ce 32748;
5k1q/8/8/8/8/8/6K1/2N5 b - - bm Qb2+; ce 32748;
The following binary created only uses 127 continuous bits to store all the above positions.
1101011011110010000000010101111110001110000010001101100001001000001001110000001000000000000010000001111010111101000000000000000
On average thats 2.44 bits/position !!!
In the past some of you were looking at various compression schemes. With my only stipulation of a guaranteed mate whats the best you can do??
Enjoy,
Les
Minimum Storage of these 52 positions
Moderators: hgm, Dann Corbit, Harvey Williamson
-
vb4
- Posts: 163
- Joined: Sat Mar 11, 2006 5:45 am
- Location: NY
-
Zach Wegner
- Posts: 1922
- Joined: Thu Mar 09, 2006 12:51 am
- Location: Earth
Re: Minimum Storage of these 52 positions
I read about this before, and though I didn't say anything, I was quite intrigued. Could you describe the algorithm? Why must the position be a mate?
-
vb4
- Posts: 163
- Joined: Sat Mar 11, 2006 5:45 am
- Location: NY
Re: Minimum Storage of these 52 positions
Hi Zach,
The reason that my utility called Mate Cruncher requires a mate position is the basis as to how my binary method works. Initially I developed a utility called Permutator which took any chess position and was able to generate 3 additonal positions taking advantage of the 4 way rotations. This allowed me to store the original position and with it was able to generate the 3 other positions with just doing some simple math. Once I played around with this utility it came to me that if I worked with a quaranteed mate position not only would I be able to rotate the position 4 ways but was also able to generate what I call sliders. I defined sliders as the following. Take what ever piece is the piece to move to the target square and place that piece on all squares from the target square that can still reach the target square. The thought behind this is if we know that Re5# is a mate then it doesnt matter where that R comes from as long as it can still reach the target square its still a mate. Now it doesnt mean that the moves created is the minimum moves to mate but it still does guarantee a mate. This is how my Mate Cruncher utility works. Now we are able to generate a maximum of 108 slider positions under an ideal scenario and compound that with the 4 way permutations you have an increase factor of approximately 400 new positions for every position you start with.
I have taken this flow one more step and have built a routine that can now take 1 posiiton and generate 1000,s of Avoid move positions from 1 position with the same assumption that the position must be a guaranteed mate position. This work is also finished. Dann Corbit has played with both the Permutator and Mate Cruncher (sliders and avoid moves) and has provided me with some testing with good results so far. In fact part of Mate Cruncher lets you actually put a test position in and see if it can find a solution. Mate Cruncher was developed to generate these new positions and to graphically show you how thigs work.
Here is a little challenge for you that you may enjoy. How many bits would it take you to store the following information. Piece type, square where it is, and the color of the piece? With my binary it takes me only 9 bits per piece! <s>
Beleive it or not I can introduce one more multiplier (5x) to this work but there are many complications I would need to work out.
Hope this helps you understand roughly what I am doing and that it provides others with some food for thought.
Take care Zach and if you have any other questions you can either get me here or my email (vb4@prodigy.net)
Les
The reason that my utility called Mate Cruncher requires a mate position is the basis as to how my binary method works. Initially I developed a utility called Permutator which took any chess position and was able to generate 3 additonal positions taking advantage of the 4 way rotations. This allowed me to store the original position and with it was able to generate the 3 other positions with just doing some simple math. Once I played around with this utility it came to me that if I worked with a quaranteed mate position not only would I be able to rotate the position 4 ways but was also able to generate what I call sliders. I defined sliders as the following. Take what ever piece is the piece to move to the target square and place that piece on all squares from the target square that can still reach the target square. The thought behind this is if we know that Re5# is a mate then it doesnt matter where that R comes from as long as it can still reach the target square its still a mate. Now it doesnt mean that the moves created is the minimum moves to mate but it still does guarantee a mate. This is how my Mate Cruncher utility works. Now we are able to generate a maximum of 108 slider positions under an ideal scenario and compound that with the 4 way permutations you have an increase factor of approximately 400 new positions for every position you start with.
I have taken this flow one more step and have built a routine that can now take 1 posiiton and generate 1000,s of Avoid move positions from 1 position with the same assumption that the position must be a guaranteed mate position. This work is also finished. Dann Corbit has played with both the Permutator and Mate Cruncher (sliders and avoid moves) and has provided me with some testing with good results so far. In fact part of Mate Cruncher lets you actually put a test position in and see if it can find a solution. Mate Cruncher was developed to generate these new positions and to graphically show you how thigs work.
Here is a little challenge for you that you may enjoy. How many bits would it take you to store the following information. Piece type, square where it is, and the color of the piece? With my binary it takes me only 9 bits per piece! <s>
Beleive it or not I can introduce one more multiplier (5x) to this work but there are many complications I would need to work out.
Hope this helps you understand roughly what I am doing and that it provides others with some food for thought.
Take care Zach and if you have any other questions you can either get me here or my email (vb4@prodigy.net)
Les
-
Golem
Re: Minimum Storage of these 52 positions
Color of the piece : 2 possibilities -> 1 bitvb4 wrote:Here is a little challenge for you that you may enjoy. How many bits would it take you to store the following information. Piece type, square where it is, and the color of the piece? With my binary it takes me only 9 bits per piece!
Square of the piece : 64 possibilities -> 6 bits
Piece type : 6 possibilities -> 3 bits
So 10 bits seems to be the minimum for me.
Note that I can exclude some possibilities (for a pawn not being on the first and eighth rank) but if I simply exclude all the possibilities for the pawn, I have 640 possibilities yet (5 pieces (king, queen, rook, knight and bischop) that can be on each of the 64 squares -> 5 * 2 * 64 = 640). It's more than the 512 information you can save with 9 bits.
I really don't believe you can code all those information with only 9 bits... It seems impossible... Can you explain your method ?
-
vb4
- Posts: 163
- Joined: Sat Mar 11, 2006 5:45 am
- Location: NY
Re: Minimum Storage of these 52 positions
Hi Gontran,
To save that extra bit what I do in my binary is the following. The trick is the whatever color is the side to move I keep all those colored pieces on one side of what I call a transition point and all the other color pieces on the other side therefore I dont need to attach the color bit to each and every piece.
Example
Tansition separates white vs black pieces
| |
1 101010111 110011011 001111110 000 010101110 110111111 ..........
To the left of the transition I have 3 pieces (Q on 2,7 K on 3,3 P on 7,6)
To the right of the transition I have 2 pieces (N on 5,6 K on 7,7)
Here it is White to move and there are 3 white pieces (3 sets of nine bits to the left of the transition point [000] ) and then there are 2 pieces after the transition which are black.
Bit 1 tells me what is the side to move (0=black 1-white)
Bit 2 - 4 tells me what piece type (in this case its a queen)
P=001 N=010 B=011 R=100 Q=101 K=110
Bit 5 - 7 tells me the x-coordinate of where the piece is
0=000 to 7=111
Bit 8 - 10 tells me the y-coordinate of where the piece is
0=000 to 7=111
So the above example says you have a White Q on x=2 and y=7
If you have any other questions Gontran give me a shout.
Les
To save that extra bit what I do in my binary is the following. The trick is the whatever color is the side to move I keep all those colored pieces on one side of what I call a transition point and all the other color pieces on the other side therefore I dont need to attach the color bit to each and every piece.
Example
Tansition separates white vs black pieces
| |
1 101010111 110011011 001111110 000 010101110 110111111 ..........
To the left of the transition I have 3 pieces (Q on 2,7 K on 3,3 P on 7,6)
To the right of the transition I have 2 pieces (N on 5,6 K on 7,7)
Here it is White to move and there are 3 white pieces (3 sets of nine bits to the left of the transition point [000] ) and then there are 2 pieces after the transition which are black.
Bit 1 tells me what is the side to move (0=black 1-white)
Bit 2 - 4 tells me what piece type (in this case its a queen)
P=001 N=010 B=011 R=100 Q=101 K=110
Bit 5 - 7 tells me the x-coordinate of where the piece is
0=000 to 7=111
Bit 8 - 10 tells me the y-coordinate of where the piece is
0=000 to 7=111
So the above example says you have a White Q on x=2 and y=7
If you have any other questions Gontran give me a shout.
Les
-
Golem
Re: Minimum Storage of these 52 positions
Hello Les,
Thank you for your explanation, it's cristal clear for me now !
I'm wondering if we can find something better than the way you do it.
Do we have an idea of the theorical minimum bits we need to code any legal chess position (if we can exclude the fact that we have not more than 16 pieces of each color on the board, not more than 8 pawn, 9 queens, 9 rook, etc... and the pawn cannot be on the first and eighth rank...). Maybe we can also use your trick (the transition point) for the type of the piece (so if we have many piece with the same type we don't need to save the type each time) ?
PS : I think this topic can be moved to the programmer forum ?
Thank you for your explanation, it's cristal clear for me now !
I'm wondering if we can find something better than the way you do it.
Do we have an idea of the theorical minimum bits we need to code any legal chess position (if we can exclude the fact that we have not more than 16 pieces of each color on the board, not more than 8 pawn, 9 queens, 9 rook, etc... and the pawn cannot be on the first and eighth rank...). Maybe we can also use your trick (the transition point) for the type of the piece (so if we have many piece with the same type we don't need to save the type each time) ?
PS : I think this topic can be moved to the programmer forum ?