OT: Roman boardgame deciphered with help from AI

[Eelco de Groot]

In case anyone gets tired with playing chess, an almost as old game, well 2000 years old game was studied with Ludii -Ludi in latin translates as 'games' I think, or something similar?-, an AI. By studying the tracks in the stone researchers could figure out which moves were played most and this matched against sets of possible rules the AI came up with as playable and attractive for a game. It looks a bit like "het molenspel" I think, in Dutch, although I do not know the rules to that either or what it is called in English. Rules can be found at site of Maastricht University. Maybe Jaap van den Herik was involved although I think he retired a couple of years ago.

https://nos.nl/artikel/2601837-ai-onthu ... s-bordspel

Google translates the NOS article
https://nos-nl.translate.goog/artikel/2 ... _hist=true

Finally someone came up with something useful to do with AI

[Ajedrecista]

Hello Eelco:

Thank you very much for the info! The proposed rules of the game in Dutch language are here:

https://www.maastrichtuniversity.nl/nl/ ... 6-02-10pdf

The assymetric nature of the game reminds me tafl games and even the proposed solution of play the both sides and the winner is the win in less moves. The proposed rules do not specify who starts, but only moves of the strong side count. I guess that the solution is each player to play the two sides of the game and the same side starts in each game (the weak or the strong).

I see that the board has got 10 spots and 6 of them are always occupied, so there are always 4 empty. It is the kind of game that intuitively has a 'small' game tree size (solvable in a reasonable time for a computer), but I do not know. The maximum number of spots where a piece can move is:

Code: Select all

2——5——2
| /|\ |
|/ | \|
3  |  3
|  |  |
3  |  3
|\ | /|
| \|/ |
2——5——2

Ideally, one can expect a game to end like this, with the pieces of the weak side (w) isolated in two of the corners by the pieces of the strong side (S):

Code: Select all

w——S——·
| /|\ |
|/ | \|
S  |  ·
|  |  |
S  |  ·
|\ | /|
| \|/ |
w——S——·

And the more interesting position for the weak side is to place their two pieces in the middle spots because the strong side has not got enough pieces to block both immediately, but I guess that can manoeuvre because the weak side must move:

Code: Select all

·——w——·
| /|\ |
|/ | \|
S  |  S
|  |  |
S  |  S
|\ | /|
| \|/ |
·——w——·

The pieces of the weak side can block themselves and the strong side do not need all its pieces to win the game:

Code: Select all

·——·——S
| /|\ |
|/ | \|
S  |  S
|  |  |
w  |  ·
|\ | /|
| \|/ |
w——S——·

Fun fact: I did all this theory from the board drawn at the first page of the PDF, which is different from the board of the second page!

Code: Select all

2——3——3——3——2
| /   |   \ |
|/    |    \|
3     |     3
|     |     |
3     |     3
|\    |    /|
| \   |   / |
2——3——3——3——2

With 14 spots and 8 of them always empty. There are not 5-move spots anymore (thus easier for the strong side IMHO) and the weak side placing their two pieces on the equivalent former 5-move spots does not save it from an immediate lose because two S can block each w and both w block themselves through the half-way line:

Code: Select all

·——S——w——S——·
| /   |   \ |
|/    |    \|
·     |     ·
|     |     |
·     |     ·
|\    |    /|
| \   |   / |
·——S——w——S——·

Both boards admit algebraic notation. From the strong side POV, for example:

Code: Select all

w—·—·—w  3
|/   \|
·—————·  2
|\   /|
S—S—S—S  1

a b c d

Code: Select all

w—·—·—w  5
|/   \|
·     ·  4
|     |
·—————·  3
|     |
·     ·  2
|\   /|
S—S—S—S  1

a b c d

Here is a proof game on the 14-spot board with the strong side (S) moving first. Please forget about accuracy:

