UCT Skill Ladders for Small Games

Contents

Update History

DateDescription
6th July 2020Published
7th July 2020Added graphs

Introduction

"When I use a word," Humpty Dumpty said, in rather a scornful tone, "it means just what I choose it to mean - neither more nor less."
LEWIS CARROLL (Charles L. Dodgson), Through the Looking-Glass, chapter 6.

There has been a lot of discussion about depth over on the BoardGameGeek(BGG) forums recently; unfortunately, everyone means something slightly different when they talk about depth, so the discussions seldom reach a satisfactory conclusion. A more concrete concept is that of a skill ladder; given a large number of players, divide them into levels where a member of level N will beat a member of level N-1 roughly 60% of the time (actual percentages may vary!); the idea being that "deeper" games will have more skill levels. This is of course impractical; most of the games in our hobby don't have a large pool of players, and methods of ranking players are unreliable at the best of times. Depth in Strategic Games goes some way towards establishing a theoretical framework for skill ladders but again, it is not helpful if you actually want to construct such a ladder. Being a practical person, I have been playing around with a concrete version of this concept for a while - an early version is defined as the Levels of Play report in Ai Ai. See here for an example. For this article I have refined this concept, to provide an algorithm that can - given sufficient computing resources - be applied to any game to produce a consistent skill ladder, allowing some comparison between games.

My AI of choice is UCT (Upper Confidence bounds applied to Trees), a standard version of Monte Carlo Tree Search. Here's why:

So, questions I try to answer here:

The Algorithm

  set weakAI to Random
  set strongAI to slightly stronger than weakAI

  loop
    play match: weakAi vs StrongAI
    if strongAI beats weakAI by more than margin
      store level
      set weakAI to strongAI
    end if
    increase strength of strongAI
  end loop

Over time, strongAI will converge to something close to perfect play, and we will have defined a set of levels.

