Einstein wuerfelt nicht

[hgm]

I guess it does not really count as a Chess variant, but it does share some aspects with it (like replacement capture), and is a fun game that is trivial to learn: "Einstein wurfelt nicht". Which as most of you probably know is Klingon for "Onestone does not throw dice".

It was a bit of a challenge to make WinBoard and XBoard support this game, because it requires the players to roll a die. But fortunately WB protocol has an almost-never-used "askuser" command that engines can use to ask questions to the user through a GUI popup, and this was eminently suitable for something like this.

Nevertheless it required a change in WinBoard, which should actually be considered a bug fix: WinBoard would refuse any move in a position where the side to move has no King (except in Suicide and Giveaway, but there it insists you make any capture you can, which also is a deal breaker). This was a side effect of Atomic Chess, where it is illegal to explode your own King, and WinBoard tacitly assumed you would have a King before the move, so it figured you must have exploded it when it cannot find one after your move. I fixed that by skipping the check test when the King is not amongst the participating pieces (i.e. if no ID is defined for it).

With that fix, and some handiwork for making new piece images, this did the trick:



I made an engine that reports it plays "einstein" as the only variant (which is then interpreted as an engine-defined variant, as WinBoard has never heard of it). This makes WinBoard automatically switch to that variant when you start it with that engine. And the engine then tells it the participating pieces, their initial setup, and how they move. As "Einstein wuerfelt night" is a shuffle game, the engine shuffles that initial position, and in case of a comp-comp game the position given by the first engine would be sent to the second. So to the user it all looks like the GUI knows the game.

In comp-comp mode the engines roll the dice for their own move. Unfortunately this does not preclude any cheating. For human-engine mistrusty people can role their own die, and enter the result when the engine asks it (the default mode), but there is an engine setting (a checkbox in the appropriate dialog) that can also let the engine role the die for you. The engine can be made (through another checkbox) to mark the stone(s) it has to move as a result of the die role before it start thinking, so that you can know what it is thinking about.

For those that would like to try it, I put a package with the fixed WinBoard, piece images (only in size 'bulky'!) and the engine for download on my website, at

http://hgm.nubati.net/einstein.zip .

[JoshPettus]

Klingon?

Sounds really neat Harm. I'll have to give it a try.

[hgm]

I now uploaded a slightly improved version. I made an alternate set of piece graphics, where the stones have no numbers on them, but look like dice. This slightly ameliorates the problem that when selecting "Highlight active stone", the WinBoard highlight marker covers the number completely. Still not ideal, though. I also included an engine logo.



The engine now can also roll the die on behalf of a human opponent, when both "Highlight active stone" and "Computer rolls dice" are switched on. When it is the user's turn the stones he canmove are then highlighted, and when he attempts to move another stone, the engine will reject it as an illegal move.

[Evert]

The game is quite neat, but is there any real challenge to writing an engine to play this?

Since the board is pretty small and move options are limited, it's actually very easy to just play out 10000 random games for a given position and die roll and pick the move with the best odds of winning:

Code: Select all

b 8 a 0 0 
c 9 0 0 0 
7 0 0 0 1 
0 0 0 3 6 
0 0 4 5 2 
Die = 3
e2d2
# Win 0.7000 (7 / 10)
# Win 0.5100 (51 / 100)
# Win 0.4910 (491 / 1000)
# Win 0.4704 (4704 / 10000)
# Win 0.4610 (460985 / 1000000)
# Win 0.4623 (4622981 / 10000000)
e2d3
# Win 0.6000 (6 / 10)
# Win 0.5400 (54 / 100)
# Win 0.5080 (508 / 1000)
# Win 0.4998 (4998 / 10000)
# Win 0.5038 (503826 / 1000000)
# Win 0.5035 (5034626 / 10000000)
e2e3
# Win 0.4000 (4 / 10)
# Win 0.4100 (41 / 100)
# Win 0.4450 (445 / 1000)
# Win 0.4499 (4499 / 10000)
# Win 0.4485 (448478 / 1000000)
# Win 0.4487 (4486722 / 10000000)

I can think of all sort of clever things to do to speed things up (distance to winning, detect some decided positions a few moves early, weigh the probabilities for expanding the different nodes), but they seem quite pointless given that playing 10000 purely random games for each root move tells you fairly accurately how likely each move is to win you the game...

Am I missing something that makes this an interesting game for computers?

[hgm]

It is true that the strength difference between a random mover and perfect play is not nearly as large in this game as in Chess. A non-searching engine, playing by a simplistic rule (comparable to playing by SEE in Chess) beat a random mover by about 75%, and loses again to a simple searching engine by ~65%. Differences between searching engines might only be a few percent. For this reason touraments typically use series of games. E.g. in the Olympiad they played 8 games per pairing (with 7 participants). At least draws are not possible.