Code: Select all

 1. a1-a2  a5-a4
 2. a2-a3  d5-d4
 3. d1-d2  d4-d3
 4. b1-a1  d3-d4
 5. d2-d3  d4-d5
 6. d3-d4  d5-c5
 7. c1-d2  c5-d5
 8. d2-d3  d5-c5
 9. d4-d5  c5-d4
10. d5-c5  d4-d5
11. d3-d4  a4-a5
12. a3-a4  a5-b5
13. a1-a2  b5-a5
14. a4-b5  a5-a4
15. a2-a3  a4-a5
16. a3-a4

w—S—S—w  5
|/   \|
S     S  4
|     |
·—————·  3
|     |
·     ·  2
|\   /|
·—·—·—·  1

a b c d

S wins in 16 moves in this proof game.

I hope no typos. The triangles in the corners allow triangulations for the strong side in order to zugzwang the weak side. I would like to see engines playing this game in both 10-spot and 14-spot boards. I am sure that they will find optimal strategies in few time.

------------

I would like to see the AI digging into other old board games like senet, hounds and jackals, mehen, the Royal Game of Ur, ludus latrunculorum, XII scripta, alquerque and polis (unknown to me until right now and more difficult to investigate due to the absence of surviving boards), if they have not being investigated through AI yet, and see (new?) proposed rules and/or new conclusions. There is a list of some old board games here.

Any insights are welcome, as usual.

Regards from Spain.

Ajedrecista.

[xenos1984]

I would like to see the AI digging into other old board games like senet, hounds and jackals, mehen, the Royal Game of Ur, ludus latrunculorum, XII scripta, alquerque and polis (unknown to me until right now and more difficult to investigate due to the absence of surviving boards), if they have not being investigated through AI yet, and see (new?) proposed rules and/or new conclusions. There is a list of some old board games here.

Quite a few of them are actually included in the Ludii game database. You can also play them against the computer. I don't know which ones they are actively researching, though.

[Ajedrecista]

Hello:

I would like to see the AI digging into other old board games like senet, hounds and jackals, mehen, the Royal Game of Ur, ludus latrunculorum, XII scripta, alquerque and polis (unknown to me until right now and more difficult to investigate due to the absence of surviving boards), if they have not being investigated through AI yet, and see (new?) proposed rules and/or new conclusions. There is a list of some old board games here.

Quite a few of them are actually included in the Ludii game database. You can also play them against the computer. I don't know which ones they are actively researching, though.

Thank you very much for the web! I did not know it. By the way, the 10-spot variant game was added under the name Ludus Coriovalli because the game was discovered in Heerlen (The Netherlands) and the Romans founded there a militar settlement name Coriovallum.

Description

This pattern was found on object 04433 in Het Romeins Museum, Heerlen, the Netherlands. It was found in Roman Coriovallum, probably sometime in the late nineteenth or early twentieth century. It has a unique pattern not attested in other games, but use wear on its surface is consistent with the movement of Roman-era gaming pieces along the lines on its surface. AI-driven simulated play identified rules that replicated the pattern of wear on the stone. This was the first time such a game was identified in this way.

------------

I played against the computer in the 10-spot variant (the weak side starts) and managed to win by blocking the weak pieces in opposite corners. Keeping the notation of my former post:

Code: Select all

 1. a3-b3  d1-d2
 2. d3-c3  a1-a2
 3. b3-a3  b1-a1
 4. c3-d3  c1-d1
 5. d3-c3  d2-d3
 6. c3-d2  d3-c3
 7. a3-b3  a1-b1
 8. d2-d3  d1-d2  // The first piece is trapped.
 9. b3-a3  a2-b3
10. a3-a2  b3-a3  // The weak side only has two moves, each ending the game at the next ply (a2-a1 a3-a2 OR a2-b3 b1-a2).
11. a2-a1  a3-a2

·—·—S—w  3
|/   \|
S—————S  2
|\   /|
w—S—·—·  1

a b c d

S wins in 11 moves.