For these experiments, each match is over 1,000 games; strongAI is better than weakAI if strong wins 60% of the games (lower bound with 95% confidence.

Matches where strong does not beat weak by a sufficient amount are not shown in the tables below, but the first column of the table shows how many matches have been played so far, and hence the number of failed levels can be inferred.

The weakest AI is Random; each turn, it chooses a random move with equal probablity. This is equivalent to UCT with exactly one iteration per move. From here, I increase the number of iterations per move by 1 until a certain threshhold is reached (number of available moves at the root node), then multiply the number of iterations by a factor of 1.1 after that. This progression is based on practical experiments, which show a lot of levels just better than random even in games as simple as Tic Tac Toe!

I set a practical upper limit of 10 hours for any one run, since my computing resources are limited. In some cases this means that UCT didn't reach perfect play, and I can only give a lower limit on the number of levels.

At the end of a run, I play one last match with strongAI vs strongAI, to verify that the game theoretic result has been approximated or met.

Start Simple

My primary focus here is games played on a 3x3 grid; nine board spaces is reasonably small state space to analyse, given my limited computing resources. Fixing the board dimensions also removes one variable from consideration when performing comparisons. Later, I'll look at a few games as they increase in board size, and therefore complexity.

Let's start with an in-depth look at the results table for Tic Tac Toe; a game universally disparaged by adults, but still played by children. All the other results tables follow the same format.

MatchAIStrong WinsDrawsStrong Losses#GamesStrong Win%p1 Win%Draw%Game Length
0Random        
1UCT(its=2)55415326797462.00 <= 64.73 <= 68.0058.00 <= 61.45 <= 64.0015.717.51
4UCT(its=5)56613026395963.00 <= 65.80 <= 69.0055.00 <= 58.50 <= 62.0013.566.97
9UCT(its=10)57710727195563.00 <= 66.02 <= 69.0057.00 <= 60.58 <= 64.0011.206.62
18UCT(its=23)54317626798661.00 <= 64.00 <= 67.0068.00 <= 70.69 <= 73.0017.856.60
29UCT(its=67)44736717198561.00 <= 64.01 <= 67.0066.00 <= 68.68 <= 71.0037.267.14
49UCT(its=448)2876872099460.00 <= 63.43 <= 66.0062.00 <= 64.94 <= 68.0069.118.06
101
UCT(its=63645)
12
740
0
752
47.00 <= 50.80 <= 54.00
47.00 <= 50.80 <= 54.00
98.40
8.97
102
UCT(its=63645)
0
740
0
740
46.00 <= 50.00 <= 54.00
46.00 <= 50.00 <= 54.00
100.00
9.00

The last two lines in this table are greyed out for a reason. Match 101 is the last match between strongAI and weakAI, but strongAI did not exceed the threshhold. Match 102 is strongAI vs strongAI, and you can see here that the draw percentage has reached 100% - UCT is playing at near-perfect play. (I run these reports for a fixed period of time, so this does not indicate the minimum number of iterations for perfect play; only that sufficient time was spent. I may follow up on this in the future.)

Note that even a very small increase in the number of iterations from 1 to 2 makes the UCT algorithm a much better player; I was quite surprised to find that there are so many levels of play in even a game this simple. In fact, this seems pretty much invariant; regardless of the game, we see a number of levels even before the algorithm is capable of sampling every starting move. We could put this down to the nature of the UCT algorithm, but I'd like to think that humans are actually incredibly smart and that even a complete novice starts a few steps up the strategy ladder. It may also be that I've forgotten what it's like to be a young child, and that the levels are something we go through as we learn to play.

Last thing of interest here; the last level (match 49) shows that 69% of games are now draws; even the weak AI is getting close to perfect play. This effectively makes it impossible for another level of play to exist; with most of the games being drawn, the remaining games are not enough to reach our 60% win rate. This is the end of all our skill ladders; it is possible to differentiate between players only in the absence of perfect play.

Comparison of 3x3 Games

This is the meaty bit. These games use exactly the same board and don't use tricks to increased the available spaces. How do they compare?

GameLevelsits (last level)Converged toCellsGame LengthMean Branching FactorEst. State Space
Hexapawn4172nd Wins95.362.8010^2.26
Tic Tac Toe7448Draw98.065.4910^5.49
Breakthrough 3x377471st Wins96.365.0610^3.30
Go 3x3 (7.5 komi)81591st Wins912.245.0110^11.36
Hex 3x3 (no swap)83371st Wins95.586.4810^4.69
Achi95961st Wins910.286.1810^4.89
Three Men's Morris101547Draw915.257.3710^9.21
Hex 3x3 (swap)1236472nd Wins96.736.6610^5.04

You'll see that I've ordered the table by the number of levels. Tables of levels for the individual games are at the end of this article, if you want more detail.

The first thing of interest is that there are, apparently, worse games than Tic Tac Toe. Hexapawn was designed as an example for an article by Martin Gardner, c. 1962. It's very similar to Breakthrough, with chess pawn movement for the pieces (in Breakthrough, pawns can move diagonally as well as forwards). If you try it, you'll find that black only has to look one move ahead to find a winning sequence; making it indeed easier than Tic Tac Toe.

After Tic Tac Toe, we get Breakthrough 3x3; and now things begin to get interesting. Breakthrough is very similar to Hexapawn, so why is one better than the other? I can see two possible factors: (a) Breakthrough has a larger branching factor, and (b) at the start of the game, Breakthrough has 3 winning moves and 4 losing moves. Hexapawn has 3 losing moves and no winning moves. I'll investigate the effect of branching factor a little later, but for now I'm going to suggest that if the result is strongly influenced by an early game decision, you need strong AI to take advantage of that fact; to which end, note that the UCT iterations of the last level in Breakthrough (747) is higher than the next three ranked games.

Go was a little bit of a surprise; even on a small board, I was expecting Go to be a bit of a beast; it seems, however, that as long as you don't start in a corner, 7.5 komi can't compensate for the first player advantage. It's interesting to note, though, that Go is longer than most games in the group, and has the largest state space. These factors weren't enough to give it more levels of play. I performed a follow-up experiment (see below), and it seems that there is no komi that can adequately balance 3x3 go. Komi 8.5 finds an extra level of play, but that's it! Anything higher, and black can just pass every move to get the best result.

Next up, Hex. Twice. As you can see, I tested Hex both with and without the swap rule; and it makes a huge difference to the number of levels; 8 with no swap, and a massive 12 (plus a relatively huge number of iterations) with swap. As with Breakthrough/Hexapawn it seems that there is an early critical decision (swap/no swap) which defines the game so much more processing power is required to choose well, early.

That just leaves Achi and Three Men's Morris - Achi has 4 pieces per side and Three Men's Morris allows free movement of pieces, but otherwise they are basically the same (bring on your pieces, then move your pieces, make a row of three to win). Achi, it seems, is decisive, whereas Three Men's Morris devolves into loops and reaches the arbitrary 15 move limit I imposed. The extra level of play can probably be explained by the longer games, and therefore more need for accurate play.

Anyhow, a quick summary; it seems that balanced starting positions and critical early decisions create larger skill chains, more so than the size of the state space.

Iterations/Skill Level for 3x3 Games

Follow-Up: Hex Progression

GameLevelsits (last level)Converged toCellsGame LengthMean Branching FactorEst. State Space
Hex 3x31236472nd Wins96.736.6610^5.04
Hex 4x414327742nd Wins169.339.9110^12.53
Hex 5x522+213917???2515.0715.4010^22.99

A quick follow-on experiment; three sizes of Hex board with the swap rule in place. 3x3 and 4x4 seem to have similar levels of play, though the top level in 4x4 Hex requires a lot (10x) more iterations to attain. 10 hours wasn't enough to reach the top level of 5x5 hex, and there are a lot more levels to find; I have no idea why!

Levels for Hex on board sizes 3-5.

Follow-Up: Go (various Komi)

<
GameLevelsits (last level)Converged toCellsGame LengthMean Branching FactorEst. State Space
Go 7.5 komi81591st Wins912.245.0110^11.36
Go 8.5 komi97291st Wins911.775.0110^11.36
Go 9.0 komi5802Draw 911.885.0110^11.36
Go 9.5 komi1???2nd Wins9???5.0110^11.36

Follow-on experiment; how does komi affect the skill levels?

Effect of komi in 3x3 go.

Follow-Up: Breakthrough Progression

GameLevelsits (last level)Converged toCellsGame LengthMean Branching FactorEst. State Space
Breakthrough 3x377471st Wins96.365.0610^3.30
Breakthrough 3x4811741st Wins126.277.6810^4.15
Breakthrough 3x51147891st Wins156.5410.0710^5.18
Breakthrough 3x612104431st Wins186.4612.6610^6.73

In this set of tests, I made the board wider, but not deeper. In human terms, this hardly changes the complexity at all. From a computer perspective, though, the branching factor, maximum game length, and thus state space have increased; the game also gets a bit more dangerous* - the odds of randomly picking a good move decrease with the board width.

* On turn 1, moving any piece forwards wins; moving any piece diagonally loses, so for width N the proportion of winning moves is N/(2N-2).

Breakthrough, wider and wider.

Bonus: Slightly Larger Games

GameLevelsits (last level)Converged toCellsGame LengthMean Branching FactorEst. State Space
Dots and Boxes 3x391129481st player win1211.806.6010^8.68
Sim12307261st Wins1513.8410.8510^9.31
Tak12104061st Wins9 (stacking)18.0112.2110^21.94
2713+125922nd Wins9 (stacking)32.015.6010^12.96
Traffic Lights14+241691???9 (stacking)22.037.8310^18.23
Martian Tic Tac Toe18+9460???9 (stacking)43.239.2410^22.18

Just to contribute a little more to the heat death of the universe, I did some runs for some slightly larger games. Tak, Traffic Lights, and Martian Tic Tac Toe all get around the 3x3 board restriction by adding a 3rd dimension (or a mechanism equivalent to stacking), Dots and Boxes looks like a 3x3 grid but is played on the lines not the cells, so a 3x3 grid of dots actually gives 12 lines. The others are just small games I found lying around in Ai Ai :)

All small games.

Conclusions

In the introduction, I asked some questions...

Is the ladder an inherent property of the UCT algorithm, or of the game?

A little bit of both. There are several very low levels of play which seem consistent across most games. The differences between Hex with and without the swap rule, Hexapawn vs Breakthrough, and Go with various Komi show that the game's resolving power is very much relevant. Balanced openings, critical early decisions, and slow convergence all seem to contribute to longer skill ladders.

Is the ladder length related to the state complexity of the game?

The game rules are more important. 3x3 Go has a very high state space but surprisingly few levels. Hex with swap rule has many more levels than Hex without, despite similar state space sizes. However, given the same rule set on different board sizes, then yes; larger board, larger state space, more levels (seen in Hex, Breakthrough).