Tactics plays a quite large role in this game, and often only a single move of the 6 allowed does not end in disaster (e.g. you must capture the opponent's most advanced stone, or he will finish way before you do, or you must make a detour to prevent exposing your most-advanced stone to capture by a highly mobile opponent stone). So averaging over all allowed moves (which is what random playouts would do) is often totally off. So I don't think that purely random playouts would do a very good job. MC-UCT would of course work, and some engines do indeed use that. But it would need enough playouts to figure out which move is best in every situation where the dice bring you.

[hgm]

E.g. I tried to do the position you calculated above with my engine. I amnot sure I did this correctly,because it looks a bit puzzling. I assumed that 7 means stone 1 for black,etc. But it says Die=3, and then calculates moves for stone 6???

If I feed my engine a 6 in this position, and set it thinking, I get the following:

Code: Select all

dep	score	nodes	time	(not shown:  tbhits	knps	seldep)
 11	+13.22 	330.7M	1:00.31	e2d2 
 10	+13.01 	60.8M  	0:11.19	e2d2 
  9	+13.10 	11.2M  	0:02.14	e2d2 
  8	+17.70 	1.89M  	0:00.42	e2d2 
  7	+18.44 	298335	0:00.12	e2d2 
  6	+16.50 	55401  	0:00.02	e2d2 
  5	+24.60 	11583  	0:00.00	e2e3 
  4	+20.00 	1705    	0:00.00	e2d2 
  2	  0.00 	1          	0:00.01	throw 6, stone 6 
  0	# 

As it prints the estimated winning probability -50 (to get a symmetric range), this means 63% winning probability for e2d2, which seems quite different from what you get.

Also note that alpha-beta does not work well, and you basically have to do full minimax. A hash table just seemed to make it weaker; the best lines have very few transposition, and the hash probing reduced the speed from 6Mnps to 4Mnps.

[Evert]

E.g. I tried to do the position you calculated above with my engine. I amnot sure I did this correctly,because it looks a bit puzzling. I assumed that 7 means stone 1 for black,etc. But it says Die=3, and then calculates moves for stone 6???

Yeah, it always calculated for stone 6; I failed to pass the result of the die roll to the move generator.
The stones are numbered 1-12 and printed in hexadecimal, so indeed 7 is stone 1 for black.

As it prints the estimated winning probability -50 (to get a symmetric range), this means 63% winning probability for e2d2, which seems quite different from what you get.

That is rather different, yes. I'll have to check what my engine currently says.

Also note that alpha-beta does not work well, and you basically have to do full minimax. A hash table just seemed to make it weaker; the best lines have very few transposition, and the hash probing reduced the speed from 6Mnps to 4Mnps.

I'm not even sure how to do hash probing properly, taking into account the dice. So at the moment it just does a type of multi-PV random playout of the root moves...

[Evert]

It's not much different:

Code: Select all

b 8 a 0 0 
c 9 0 0 0 
7 0 0 0 1 
0 0 0 3 6 
0 0 4 5 2 
Die = 6
e2d2
# Win 0.5000 1.0000 (5 / 10 vs 1 / 1, d=0)
# Win 0.4500 0.3333 (45 / 100 vs 4 / 12, d=1)
# Win 0.4760 0.5185 (476 / 1000 vs 112 / 216, d=2)
# Win 0.4745 0.4630 (4745 / 10000 vs 1800 / 3888, d=3)
# Win 0.4634 0.4657 (46337 / 100000 vs 34403 / 73872, d=4)
# Win 0.4626 0.4633 (462560 / 1000000 vs 657436 / 1419052, d=5)
# Win 0.4635 0.4613 (4635195 / 10000000 vs 13314032 / 28861607, d=6)
e2d3
# Win 0.5000 1.0000 (5 / 10 vs 1 / 1, d=0)
# Win 0.5400 0.5000 (54 / 100 vs 6 / 12, d=1)
# Win 0.5150 0.5093 (515 / 1000 vs 110 / 216, d=2)
# Win 0.4916 0.4992 (4916 / 10000 vs 1941 / 3888, d=3)
# Win 0.5020 0.5029 (50199 / 100000 vs 35193 / 69984, d=4)
# Win 0.5039 0.5042 (503911 / 1000000 vs 644518 / 1278269, d=5)
# Win 0.5032 0.5038 (5031765 / 10000000 vs 11895669 / 23609734, d=6)
e2e3
# Win 0.3000 1.0000 (3 / 10 vs 1 / 1, d=0)
# Win 0.4600 0.5000 (46 / 100 vs 6 / 12, d=1)
# Win 0.4700 0.4954 (470 / 1000 vs 107 / 216, d=2)
# Win 0.4546 0.4596 (4546 / 10000 vs 1787 / 3888, d=3)
# Win 0.4591 0.4628 (45908 / 100000 vs 32388 / 69984, d=4)
# Win 0.4618 0.4617 (461796 / 1000000 vs 589639 / 1277158, d=5)
# Win 0.4614 0.4617 (4614037 / 10000000 vs 10958760 / 23734782, d=6)

The first number is the result of a pure random playout, the second is a full width search to d ply followed by random playout. Of course, it's quite probable that the latter completely dominates the score. I did make the random playout slightly less stupid in that if there is an obviously winning move, it will actually play that instead of picking a random move.

[hgm]

Well, I cannot guarantee that the number my engine prints is anywhere close to correct. When it can search to the end of the game the results seem to make sense, so the way I propagate scores through the search is probably correct. The evaluation can suck, however.

I don't know how much the predicate 'obviously winning move' covers. Moves that would be obvious to my static evaluator could be pushing your own stone closest to finishing, capture an own stone adjacent to your quickest finisher to makeit finish even faster, or capturing the opponent's most advanced stone, when that delays his arrival more than you can accelerate your own (by moving forward or capturing an own stone). Doing playouts mostly guided by those rules could be better than random.

It would anyway be better to test on positions with only 3 or 4 stones, where you can calculate the winning probabilities by hand.

[elpapa]

mI' nagh ronmoHbe' Qun