Occupy one of the 5-move spots (a2 or d2) ASAP and stay there cuts a lot of moves of the weak side.

There are also other variants with different number of pieces of the weak and strong sides implemented at Ludii Portal, as well as different lattices.

------------

I would say that the shortest possible games with the weak side playing bad on purpose and the strong side starting are three moves in the 10-spot variant and seven moves in the 14-spot variant, both in 4 vs 2 pieces:

Code: Select all

1. a1-a2  d3-c3
2. d1-d2  c3-b3
3. d2-c3

w—w—S—·  3
|/   \|
S—————·  2
|\   /|
·—S—S—·  1

a b c d

S wins in 3 moves.

==================

1. a1-a2  d5-c5
2. a2-a3  c5-b5
3. a3-a4  b5-c5
4. d1-d2  c5-b5
5. d2-d3  b5-c5
6. d3-d4  c5-b5
7. d4-c5

w—w—S—·  5
|/   \|
S     ·  4
|     |
·—————·  3
|     |
·     ·  2
|\   /|
·—S—S—·  1

a b c d

S wins in 7 moves.

------------

Low depth perft values computed by hand for both 10-spot and 14-spot variants should be:

Code: Select all

10-spot variant:
Perft(1) =  4
Perft(2) = 12

14-spot variant:
Perft(1) =  4
Perft(2) = 16

------------

A simpler lattice would be a polygon (a regular polygon for better comprehension), where each spot or vertex allows two moves at most: clockwise (CW) and counterclockwise (CCW); and two pieces for the strong side and one for the weak side. Then, the solution is trivial. If we take a polygon with an odd number of vertex (N = {5, 7, 9, ...}) naming N the vertex where the weak side starts and 1, 2, 3, ... CW in a clock fashion, and the pieces of the strong side starting at spots floor(N/2) = (N-1)/2 and ceiling(N/2) = (N+1)/2 (this is the reason for an odd N: the pieces of the strong side being together and at equal distance CW and CCW of the piece of the weak side), and the strong side starting, one of the plans is just take the piece of ceiling(N/2) and move CW, the weak side moves CCW while possible, and move the piece on floor(N/2) CCW when needed. There is a moment where the weak side must go CW and the piece that started on floor(N/2) just chase CW until the end. For example:

Code: Select all

   N = 5

     5

     w
4 ·     · 1
    S S

    3 2

1. 3-4  5-1
2. 4-5

===============

     N = 7

       7

       w
  6 ·     · 1
5 ·         · 2
     S   S

     4   3

1. 4-5  7-6
2. 3-2  6-7
3. 5-6  7-1
4. 6-7

With this particular setup, the number of moves to win is N-3. One of the pieces of the strong side waits while the other chases the weak side, very much in the fashion of this video if things would have been done right:

https://www.youtube.com/watch?v=UXEAKNWR6NU

(From The Simpsons S10E13 'Homer to the Max', first aired on February 7, 1999).

Regards from Spain.

Ajedrecista.

[Ajedrecista]

Hello:

I let the computer to play against itself in the 10-spot variant (4 vs 2) and the game finished in seven moves:

Code: Select all

w starts.

1. d3-c3  a1-a2
2. c3-d3  d1-d2
3. d3-c3  d2-d3
4. c3-d2  a2-b3
5. d2-d1  b1-a2
6. d1-d2  d3-c3
7. d2-d3  c1-d2

w—S—S—w  3
|/   \|
S—————S  2
|\   /|
·—·—·—·  1

a b c d

S wins in 7 moves.

This does not mean that both sides played perfectly, of course. For example, I thought that 5. d2-d1 was bad, cornering itself, while 5. d2-a2 keeps a piece on one of the 5-move spots, being less cramped. I forced 5. d2-a2 and let the computer play against itself again:

Code: Select all

w starts.