How does scaling a game affect the skill ladder?

Larger boards make for more levels - this was very apparent in Hex where it's clear that the game is more interesting, but also true in Breakthrough, even when a human would find no difference.

How does the swap rule affect the skill ladder?

In Hex, the swap rule drastically increased the number of skill levels, presumably because early decisions became more crucial.

What's the best game to play on a 3x3 grid?

On strictly a 3x3 board, Hex with the swap rule has the most skill levels. If you allow stacking then Martian Tic Tac Toe followed by Traffic Lights are best.

What's the best komi for Go on a 3x3 grid?

8.5 gives the longest skill chain; though a more correct answer may be that there is no komi that can result in a balanced game.

Paths Not Travelled, ...

I have focused here on the number of levels of play found, but there are a couple of other interesting points which I haven't analysed in detail. The first of these is, the number of iterations UCT needs to play at the top level. This is related to the number of levels, but there are exceptions. Breakthrough 3x3 has fewer levels than Go, Hex, and Achi but requires more iterations to play at the top level. Why? Also of interest (and not captured here at all), is the minimum amount of iterations required for UCT to play a perfect(ish) game.

Level Tables by Game

Hexapawn

MatchAIStrong WinsDrawsStrong Losses#GamesStrong Win%p1 Win%Draw%Game Length
0Random        
1UCT(its=2)631032795863.00 <= 65.87 <= 69.0046.00 <= 48.85 <= 52.000.004.71
5UCT(its=4)631034097162.00 <= 64.98 <= 68.0026.00 <= 28.53 <= 31.000.004.89
20UCT(its=17)631036299361.00 <= 63.54 <= 66.0012.00 <= 13.49 <= 16.000.005.36
99
UCT(its=31061)
370
0
370
740
46.00 <= 50.00 <= 54.00
0.00 <= 0.00 <= 1.00
0.00
5.68
100
UCT(its=31061)
370
0
370
740
46.00 <= 50.00 <= 54.00
0.00 <= 0.00 <= 1.00
0.00
5.95

BGG Page

Tic Tac Toe

MatchAIStrong WinsDrawsStrong Losses#GamesStrong Win%p1 Win%Draw%Game Length
0Random        
1UCT(its=2)55415326797462.00 <= 64.73 <= 68.0058.00 <= 61.45 <= 64.0015.717.51
4UCT(its=5)56613026395963.00 <= 65.80 <= 69.0055.00 <= 58.50 <= 62.0013.566.97
9UCT(its=10)57710727195563.00 <= 66.02 <= 69.0057.00 <= 60.58 <= 64.0011.206.62
18UCT(its=23)54317626798661.00 <= 64.00 <= 67.0068.00 <= 70.69 <= 73.0017.856.60
29UCT(its=67)44736717198561.00 <= 64.01 <= 67.0066.00 <= 68.68 <= 71.0037.267.14
49UCT(its=448)2876872099460.00 <= 63.43 <= 66.0062.00 <= 64.94 <= 68.0069.118.06
101
UCT(its=63645)
12
740
0
752
47.00 <= 50.80 <= 54.00
47.00 <= 50.80 <= 54.00
98.40
8.97
102
UCT(its=63645)
0
740
0
740
46.00 <= 50.00 <= 54.00
46.00 <= 50.00 <= 54.00
100.00
9.00

BGG Page

Achi

MatchAIStrong WinsDrawsStrong Losses#GamesStrong Win%p1 Win%Draw%Game Length
0Random        
1UCT(its=2)629330793964.08 <= 67.15 <= 70.0755.34 <= 58.52 <= 61.630.327.99
5UCT(its=6)630132095163.23 <= 66.30 <= 69.2359.07 <= 62.20 <= 65.220.117.35
11UCT(its=12)631033997062.00 <= 65.05 <= 67.9960.85 <= 63.92 <= 66.880.006.90
17UCT(its=21)631035398461.08 <= 64.13 <= 67.0661.70 <= 64.74 <= 67.660.006.92
23UCT(its=38)631035398461.08 <= 64.13 <= 67.0662.52 <= 65.55 <= 68.450.007.22
32UCT(its=89)631036699760.25 <= 63.29 <= 66.2359.54 <= 62.59 <= 65.540.008.41
43UCT(its=253)631034897961.40 <= 64.45 <= 67.3962.23 <= 65.27 <= 68.190.009.49
52UCT(its=596)631036499560.38 <= 63.42 <= 66.3570.02 <= 72.86 <= 75.540.0010.28
76
UCT(its=5874)
591
0
370
961
58.38 <= 61.50 <= 64.52
86.27 <= 88.45 <= 90.32
0.00
10.84
77
UCT(its=5874)
369
0
370
739
46.34 <= 49.93 <= 53.53
99.48 <= 100.00 <= 100.00
0.00
10.99

BGG Page

Go 3x3 7.5 Komi

MatchAIStrong WinsDrawsStrong Losses#GamesStrong Win%p1 Win%Draw%Game Length
0Random        
2UCT(its=3)631031094164.00 <= 67.06 <= 70.0050.00 <= 53.35 <= 57.000.0014.73
6UCT(its=7)631034797861.00 <= 64.52 <= 67.0048.00 <= 51.53 <= 55.000.0014.67
11UCT(its=12)631036099161.00 <= 63.67 <= 67.0053.00 <= 56.00 <= 59.000.0013.77
17UCT(its=21)631029792865.00 <= 68.00 <= 71.0052.00 <= 55.50 <= 59.000.0013.30
23UCT(its=38)631032795863.00 <= 65.87 <= 69.0058.00 <= 61.59 <= 65.000.0012.73
29UCT(its=67)631033596662.00 <= 65.32 <= 68.0067.00 <= 69.57 <= 72.000.0012.59
38UCT(its=159)631034597662.00 <= 64.65 <= 68.0075.00 <= 77.97 <= 80.000.0012.24
78
UCT(its=7180)
507
0
370
877
55.00 <= 57.81 <= 61.00
88.00 <= 90.08 <= 92.00
0.00
11.05
79
UCT(its=7180)
381
0
370
751
47.00 <= 50.73 <= 54.00
88.00 <= 90.41 <= 92.00
0.00
10.10

BGG Page

Go 3x3 8.5 Komi

