Thanks Grobe for this....I'm doing what I can to reduce the count thru definition....and maybe (just maybe) taking the # from a TEE count to a 'unique position' count would simply be a multiple...I don't know.
BTW, something I'd like to look into is how Krabbe (?) set the parameters for calc'ing the positions for the first 10 moves (?) and why he abandoned his research....hmmm....
As it pertains to symetries (and rotations), I beleive this to be correct:
As it pertains to symetries (and rotations), I beleive this to be correct:
Every position has one colour change/board swap symetry. Every position with pawns has an additional vertical reflection symetry Every position without pawns has four reflections (vertical, horizontal and also along each diagonal) and four rotationsI have tried to summarize my thoughts on symmetries in a blog post.
It is too lengthy to include it here.
Just one brief observation: not all symmetries you listed are independent. In all there are 8 distinct positions that are essentially different under those transformations. Many subsets of those symmetries are capable of generating all of those 8. In my blog post I developed a system which generates all 8 symmetrical positions from vertical and horizontal mirroring and transponation ( mirroring over the main diagonal of the position matrix ). This is economic because vertical and horizontal mirroring can be used for some specific symmetries and they can be written simply as a matrix multiplication by a certain matrix ( the mirror matrix ) from right or left. Matrix transponation is also an elementary operation. Any rotation which is the integer multiple of 90 degrees can be generated using some combination of these elementary operations and also any combination of such rotations and any type of reflections.
These are the 8 symmetrical positions in my notation ( P is the position matrix, M is the mirror matrix ):
Visualization of symmetric positions:
| 1 | 2 | 2 | 1 | 3 | 4 | 1 | 3 | |||
| 3 | 4 | 4 | 3 | 1 | 2 | 2 | 4 | |||
| 4 | 3 | 2 | 4 | 3 | 1 | 4 | 2 | |||
| 2 | 1 | 1 | 3 | 4 | 2 | 3 | 1 |
In order:
Initial Position Horizontal Reflection Vertical Reflection A1-H8 Reflection
180° Rotation 90° Clockwise Rotation 270° Clockwise Rotation A8-H1 Reflection
In order:
e1 (initial) -> d1, e8, h4, d8, h5, a4, a5
Let's assume that there are 2*10^9 PC-s in the world and they are all high end: having 16 cores operating at 5 GHz ( capable of executing 16*5*10^9 elementary operations per second ). Make them all work for one full year which is 3.154*10^7 seconds. They will be able to perform 5*10^27 elementary operations in a year.
If a chess position can be generated and examined in one elementary operation ( in practice this takes orders of magnitudes more ) and we want to examine 10^40 positions with all PC-s on Earth it would take 2*10^12 years, more time than the age of the universe.
Currrently it is believed that chess has legal positions on the order of 10^40+.
Let's get started !!..........
I also think we should start ...
... studying quantum computers.
Yes, if the path to a solution lies anywhere it's there.
Symmetries are at most three bits of superfluos information. One order of magnitude.
In my humble opinion, the most tractable approach is to focus on board representation. And in some ingenious ways to prune away information, based on that there are no legal moves that can lead to positions requiring that information.
You say that Lomosonov tablebases uses 150 bits per position? Any information on how they encode the positions? Shouldn't they be able to get away with less than that (since they can assume there are at most 7 pieces.. )
Ultimately, aren't we trying to modularize the count ? If we broke it into say, 20-30-40 separate conditions, then it'd be a start. I'd like to see the matrix for this....I'm sure it's already put together...then we could zero in on what's not immediately solvable and possibly subset that....I don't know....
(the halo represents naivete)
Tapani, I proposed a minimal scheme based on the small piece count a couple of pages back. 14 bits per piece, 15 if you really do need to capture high colour to move. No en passant or castling indicators either. For a position with seven pieces, this isn't far off the 150 bits for the position, so it's already probably prey close to optimized at 150.
In a post I have calculated the volume of the memory needed to store bits on the order of the number of legal chess positions. For very unscientific reasons I was calculating with 1 bit of information stored in 1 water molecule.
In fact this turns out to be not that far from reality. If not water at least oxygen is involved in this experiment :
"The computer could be instructed to end the voltage pulse at a particular value of the tunneling current, thus leaving the molecule in any desired location," they said. So, a molecule might be set in a particular position to store information.
Good question, one for google :) lol
Here's a forum I'd like you guys to participate in..
http://www.chess.com/forum/view/off-topic/favourite-quotes
Tapani, I proposed a minimal scheme based on the small piece count a couple of pages back. 14 bits per piece, 15 if you really do need to capture high colour to move. No en passant or castling indicators either. For a position with seven pieces, this isn't far off the 150 bits for the position, so it's already probably prey close to optimized at 150.
Oh, saw it. Actually I remember seeing that but thought 150 was way way too much for 7 pieces :-)
Just from the top of my head, up to 7 pieces should be encodable in 50-something bits.
Adds up to well below 60 bits. Properly coded I think under 50 is possible.
The base 6 number encodes the remaining pieces as a list (do I need to explain how to encode a list as a number?) of white pieces first (values 1-5), then a 0 to indicate color change, then the black pieces (values 1-5). If less than 7 pieces, additional 0s can be used for blanks (and the squares to be omitted).
And there are still many many representations for every position (KRPvKRPP == KPRvKRPP == KRPvKPRP etc). Guessing on about 7-8 bits of redundancy, hence a total of around 50 might be possible.
I have made my thinking and calculations on the subject and I think that I have a better understanding of the question now.
I have a proof that there are less than 1.55 * 10^47 legal chess positions ( there are better upper bounds than this, but those are proofs of others and I'm not familiar with their subtleties, on the other hand I understand my own proof fully and I can explain it in detail ).
These 1.55 * 10^47 random positions are generated in a systematic way, they can be enumerated, so storing a random legal chess position can be done in at most log(1.55*10^47)/log(2) ~ 157 bits.
Number of possible legal armies of chessmen ( vertical axis ) in function of the number of men in the armies ( horizontal axis ):
The number of random positions per legal army can be calculated in a straightforward way. Determining the number of random positions that can be set up using legal armies is then a question of summing up these numbers for all the 58 084 310 possible armies. This is how the 1.55 * 10^47 number is reached.
An army can be thought of as an n-touple:
( n1, n2, ... , n(i) , ... , n10 )
where n(i) denotes the multiplicity of the (i)-th kind of chessman in the army ( there are 10 different kinds of non king chessmen ).
In all positions there are two kings, so kings need not be listed in the army, also their multiplicity is 1. Of two kings there are 3612 legal positions. In each of those 62 squares are empty.
Generating random position amounts to putting the members of an army on squares randomly choosen from the 62 empty squares.
The number of distinct ways in which you can place an army on the 62 empty squares depends only on the n-touple describing the army:
If you calculate this formula for the starting position and multiply it by the number of legal king positions you get almost the Shannon number, 4.63 * 10^42 ( not exactly because Shannon did not correct his number for legal kings, but that is the only difference ):
If you divide this number with Shannon's number
you get:
3612 / ( 64 * 63 )
64*63 is the number of ways in which you can place two kings on the board, including illegal positions, 3612 is the number of legal ways, so this gives the legality ratio of two king positions, which is cca. 0.89.
.....
I like how you've applied this linear algebra thing....it seems like it should hold. My comment is that....do we care whose move it is ?....assuming the board is always "White plays from 270 degrees - black plays from 90 degrees" then these positions are ='ly symmetrical....therefore, (1) position....irrespective of "White to Move or Black to Move".
Maybe at this point I need clarification/definition on "Unique Positions"....because I see the examples above as (1) count........
The symetries are still all unique positions, but from a tablebase evaluation efficiency standpoint the calculation only needs to be performed once and then applied to each symetrical position.