1. d3-c3  a1-a2
2. c3-d3  d1-d2
3. d3-c3  d2-d3
4. c3-d2  a2-b3
5. d2-a2  d3-d2
6. a2-a1  d2-a2

w—S—·—·  3
|/   \|
S—————·  2
|\   /|
w—S—S—·  1

a b c d

S wins in 6 moves.

I was proven wrong, naturally, but it served to me to discover a new lock pattern where one piece (the one on a2) contributes to lock two pieces at once.

------------

I let the computer to play against itself again. The weak side started moving a piece to a 5-move spot (finally!) and the game was much longer:

Code: Select all

w starts.

 1. a3-a2  c1-d2
 2. d3-c3  d1-c1
 3. c3-d3  c1-d1
 4. a2-a3  a1-a2
 5. a3-b3  b1-c1
 6. d3-c3  a2-a1
 7. b3-a3  d2-d3
 8. a3-a2  c1-d2
 9. a2-b1  d2-c1
10. c3-d2  d3-c3
11. d2-d3  a1-a2
12. b1-a1  c1-d2
13. a1-b1  d1-c1
14. b1-a1  c1-b1

·—·—S—w  3
|/   \|
S—————S  2
|\   /|
w—S—·—·  1

a b c d

S wins in 14 moves.

I really like the game and wonder about how top engines would handle it. The engine at Ludii Portal is called Ludii (UCT), so I expect Upper Confidence bounds applied to Trees.

Regards from Spain.

Ajedrecista.

[xenos1984]

The engine at Ludii Portal is called Ludii (UCT), so I expect Upper Confidence bounds applied to Trees.

Yes, that's correct. The Java Ludii player has more engines to choose from, including alpha-beta.

[Ajedrecista]

Hello:

There is an interesting article about the research of the game, proposed rulesets with AI and much more here:

Ludus Coriovalli: using artificial intelligence-driven simulations to identify rules for an ancient board game (HTML version).
Ludus Coriovalli: using artificial intelligence-driven simulations to identify rules for an ancient board game (PDF version).

It is worth reading IMHO. The full list of possible number of moves is 30 for the 10-spot variant and 38 for the 14-spot variant, as we can see at Figure 9, boards F and G: there are 15 and 19 lines, respectively, and they can be travelled in either direction (back and forth, left and right, up and down or whatever you want to call it).

------------

The objective of the game with the proposed ruleset is that the strong side must lock the weak side... but the reverse is also possible! Keeping my notation of former posts:

Code: Select all

S starts.

1. a1-a2  d3-d2
2. a2-a1  a3-a2

·—·—·—·  3
|/   \|
w—————w  2
|\   /|
S—S—S—S  1

a b c d

S loses in 2 moves.

The same can be achieved in the 14-spot variant in few more moves, with w standing on a2 and d2 and S in their starting positions a1, b1, c1 and d1.

------------

I have written about 5-move spots in the 10-spot variant (a2 and d2). This is true in an empty board, but since the game has six pieces (4 vs 2), there are only 10 - 6 = 4 free spots at most for a2 or d2. In this case, the other 5-move spot will have much less mobility.

This is not exactly related with perft values and branching factors (BF). One can think that there is an upper bound of BF =< 4, so Perft(n) =< 4^n. In fact, we can remove the equal sign since we know that Perft(1) = 4 [BF(1) = Perft(1)/Perft(0) = 4/1 = 4] and Perft(1) = 12 [BF(2) = Perft(2)/Perft(1) = 12/4 = 3]. This is true early in the game regardless who starts first:

• If S starts: Perft(1) = 4 {a1-a2, b1-a2, c1-d2, d1-d2} and then w can move in 3 ways after each S initial move, so 3 + 3 + 3 + 3 = 12.

• If w starts: Perft(1) = 4 {a3-a2, a3-b3, d3-c3, d3-d2} and then S can move in 2 or 4 ways, depending on w initial move, so 2 + 4 + 4 + 2 = 12.