MatchAIStrong WinsDrawsStrong Losses#GamesStrong Win%p1 Win%Draw%Game Length
0Random        
2UCT(its=3)631036499560.38 <= 63.42 <= 66.3548.25 <= 51.36 <= 54.450.0014.67
6UCT(its=7)631034397461.73 <= 64.78 <= 67.7247.38 <= 50.51 <= 53.650.0014.53
11UCT(its=12)631035698760.89 <= 63.93 <= 66.8751.69 <= 54.81 <= 57.890.0014.03
16UCT(its=19)631032295363.15 <= 66.21 <= 69.1454.97 <= 58.13 <= 61.230.0013.41
22UCT(its=35)631033496562.33 <= 65.39 <= 68.3256.77 <= 59.90 <= 62.940.0012.76
28UCT(its=61)631036399460.44 <= 63.48 <= 66.4260.54 <= 63.58 <= 66.520.0012.22
35UCT(its=119)631035999060.69 <= 63.74 <= 66.6770.70 <= 73.54 <= 76.190.0012.37
54UCT(its=729)631035598660.95 <= 64.00 <= 66.9379.21 <= 81.74 <= 84.030.0011.77
104
UCT(its=85567)
421
0
370
791
49.74 <= 53.22 <= 56.68
94.34 <= 95.95 <= 97.12
0.00
12.70
105
UCT(its=85567)
363
0
370
733
45.91 <= 49.52 <= 53.14
93.43 <= 95.23 <= 96.55
0.00
12.21

BGG Page

Go 3x3 9.0 Komi

MatchAIStrong WinsDrawsStrong Losses#GamesStrong Win%p1 Win%Draw%Game Length
0Random        
5UCT(its=6)38150011699760.25 <= 63.29 <= 66.2322.48 <= 25.08 <= 27.8650.1514.31
18UCT(its=24)3605418298361.09 <= 64.14 <= 67.0824.82 <= 27.52 <= 30.3955.0413.16
30UCT(its=74)3256126099760.25 <= 63.29 <= 66.2327.91 <= 30.69 <= 33.6261.3812.28
55UCT(its=802)275711999560.33 <= 63.37 <= 66.3032.81 <= 35.73 <= 38.7671.4611.88
104
UCT(its=85567)
66
728
6
800
50.29 <= 53.75 <= 57.18
42.08 <= 45.50 <= 48.96
91.00
11.52
105
UCT(its=85567)
12
718
11
741
46.48 <= 50.07 <= 53.66
44.87 <= 48.45 <= 52.05
96.90
13.49

BGG Page

Go 3x3 9.5 Komi

MatchAIStrong WinsDrawsStrong Losses#GamesStrong Win%p1 Win%Draw%Game Length
0Random        
51
UCT(its=548)
370
0
370
740
46.41 <= 50.00 <= 53.59
0.00 <= 0.00 <= 0.52
0.00
15.10
52
UCT(its=548)
370
0
370
740
46.41 <= 50.00 <= 53.59
0.00 <= 0.00 <= 0.52
0.00
16.28

BGG Page

Breakthrough 3x3

MatchAIStrong WinsDrawsStrong Losses#GamesStrong Win%p1 Win%Draw%Game Length
0Random        
1UCT(its=2)631030493564.00 <= 67.49 <= 70.0059.00 <= 62.14 <= 65.000.004.24
5UCT(its=6)631035098161.00 <= 64.32 <= 67.0064.00 <= 66.67 <= 70.000.004.40
14UCT(its=15)631036899960.00 <= 63.16 <= 66.0056.00 <= 59.36 <= 62.000.004.63
25UCT(its=43)631031694764.00 <= 66.63 <= 70.0046.00 <= 48.89 <= 52.000.005.13
36UCT(its=122)631036299361.00 <= 63.54 <= 66.0061.00 <= 64.05 <= 67.000.005.75
55UCT(its=747)631036199261.00 <= 63.61 <= 67.0084.00 <= 86.39 <= 88.000.006.36
119
UCT(its=333021)
369
0
370
739
46.00 <= 49.93 <= 54.00
99.00 <= 100.00 <= 100.00
0.00
6.26
120
UCT(its=333021)
369
0
370
739
46.00 <= 49.93 <= 54.00
99.00 <= 100.00 <= 100.00
0.00
6.03

BGG Page

Breakthrough 3x4

MatchAIStrong WinsDrawsStrong Losses#GamesStrong Win%p1 Win%Draw%Game Length
0Random        
1UCT(its=2)631034697762.00 <= 64.59 <= 68.0057.00 <= 60.18 <= 63.000.004.68
7UCT(its=8)631028491566.00 <= 68.96 <= 72.0056.00 <= 58.91 <= 62.000.004.44
13UCT(its=15)631034497562.00 <= 64.72 <= 68.0058.00 <= 61.03 <= 64.000.004.42
21UCT(its=31)631036299361.00 <= 63.54 <= 66.0056.00 <= 59.21 <= 62.000.004.76
31UCT(its=81)6310369100060.00 <= 63.10 <= 66.0051.00 <= 54.10 <= 57.000.005.46
51UCT(its=548)631035498561.00 <= 64.06 <= 67.0053.00 <= 55.84 <= 59.000.005.87
59UCT(its=1174)631033596662.00 <= 65.32 <= 68.0072.00 <= 74.74 <= 77.000.006.27
112
UCT(its=183420)
447
0
370
817
51.00 <= 54.71 <= 58.00
94.00 <= 95.23 <= 96.00
0.00
6.71
113
UCT(its=183420)
369
0
370
739
46.00 <= 49.93 <= 54.00
99.00 <= 100.00 <= 100.00
0.00
6.84

BGG Page

Breakthrough 3x5

