The next text is based on a card trick by magician an mathematician William Fitch Cheney. I don't think it is useable in practice, but hey, maybe someone gets inspired.
Suppose you are building a database containing all 3 white men versus 2 black men positions. Would it be possible to store just the position of four men, and calculate the position and colour of the fifth man?
Trick 0: well, the colour of the fifth man is no problem. In the database there are:
3 whites and 1 black: fifth must be black
2 whites and 2 blacks: fifth is white
The position of the fifth men must be, somehow, retrieved from the order in which the four men are stored. 4 men can be stored in 4!=24 ways. 24 seems to fall short, because there are 46 possible positions for the fifth man. How to overcome this?
Divide the board in 4 quadrants. The top-left and down-right will have 12 fields, the other 2 have 11 fields. Since there are 4 quadrants and 5 pieces, one quadrant will contain at least 2 pieces.
Trick number one: the first ordered piece defines in which quadrant the missing piece is. So if the first stored man is in top-right, the fifth is also in top-right.
Trick number two: a quadrant is just a 5x5 miniboard with 11 or 12 fields. Since there are two possible candidates for the first ordered piece when building the database, choose the one which is less than 7 fields away from the other, reading left to right and when bottom goto top.
Trick number three: when building the database, store the piece-positions of the remaining three pieces in specific order:
LMH=1
LHM=2
MLH=3
HLM=4
MHL=5
HML=6
(L-lowest field, M=middle, H=high)
Wrapping up: you know what colour the fifth piece is (could be a king also), you know in which quadrant it, is and you know it's distance to a known piece.
Storing a 5 piece position by storing only 4 pieces
Re: Storing a 5 piece position by storing only 4 pieces
Hi,steenslag wrote:The next text is based on a card trick by magician an mathematician William Fitch Cheney. I don't think it is useable in practice, but hey, maybe someone gets inspired.
Suppose you are building a database containing all 3 white men versus 2 black men positions. Would it be possible to store just the position of four men, and calculate the position and colour of the fifth man?
Trick 0: well, the colour of the fifth man is no problem. In the database there are:
3 whites and 1 black: fifth must be black
2 whites and 2 blacks: fifth is white
The position of the fifth men must be, somehow, retrieved from the order in which the four men are stored. 4 men can be stored in 4!=24 ways. 24 seems to fall short, because there are 46 possible positions for the fifth man. How to overcome this?
Divide the board in 4 quadrants. The top-left and down-right will have 12 fields, the other 2 have 11 fields. Since there are 4 quadrants and 5 pieces, one quadrant will contain at least 2 pieces.
Trick number one: the first ordered piece defines in which quadrant the missing piece is. So if the first stored man is in top-right, the fifth is also in top-right.
Trick number two: a quadrant is just a 5x5 miniboard with 11 or 12 fields. Since there are two possible candidates for the first ordered piece when building the database, choose the one which is less than 7 fields away from the other, reading left to right and when bottom goto top.
Trick number three: when building the database, store the piece-positions of the remaining three pieces in specific order:
LMH=1
LHM=2
MLH=3
HLM=4
MHL=5
HML=6
(L-lowest field, M=middle, H=high)
Wrapping up: you know what colour the fifth piece is (could be a king also), you know in which quadrant it, is and you know it's distance to a known piece.
Where is the gain?
The number of 3x2 positions is 1,047,473,160. As a consequence, if you can identify a position with 30 bits.
What happens with the approach proposed ?
For storing the position of a piece you need to distinguish a square among 50 and a piece among 4. That means that you have to distinguish a number among 200. In order to store 4 pieces you have to distinguish a number among 200^4 = 1,600,000,000. And you have then to double this number to take into account who is to play. Finally you have to distinguish a number among 3,200,000,000 and you need 32bits for that.
As a consequence, with this approach, you have lost almost 7% of memory.
Gérard
