Enumeration: number of positions Einstein forum
12 replies. Last post: 20070510
Reply to this topic Return to forum
ypercube ★ at 20070503
Has anybody counted
1. the number of possible positions, configurations of the board of the EinStein game?
2. and how many of these positions can actually appear in a real game? (example: five in a row of the same colour is not possible in the first row or column, so such a position counts for question 1 but not for 2).

William S. at 20070504
for #1, the exact answer is 2 681 526 361 893 625 positions.
for #2, I have an upper bound of 2 490 013 193 601 024 positions.

Ingo Althofer at 20070505
Hello all,
yper asked:
> 1. the number of possible positions, configurations
> of the board of the EinStein game?
> 2. and how many of these positions can actually appear
> in a real game? (example: five in a row of the same
> colour is not possible in the first row or column, so
> such a position counts for question 1 but not for 2).
William replied:
> for #1, the exact answer is 2 681 526 361 893 625 positions.
> for #2, I have an upper bound of 2 490 013 193 601 024 positions.
Without checking the numbers in detail, the bounds given
by William look reasonable to me.
When designing the game (back in Summer 2004) two
of my side constraints were:
(i) The game should be as small as possible.
and
(ii) The game should be so large that there was/is no danger
of solution by computer enumerations in the near future.
Greetings, Ingo.

FatPhil at 20070505
I make #1 5595650767265101, so disagree with Willam and Ingo by a factor of over 2.
I think I know what William did. I conclude that “no stones on the board” was a configuration that he did _not_ count. I do.
Note, as every position apart from that empty configuration has an associated position where every stone has its colour swapped, the number of nonempty configurations must be even. So the total including the empty one must be odd.

Jörg Günther at 20070506
To get a number I did the following:
There are configuratons on the board with k stones, k ranging from 0 to 12.
There are 25!/(k!*(25k)!) different ways to place k (equal) stones on a board with 25 positions (ignoring any symmetry).
There are 12!/(k!*(12k)!) different sets of k stones out of the 12 EWNstones.
Every set of k stones can be permutatet: k!.
Putting this together gives $\sum_{k=0}^{12} ( \frac{25!}{k!*(25k)!}*k!*\frac{12!}{k!*(12k)!})$ (in tex)
and letting do maple its dirty work gives
> sum((25!*12!)/(k!*(25k)!*(12k)!), k=0..12);
5595650767265101
Which is Phils number.

FatPhil at 20070506
Thanks for reproducing my result, JÃ¶rg. I deliberately didn't include my working as I wanted to make sure that I didn't influence others' derivations.
In Pari/GP:
? einstein(n) = 25!/(25n)!
? s=0;for(i=0,12,v=einstein(i)*binomial(12,i);s+=v;print(i,” “,v,” “,s))
0 1 1
1 300 301
2 39600 39901
3 3036000 3075901
4 150282000 153357901
5 5049475200 5202833101
6 117821088000 123023921101
7 1918800576000 2041824497101
8 21586506480000 23628330977101
9 163098048960000 186726379937101
10 782870635008000 969597014945101
11 2135101731840000 3104698746785101
12 2490952020480000 5595650767265101
(the rightmost column is the running total)
Or more succintly:
? sum(n=0,12,(25!*12!)/(n!*(25n)!*(12n)!))
5595650767265101

FatPhil at 20070506
Quoth Ingo: (i) The game should be as small as possible.
Removing the two corners which remain almost always unused reduces the number of arbitrary stone positions by a factor of 4. I don't know what it does to the number of actually attainable positions, though.
Has anyone ever won a frame after going though either of those corner squares?

Ingo Althofer at 20070506
FatPhil wrote:
> I make #1 5595650767265101, so disagree with Willam
> and Ingo by a factor of over 2.
You may be right in formal numbers, but from the
viewpoint of in/tractability a factor of 2 is
peanuts in this situation.
The trivial lower bound
25*24*23*…*14*13 was large enough
for my purposes.
FatPhil wrote:
> Quoth Ingo: (i) The game should be as small as possible.
> Removing the two corners which remain almost always unused
> reduces the number of arbitrary stone positions by a factor
> of 4.
By “small” I did not only mean the shear number, but also
some sort of “descriptional complexity”. In this sense
“5x5 board” may be interpreted to be simpler/smaller than
“5x5 board without the northeast and the southwest corner.”
> Has anyone ever won a frame after going though either
> of those corner squares?
I think LuiseR had a situation at least in one of her games
where a move to the corner square gave best chances.
Ingo.

Theo van der Storm at 20070506
> Has anybody counted …
A slightly different question:
3. What's the number of essentially different EinStein move exercises a player can be faced with? This includes her/his throw.
take into account symmetries, e.g.
 if a player has one stone the number on it is irrelevant.
 mirrored positions across the diagonals
 numbering each player's stones upwards or downwards, e.g. 126 against 35 is essentially the same as 156 against 35 (or 24 for that matter).
 player with stones 126 throws 3, 4 or 5. They are essentially the same exercise.

kitaktus at 20070510
@FatPhil and Joerg:
Positions with blue stones on e1 and red stones on a5 can be ignored, they are already finished. Perhaps William S. took this into account.
@Theo:
The verry most positions have 3 symmetries. Some have less (e.g. if all stones stands on the diagonal), some have more (e.g. a EinStein). But I think factor 8 is a good approximation.
The most positions have many stones. So I would say that there are in average between 4 and 5 distinguishable dice throws.
So, taking the answer for ypercubes question 2, dividing it by 2^3 and multipling it with 4 or 5 could be a good approximation.
@FatPhil again:
I also already saw a position were a2a1 was optimal. I don't know the exact position but the main theme was someting like:
…..
…..
…..
E…6
..5..
a2a1 gives 5/6(5/6)^4 = 35.108..%
a2b1 or a2b2 gives 1/6 = 16.666..%