MatchAIStrong WinsDrawsStrong Losses#GamesStrong Win%p1 Win%Draw%Game Length
0Random        
1UCT(its=2)631034197262.00 <= 64.92 <= 68.0060.00 <= 63.07 <= 66.000.004.98
7UCT(its=8)631036499560.00 <= 63.42 <= 66.0057.00 <= 60.20 <= 63.000.004.67
10UCT(its=11)631035498561.00 <= 64.06 <= 67.0054.00 <= 57.06 <= 60.000.004.33
16UCT(its=19)631031694764.00 <= 66.63 <= 70.0054.00 <= 57.55 <= 61.000.004.15
24UCT(its=41)631032795863.00 <= 65.87 <= 69.0060.00 <= 63.47 <= 66.000.004.04
30UCT(its=72)631036499560.00 <= 63.42 <= 66.0058.00 <= 61.21 <= 64.000.004.56
39UCT(its=170)631034998061.00 <= 64.39 <= 67.0047.00 <= 49.90 <= 53.000.005.50
64UCT(its=1847)631035498561.00 <= 64.06 <= 67.0044.00 <= 47.51 <= 51.000.005.66
70UCT(its=3271)631031094164.00 <= 67.06 <= 70.0055.00 <= 58.02 <= 61.000.005.89
74UCT(its=4789)631036199261.00 <= 63.61 <= 67.0081.00 <= 83.57 <= 86.000.006.54
120
UCT(its=384020)
394
0
362
756
49.00 <= 52.12 <= 56.00
97.00 <= 97.88 <= 99.00
0.00
6.85
121
UCT(its=384020)
369
0
370
739
46.00 <= 49.93 <= 54.00
99.00 <= 100.00 <= 100.00
0.00
6.85

BGG Page

Breakthrough 3x6

MatchAIStrong WinsDrawsStrong Losses#GamesStrong Win%p1 Win%Draw%Game Length
0Random        
2UCT(its=3)631031894963.43 <= 66.49 <= 69.4254.15 <= 57.32 <= 60.430.005.28
12UCT(its=13)631034297361.80 <= 64.85 <= 67.7950.10 <= 53.24 <= 56.350.004.67
18UCT(its=21)631033596662.26 <= 65.32 <= 68.2651.92 <= 55.07 <= 58.180.004.08
22UCT(its=31)631036299360.50 <= 63.54 <= 66.4862.24 <= 65.26 <= 68.150.003.87
30UCT(its=67)631035598660.95 <= 64.00 <= 66.9365.39 <= 68.36 <= 71.180.003.80
36UCT(its=118)631036499560.38 <= 63.42 <= 66.3561.60 <= 64.62 <= 67.530.004.36
41UCT(its=191)631033096162.60 <= 65.66 <= 68.6048.45 <= 51.61 <= 54.760.005.32
72UCT(its=3660)631034897961.40 <= 64.45 <= 67.3944.39 <= 47.50 <= 50.630.005.54
80UCT(its=7846)631031394463.78 <= 66.84 <= 69.7747.56 <= 50.74 <= 53.920.005.86
83UCT(its=10443)631033796862.13 <= 65.19 <= 68.1274.64 <= 77.38 <= 79.900.006.46
110
UCT(its=136907)
447
0
370
817
51.28 <= 54.71 <= 58.10
93.54 <= 95.23 <= 96.49
0.00
6.84
111
UCT(its=136907)
369
0
370
739
46.34 <= 49.93 <= 53.53
99.48 <= 100.00 <= 100.00
0.00
6.88

BGG Page

Three Men's Morris

MatchAIStrong WinsDrawsStrong Losses#GamesStrong Win%p1 Win%Draw%Game Length
0Random        
2UCT(its=3)6064927993464.00 <= 67.51 <= 70.0049.00 <= 52.52 <= 56.005.2510.01
6UCT(its=7)630136499560.00 <= 63.37 <= 66.0053.00 <= 56.33 <= 59.000.107.73
10UCT(its=11)631033196263.00 <= 65.59 <= 69.0059.00 <= 62.58 <= 66.000.006.63
19UCT(its=26)631035598661.00 <= 64.00 <= 67.0062.00 <= 65.52 <= 68.000.006.19
26UCT(its=50)631028691766.00 <= 68.81 <= 72.0061.00 <= 63.90 <= 67.000.006.70
31UCT(its=81)631035598661.00 <= 64.00 <= 67.0061.00 <= 63.69 <= 67.000.007.64
35UCT(its=118)6123732297162.00 <= 64.93 <= 68.0057.00 <= 59.99 <= 63.003.819.35
39UCT(its=173)52121924398361.00 <= 64.14 <= 67.0053.00 <= 56.21 <= 59.0022.2812.09
62UCT(its=1547)3595438798961.00 <= 63.75 <= 67.0048.00 <= 51.52 <= 55.0054.9015.25
87
UCT(its=16760)
71
740
0
811
51.00 <= 54.38 <= 58.00
44.00 <= 47.60 <= 51.00
91.25
19.16
88
UCT(its=16760)
0
740
0
740
46.00 <= 50.00 <= 54.00
46.00 <= 50.00 <= 54.00
100.00
20.00

BGG Page

Hex 3x3

MatchAIStrong WinsDrawsStrong Losses#GamesStrong Win%p1 Win%Draw%Game Length
0Random        
1UCT(its=2)631031294364.00 <= 66.91 <= 70.0051.00 <= 54.61 <= 58.000.007.45
4UCT(its=5)631033796862.00 <= 65.19 <= 68.0047.00 <= 49.90 <= 53.000.007.22
8UCT(its=9)631033496562.00 <= 65.39 <= 68.0049.00 <= 52.23 <= 55.000.006.97
13UCT(its=14)631035198261.00 <= 64.26 <= 67.0048v <= 51.32 <= 54.000.006.71
21UCT(its=31)631030994064.00 <= 67.13 <= 70.0043.00 <= 46.49 <= 50.000.006.70
29UCT(its=67)631036199261.00 <= 63.61 <= 67.0032.00 <= 34.58 <= 38.000.006.67
41UCT(its=209)631036699760.00 <= 63.29 <= 66.0029.00 <= 32.30 <= 35.000.006.77
48UCT(its=407)631031494564.00 <= 66.77 <= 70.0027.00 <= 30.05 <= 33.000.007.18
55UCT(its=794)631031194264.00 <= 66.99 <= 70.0035.00 <= 38.43 <= 42.000.007.48
59UCT(its=1162)631033997062.00 <= 65.05 <= 68.0028.00 <= 30.72 <= 34.000.007.19
71UCT(its=3647)631036499560.00 <= 63.42 <= 66.0011.00 <= 13.37 <= 16.000.006.73
85
UCT(its=13851)
370
0
370
740
46.00 <= 50.00 <= 54.00
0.00 <= 0.00 <= 1.00
0.00
6.82
86
UCT(its=13851)
370
0
370
740
46.00 <= 50.00 <= 54.00
0.00 <= 0.00 <= 1.00
0.00
7.05

BGG Page

Hex 3x3 (No Swap)

