### Enumeration: number of positions Einstein forum

12 replies. Last post: 2007-05-10

Enumeration: number of positions
• ypercube ★ at 2007-05-03

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).

• ypercube ★ at 2007-05-04

A quick upper limit for 1: 26^12. It's sure that it can be lowered.

• kitaktus at 2007-05-04

1. < 5.7 * 10^15 is the best limit, I can get in 5 min.

• William S. at 2007-05-04

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 2007-05-05

Hello all,

> 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 2007-05-05

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 non-empty configurations must be even. So the total including the empty one must be odd.

• Jörg Günther at 2007-05-06

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!*(25-k)!) different ways to place k (equal) stones on a board with 25 positions (ignoring any symmetry).

There are 12!/(k!*(12-k)!) different sets of k stones out of the 12 EWN-stones.

Every set of k stones can be permutatet: k!.

Putting this together gives $\sum_{k=0}^{12} ( \frac{25!}{k!*(25-k)!}*k!*\frac{12!}{k!*(12-k)!})$ (in tex)

and letting do maple its dirty work gives

> sum((25!*12!)/(k!*(25-k)!*(12-k)!), k=0..12);

5595650767265101

Which is Phils number.

• FatPhil at 2007-05-06

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!/(25-n)!

? 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!*(25-n)!*(12-n)!))

5595650767265101

• FatPhil at 2007-05-06

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 2007-05-06

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 north-east and the south-west 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 2007-05-06

> 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 2007-05-10

@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 a2-a1 was optimal. I don't know the exact position but the main theme was someting like:

…..

…..

…..

E…6

..5..

a2-a1 gives 5/6-(5/6)^4 = 35.108..%

a2-b1 or a2-b2 gives 1/6 = 16.666..%