I will just stick to w starts from here because this is the variant implemented at Ludii Portal, that allows some tests. Then, Perft(3) =< 48 and Perft(4) =< 192 with the same reasoning. Going up, Perft(n) =< 12 × 4^(n - 2). For example, for 16 moves of the strong side (32 plies): Perft(32) =< 12 × 4^30 ~ 1.38e+19, but it could be a very generous upper bound. If we simply consider an estimated BF = sqrt(4 × 3) as in the first two plies, then Perft(32) ~ 12^(32/2) ~ 1.85e+17. This is with 32 plies, but the optimum solution/s of the game might be shorter. One step ahead, I computed Perft(3) by hand. I hope no typos:

Code: Select all

w starts.

w—·—·—w  3
|/   \|
·—————·  2
|\   /|
S—S—S—S  1

a b c d

 1) 1. a3-a2  c1-d2  2. a2-a3
 2) 1. a3-a2  c1-d2  2. a2-b3
 3) 1. a3-a2  c1-d2  2. d3-c3

 4) 1. a3-a2  d1-d2  2. a2-a3
 5) 1. a3-a2  d1-d2  2. a2-b3
 6) 1. a3-a2  d1-d2  2. d3-c3

 7) 1. a3-b3  a1-a2  2. b3-a3
 8) 1. a3-b3  a1-a2  2. b3-c3
 9) 1. a3-b3  a1-a2  2. d3-c3
10) 1. a3-b3  a1-a2  2. d3-d2

11) 1. a3-b3  b1-a2  2. b3-a3
12) 1. a3-b3  b1-a2  2. b3-c3
13) 1. a3-b3  b1-a2  2. d3-c3
14) 1. a3-b3  b1-a2  2. d3-d2

15) 1. a3-b3  c1-d2  2. b3-a2
16) 1. a3-b3  c1-d2  2. b3-a3
17) 1. a3-b3  c1-d2  2. b3-c3
18) 1. a3-b3  c1-d2  2. d3-c3

19) 1. a3-b3  d1-d2  2. b3-a2
20) 1. a3-b3  d1-d2  2. b3-a3
21) 1. a3-b3  d1-d2  2. b3-c3
22) 1. a3-b3  d1-d2  2. d3-c3

23) 1. d3-c3  a1-a2  2. a3-b3
24) 1. d3-c3  a1-a2  2. c3-b3
25) 1. d3-c3  a1-a2  2. c3-d2
26) 1. d3-c3  a1-a2  2. c3-d3

27) 1. d3-c3  b1-a2  2. a3-b3
28) 1. d3-c3  b1-a2  2. c3-b3
29) 1. d3-c3  b1-a2  2. c3-d2
30) 1. d3-c3  b1-a2  2. c3-d3

31) 1. d3-c3  c1-d2  2. a3-a2
32) 1. d3-c3  c1-d2  2. a3-b3
33) 1. d3-c3  c1-d2  2. c3-b3
34) 1. d3-c3  c1-d2  2. c3-d3

35) 1. d3-c3  d1-d2  2. a3-a2
36) 1. d3-c3  d1-d2  2. a3-b3
37) 1. d3-c3  d1-d2  2. c3-b3
38) 1. d3-c3  d1-d2  2. c3-d3

39) 1. d3-d2  a1-a2  2. a3-a2
40) 1. d3-d2  a1-a2  2. d2-c3
41) 1. d3-d2  a1-a2  2. d2-d3

42) 1. d3-d2  b1-a2  2. a3-a2
43) 1. d3-d2  b1-a2  2. d2-c3
44) 1. d3-d2  b1-a2  2. d2-d3

I took advantage of the symmetries. So Perft(3) = 44 and BF(3) = 44/12 = 11/3; 3.5 < BF(3) < 4. Will BF(n) =< 4 hold? Having 4 free spots does not mean 4 possible moves at most since different pieces can jump to the same free spot. Example in the eventual computation of Perft(4):