MatchAIStrong WinsDrawsStrong Losses#GamesStrong Win%p1 Win%Draw%Game Length
0Random        
1UCT(its=2)631033296362.47 <= 65.52 <= 68.4652.40 <= 55.56 <= 58.670.007.37
4UCT(its=5)631035798860.82 <= 63.87 <= 66.8046.59 <= 49.70 <= 52.810.007.03
8UCT(its=9)631032195263.22 <= 66.28 <= 69.2149.66 <= 52.84 <= 55.990.006.74
15UCT(its=18)631031194263.92 <= 66.99 <= 69.9155.21 <= 58.39 <= 61.490.006.48
23UCT(its=38)631035898960.76 <= 63.80 <= 66.7462.91 <= 65.93 <= 68.810.006.16
33UCT(its=98)631036199260.57 <= 63.61 <= 66.5568.17 <= 71.07 <= 73.800.005.88
46UCT(its=337)631031794863.50 <= 66.56 <= 69.4978.06 <= 80.70 <= 83.080.005.58
118
UCT(its=321690)
403
0
370
773
48.61 <= 52.13 <= 55.64
96.51 <= 97.80 <= 98.62
0.00
5.36
119
UCT(its=321690)
369
0
370
739
46.34 <= 49.93 <= 53.53
99.48 <= 100.00 <= 100.00
0.00
5.18

BGG Page

Hex 4x4

MatchAIStrong WinsDrawsStrong Losses#GamesStrong Win%p1 Win%Draw%Game Length
0Random        
1UCT(its=2)631030893964.00 <= 67.20 <= 70.0054.00 <= 57.61 <= 61.000.0013.19
5UCT(its=6)631028891966.00 <= 68.66 <= 72.0052.00 <= 55.60 <= 59.000.0012.50
9UCT(its=10)631036199261.00 <= 63.61 <= 67.0054.00 <= 57.16 <= 60.000.0011.99
14UCT(its=15)631032996063.00 <= 65.73 <= 69.0056.00 <= 59.48 <= 63.000.0011.47
18UCT(its=21)631036699760.00 <= 63.29 <= 66.0056.00 <= 59.18 <= 62.000.0011.01
23UCT(its=34)631035498561.00 <= 64.06 <= 67.0054.00 <= 57.46 <= 61.000.0010.24
29UCT(its=61)631034097162.00 <= 64.98 <= 68.0053.00 <= 56.54 <= 60.000.009.54
37UCT(its=130)631031194264.00 <= 66.99 <= 70.0052.00 <= 55.63 <= 59.000.009.10
45UCT(its=279)631033196263.00 <= 65.59 <= 69.0054.00 <= 57.38 <= 60.000.008.77
55UCT(its=724)631032095163.00 <= 66.35 <= 69.0048.00 <= 51.00 <= 54.000.008.59
63UCT(its=1552)631036499560.00 <= 63.42 <= 66.0037.00 <= 40.10 <= 43.000.008.35
72UCT(its=3660)631033696762.00 <= 65.25 <= 68.0024 .00<= 26.37 <= 29.000.008.59
95UCT(its=32774)631036899960.00 <= 63.16 <= 66.0011.00 <= 13.31 <= 16.000.009.33
102
UCT(its=63868)
372
0
370
742
47.00 <= 50.13 <= 54.00
0.00 <= 0.13 <= 1.00
0.00
9.90
103
UCT(its=63868)
370
0
370
740
46.00 <= 50.00 <= 54.00
0.00 <= 0.00 <= 1.00
0.00
10.00

BGG Page

Hex 5x5

MatchAIStrong WinsDrawsStrong Losses#GamesStrong Win%p1 Win%Draw%Game Length
0Random        
1UCT(its=2)631032996063.00 <= 65.73 <= 69.0048.00 <= 50.94 <= 54.000.0020.80
5UCT(its=6)631033596662.00 <= 65.32 <= 68.0047.00 <= 49.90 <= 53.000.0020.01
9UCT(its=10)631034297362.00 <= 64.85 <= 68.0046.00 <= 48.72 <= 52.000.0019.53
15UCT(its=16)631026889967.00 <= 70.19 <= 73.0044.00 <= 47.27 <= 51.000.0018.91
21UCT(its=22)631035298361.00 <= 64.19 <= 67.0042.00 <= 44.66 <= 48.000.0018.19
26UCT(its=30)631034397462.00 <= 64.78 <= 68.0046.00 <= 49.49 <= 53.000.0017.28
29UCT(its=40)631036599660.00 <= 63.35 <= 66.0046.00 <= 49.10 <= 52.000.0016.41
34UCT(its=65)631029993065.00 <= 67.85 <= 71.0047.00 <= 50.54 <= 54.000.0015.34
39UCT(its=104)631034497562.00 <= 64.72 <= 68.0051.00 <= 54.46 <= 58.000.0014.67
44UCT(its=168)631030893964.00 <= 67.20 <= 70.0050.00 <= 52.93 <= 56.000.0013.50
49UCT(its=271)631035798861.00 <= 63.87 <= 67.0047.00 <= 49.70 <= 53.000.0012.92
55UCT(its=480)631035198261.00 <= 64.26 <= 67.0045.00 <= 48.27 <= 51.000.0012.68
61UCT(its=850)631033796862.00 <= 65.19 <= 68.0042.00 <= 44.73 <= 48.000.0012.38
70UCT(its=2004)631032996063.00 <= 65.73 <= 69.0037.00 <= 39.90 <= 43.000.0011.92
83UCT(its=6920)631036099161.00 <= 63.67 <= 67.0032.00 <= 34.81 <= 38.000.0011.85
91UCT(its=14834)631034097162.00 <= 64.98 <= 68.0032.00 <= 34.50 <= 38.000.0011.98
95UCT(its=21718)631034897961.00 <= 64.45 <= 67.0038.00 <= 40.96 <= 44.000.0013.08
99UCT(its=31797)631035898961.00 <= 63.80 <= 67.0040.00 <= 42.87 <= 46.000.0014.47
106UCT(its=61964)631036499560.00 <= 63.42 <= 66.0046.00 <= 48.74 <= 52.000.0015.21
111UCT(its=99794)631036599660.00 <= 63.35 <= 66.0066.00 <= 68.57 <= 71.000.0015.30
119UCT(its=213917)631035398461.00 <= 64.13 <= 67.0060.00 <= 63.11 <= 66.000.0015.07
122
UCT(its=284723)
616
0
370
986
59.00 <= 62.47 <= 65.00
45.00 <= 48.38 <= 51.00
0.00
14.03
123
UCT(its=284723)
360
0
370
730
46.00 <= 49.32 <= 53.00
34.00 <= 37.95 <= 42.00
0.00
13.42

BGG Page

Tak

MatchAIStrong WinsDrawsStrong Losses#GamesStrong Win%p1 Win%Draw%Game Length
0Random        
2UCT(its=3)55515220691366.00 <= 69.11 <= 72.0049.00 <= 52.25 <= 55.0016.6518.16
9UCT(its=10)5927831698661.00 <= 64.00 <= 67.0049.00 <= 52.33 <= 55.007.9116.56
14UCT(its=16)6094324389567.00 <= 70.45 <= 73.0049.00 <= 51.79 <= 55.004.8013.39
18UCT(its=23)6133534899660.00 <= 63.30 <= 66.0049.00 <= 52.16 <= 55.003.5110.86
24UCT(its=41)6212034398461.00 <= 64.13 <= 67.0057.00 <= 59.86 <= 63.002.038.83
36UCT(its=130)631034397462.00 <= 64.78 <= 68.0066.00 <= 68.79 <= 72.000.007.25
43UCT(its=253)627835999460.00 <= 63.48 <= 66.0074.00 <= 76.56 <= 79.000.807.14
50UCT(its=493)627835398861.00 <= 63.87 <= 67.0080.00 <= 82.59 <= 85.000.818.49
59UCT(its=1162)628635198561.00 <= 64.06 <= 67.0081.00 <= 83.45 <= 86.000.6111.65
68UCT(its=2740)627833997462.00 <= 64.78 <= 68.0080.00 <= 82.55 <= 85.000.8215.75
82UCT(its=10406)6231635599460.00 <= 63.48 <= 66.0084.00 <= 85.81 <= 88.001.6118.01
85
UCT(its=13851)
387
3
369
759
48.00 <= 51.19 <= 55.00
96.00 <= 97.56 <= 98.00
0.40
18.86
86
UCT(its=13851)
358
9
366
733
46.00 <= 49.45 <= 53.00
97.00 <= 98.29 <= 99.00
1.23
18.76

BGG Page

Dots and Boxes (3x3 dots)

MatchAIStrong WinsDrawsStrong Losses#GamesStrong Win%p1 Win%Draw%Game Length
0Random        
1UCT(its=2)56513117487069.00 <= 72.47 <= 75.0055.00 <= 58.79 <= 62.0015.0611.53
8UCT(its=9)55215728999860.00 <= 63.18 <= 66.0067.00 <= 69.59 <= 72.0015.7311.31
25UCT(its=46)47231719598461.00 <= 64.08 <= 67.0058.00 <= 60.82 <= 64.0032.2211.34
35UCT(its=118)43738716899261.00 <= 63.56 <= 66.0067.00 <= 69.61 <= 72.0039.0111.51
45UCT(its=307)43439316699360.00 <= 63.49 <= 66.0067.00 <= 69.94 <= 73.0039.5811.53
59UCT(its=1164)35854597100060.00 <= 63.05 <= 66.0063.00 <= 65.95 <= 69.0054.5011.72
80UCT(its=8615)3495636597761.00 <= 64.53 <= 67.0068.00 <= 70.57 <= 73.0057.6311.65
107UCT(its=112948)44736815797262.00 <= 64.92 <= 68.0078.00 <= 81.07 <= 83.0037.8611.80
108
UCT(its=124243)
369
24
358
751
47.00 <= 50.73 <= 54.00
97.00 <= 98.40 <= 99.00
3.20
11.94
109
UCT(its=124243)
357
12
364
733
46.00 <= 49.52 <= 53.00
98.00 <= 99.18 <= 100.00
1.64
11.95

BGG Page

Sim

MatchAIStrong WinsDrawsStrong Losses#GamesStrong Win%p1 Win%Draw%Game Length
0Random        
1UCT(its=2)631031694763.57 <= 66.63 <= 69.5634.87 <= 37.91 <= 41.040.0010.01
2UCT(its=3)631035999060.69 <= 63.74 <= 66.6737.59 <= 40.61 <= 43.700.0011.17
7UCT(its=8)631034397461.73 <= 64.78 <= 67.7246.56 <= 49.69 <= 52.830.0012.39
15UCT(its=17)631034797861.47 <= 64.52 <= 67.4644.94 <= 48.06 <= 51.190.0013.33
24UCT(its=39)631035498561.02 <= 64.06 <= 67.0042.80 <= 45.89 <= 49.010.0013.59
32UCT(its=83)631030093164.71 <= 67.78 <= 70.7034.01 <= 37.06 <= 40.210.0013.72
40UCT(its=179)631032996062.67 <= 65.73 <= 68.6629.71 <= 32.60 <= 35.630.0013.93
48UCT(its=383)631033296362.47 <= 65.52 <= 68.4626.80 <= 29.60 <= 32.550.0014.01
56UCT(its=821)631033096162.60 <= 65.66 <= 68.6020.94 <= 23.52 <= 26.300.0014.08
72UCT(its=3775)631036299360.50 <= 63.54 <= 66.4812.45 <= 14.50 <= 16.830.0013.83
94UCT(its=30726)631034797861.47 <= 64.52 <= 67.4615.14 <= 17.38 <= 19.880.0013.84
106
UCT(its=96431)
446
0
370
816
51.23 <= 54.66 <= 58.04
3.41 <= 4.66 <= 6.33
0.00
13.70
107
UCT(its=96431)
370
0
370
740
46.41 <= 50.00 <= 53.59
0.00 <= 0.00 <= 0.52
0.00
13.58

BGG Page

Martian Tic Tac Toe