Code: Select all

w starts.

1. d3-d2  a1-a2
2. d2-c3

w—·—w—·  3
|/   \|
S—————·  2
|\   /|
·—S—S—S  1

a b c d

perft(1) = 6
{a2-a1, a2-b3, a2-d2, b1-a1, c1-d2, d1-d2}

So we need a true perft counter instead of vague estimates if we try to bound the tree size of the game. Other thing is that the average BF would be indeed less or more than 4 for higher depths.

------------

What is better for w in the opening (aiming for a longer game): a3-a2, a3-b3, d3-c3 or d3-d2? Given the symmetry of the game, running games forcing 1. a3-a2 and 1. a3-b3 is enough:

Code: Select all

Length of games played by the engine at Ludii Portal against itself.
Metric: moves of the strong side.
Alternatively, since the strong side always wins, we get plies = 2 × (moves of the strong side).

Meaning of the following sample vector:
[0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0]
0 games lasting 3 moves, 0 games lasting 4 moves, ..., 1 game lasting 8 moves, ..., 2 games lasting 16 moves, ..., 0 games lasting 25 moves.

Number of games by each opening move: 10
Number of moves:  [ 3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25] moves.
Forcing 1. a3-a2: [ 0,  0,  0,  1,  0,  1,  1,  0,  0,  2,  0,  2,  2,  0,  1,  0,  0,  0,  0,  0,  0,  0,  0] games.
Forcing 1. b3-a3: [ 0,  0,  0,  1,  0,  0,  2,  0,  2,  0,  1,  1,  0,  0,  1,  1,  0,  0,  0,  0,  0,  0,  1] games.

           1. a3-a2   1. a3-b3
Minimum:      6          6      // Less is worse for the weak side (that chooses the opening move).
Median:      12         11      // Less is worse for the weak side (that chooses the opening move).
Average:     12.2       13.3    // Less is worse for the weak side (that chooses the opening move).
Maximum:     17         25      // Less is worse for the weak side (that chooses the opening move).

This is not law carved in stone because the engine might not be perfect (I had the feeling about some moves repeating sometimes and even once the strong side got almost locked and the weak side refused to lock) and the number of games is low, but can give us a rough idea and some statistics (previous discard of outliers?): average number of moves, standard deviation, mode, median, percentils, minimum, ...

The game of 25 moves had lots of repeating moves IMHO and can be considered an outlier. If I cherry pick the data, discarding the three longer games of each opening move, I get:

Code: Select all

           1. a3-a2   1. a3-b3
Minimum:      6          6      // Less is worse for the weak side (that chooses the opening move).
Median:       9         11      // Less is worse for the weak side (that chooses the opening move).
Average:     10.7       10.4    // Less is worse for the weak side (that chooses the opening move).
Maximum:     14         14      // Less is worse for the weak side (that chooses the opening move).

This short experiment with 10 games in each opening and the cherry picking with the 7 shortest games showed different conclusions: the raw data with 10 games says that 1. a3-b3 is better for the weak side while the trimmed data says the opposite. Disclaimer: very few games and not a perfect engine.

The shortest game of 6 moves starting with 1. a3-a2:

Code: Select all

w starts.

1. a3-a2  d1-d2
2. d3-c3  d2-d3
3. a2-d2  a1-a2
4. d2-d1  a2-b3
5. c3-d2  b1-a2
6. d2-c3  a2-d2

·—S—w—S  3
|/   \|
·—————S  2
|\   /|
·—·—S—w  1

a b c d

S wins in 6 moves.

I did not record the shortest game of 6 moves starting with 1. a3-b3, which was played before in the experiment, but I would say that the locking pattern was similar if not the same. The sequence of games was like a penalty shoot-out : 1. a3-a2; 1. a3-b3; 1. a3-a2; 1. a3-b3; ...

Regards from Spain.

Ajedrecista.