MatchAIStrong WinsDrawsStrong Losses#GamesStrong Win%p1 Win%Draw%Game Length
0Random        
2UCT(its=3)631034197261.86 <= 64.92 <= 67.8546.97 <= 50.10 <= 53.240.0034.76
10UCT(its=11)631035198261.21 <= 64.26 <= 67.1949.42 <= 52.55 <= 55.650.0025.00
14UCT(its=16)631031794863.50 <= 66.56 <= 69.4952.62 <= 55.80 <= 58.930.0018.59
18UCT(its=23)631035598660.95 <= 64.00 <= 66.9357.36 <= 60.45 <= 63.450.0013.48
26UCT(its=50)631036699760.25 <= 63.29 <= 66.2354.89 <= 57.97 <= 61.000.0011.18
31UCT(its=81)631036199260.57 <= 63.61 <= 66.5556.69 <= 59.78 <= 62.790.0012.85
35UCT(its=118)631030393464.49 <= 67.56 <= 70.4851.40 <= 54.60 <= 57.770.0016.12
38UCT(its=157)631026289367.59 <= 70.66 <= 73.5549.58 <= 52.86 <= 56.110.0024.26
41UCT(its=209)631032996062.67 <= 65.73 <= 68.6647.15 <= 50.31 <= 53.470.0029.99
45UCT(its=306)631036699760.25 <= 63.29 <= 66.2348.05 <= 51.15 <= 54.250.0035.16
50UCT(its=493)631031995063.36 <= 66.42 <= 69.3545.26 <= 48.42 <= 51.600.0037.17
57UCT(its=960)631033196262.53 <= 65.59 <= 68.5347.78 <= 50.94 <= 54.080.0035.95
65UCT(its=2059)631031094163.99 <= 67.06 <= 69.9845.70 <= 48.88 <= 52.080.0034.96
70UCT(its=3316)631032195263.22 <= 66.28 <= 69.2145.89 <= 49.05 <= 52.230.0037.00
74UCT(its=4855)631036799860.19 <= 63.23 <= 66.1647.00 <= 50.10 <= 53.200.0039.20
77UCT(its=6462)6310369100060.06 <= 63.10 <= 66.0451.60 <= 54.70 <= 57.760.0041.03
81UCT(its=9460)631030393464.49 <= 67.56 <= 70.4852.04 <= 55.25 <= 58.410.0043.23
83
UCT(its=11447)
440
0
370
810
50.88 <= 54.32 <= 57.72
54.72 <= 58.15 <= 61.50
0.00
44.87
84
UCT(its=11447)
336
0
370
706
43.93 <= 47.59 <= 51.28
57.40 <= 61.05 <= 64.58
0.00
47.46

BGG Page

Traffic Lights

MatchAIStrong WinsDrawsStrong Losses#GamesStrong Win%p1 Win%Draw%Game Length
0Random        
2UCT(its=3)631030193264.63 <= 67.70 <= 70.6347.76 <= 50.97 <= 54.160.0019.35
7UCT(its=8)631026089167.75 <= 70.82 <= 73.7149.80 <= 53.09 <= 56.340.0018.37
11UCT(its=12)631035098161.27 <= 64.32 <= 67.2645.41 <= 48.52 <= 51.650.0018.06
17UCT(its=21)631035598660.95 <= 64.00 <= 66.9345.98 <= 49.09 <= 52.210.0017.64
23UCT(its=38)631033496562.33 <= 65.39 <= 68.3247.21 <= 50.36 <= 53.510.0018.20
27UCT(its=55)631032996062.67 <= 65.73 <= 68.6650.48 <= 53.65 <= 56.780.0019.19
30UCT(its=73)631034998061.34 <= 64.39 <= 67.3252.28 <= 55.41 <= 58.490.0020.45
43UCT(its=253)631036099160.63 <= 63.67 <= 66.6151.88 <= 54.99 <= 58.070.0021.37
66UCT(its=2265)631035398461.08 <= 64.13 <= 67.0663.14 <= 66.16 <= 69.050.0021.91
79UCT(its=7818)631036299360.50 <= 63.54 <= 66.4860.20 <= 63.24 <= 66.190.0021.88
93UCT(its=29691)631032595662.94 <= 66.00 <= 68.9465.29 <= 68.31 <= 71.180.0021.97
102UCT(its=70009)6310369100060.06 <= 63.10 <= 66.0467.80 <= 70.70 <= 73.440.0022.07
115UCT(its=241691)631035999060.69 <= 63.74 <= 66.6769.45 <= 72.32 <= 75.020.0022.03
119
UCT(its=353859)
405
0
370
775
48.74 <= 52.26 <= 55.75
74.75 <= 77.81 <= 80.59
0.00
22.01
120
UCT(its=353859)
335
0
370
705
43.85 <= 47.52 <= 51.21
75.70 <= 78.87 <= 81.72
0.00
21.98

BGG Page

27

MatchAIStrong WinsDrawsStrong Losses#GamesStrong Win%p1 Win%Draw%Game Length
0Random        
1UCT(its=2)5888623891266.12 <= 69.19 <= 72.1049.17 <= 52.41 <= 55.649.4323.81
4UCT(its=5)5849431098860.82 <= 63.87 <= 66.8044.17 <= 47.27 <= 50.389.5123.87
11UCT(its=12)5898431198461.08 <= 64.13 <= 67.0645.67 <= 48.78 <= 51.908.5424.24
18UCT(its=23)59278330100060.06 <= 63.10 <= 66.0447.41 <= 50.50 <= 53.597.8024.78
26UCT(its=50)5937532499260.52 <= 63.56 <= 66.5045.44 <= 48.54 <= 51.657.5625.01
36UCT(its=130)6006230696862.13 <= 65.19 <= 68.1243.37 <= 46.49 <= 49.646.4025.25
45UCT(its=306)6015933699660.26 <= 63.30 <= 66.2439.88 <= 42.92 <= 46.025.9226.09
54UCT(its=722)5996329095263.16 <= 66.23 <= 69.1640.22 <= 43.33 <= 46.506.6226.43
61UCT(its=1406)5947333099760.20 <= 63.24 <= 66.1843.11 <= 46.19 <= 49.297.3227.61
70UCT(its=3316)6065033398960.76 <= 63.80 <= 66.7444.02 <= 47.12 <= 50.235.0628.42
77UCT(its=6462)6143433798561.02 <= 64.06 <= 67.0041.49 <= 44.57 <= 47.693.4530.38
84UCT(its=12592)6212035599660.31 <= 63.35 <= 66.2929.01 <= 31.83 <= 34.792.0132.01
95
UCT(its=35926)
459
66
337
862
53.75 <= 57.08 <= 60.34
13.71 <= 16.01 <= 18.61
7.66
31.97
96
UCT(its=35926)
340
91
325
756
47.43 <= 50.99 <= 54.54
9.85 <= 11.97 <= 14.48
12.04
32.37

BGG Page