UCT Skill Ladders for Small Games

Contents

• Contents
• Introduction
• The Algorithm
• Start Simple
• Comparison of 3x3 Games
• Follow-Up: Hex Progression
• Follow-Up: Go (various Komi)
• Follow-Up: Breakthrough Progression
• Bonus: Slightly Larger Games
• Conclusions
• UCT Outcome Chains
• Level Tables by Game
• 27
• Achi
• Breakthrough
• Chessline
• Claustrophobia (7 Spots)
• Dao
• Dodo
• Dots and Boxes (3x3 dots)
• Go
• One Eye Go 3x3 1.0 Komi
• Hex
• Hexapawn
• Martian Tic Tac Toe
• Proteus
• Sim
• Tak
• Three Men's Morris
• Tic Tac Chess
• Tic Tac Toe
• Traffic Lights

Update History

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 better defined 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, impossible. 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 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. There is more information on how reproducible the results are with various parameters here.

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

• UCT converges to perfect play given sufficient time (as you'll see in the results section, however, convergence is not necessarily fast.)
• Evaluation is done through random playouts, so there is no requirement for heuristics which would introduce human bias.
• The algorithm is simple and easily understood.
• Unlike, say, AlphaBeta search, UCT can be interrupted at any point without affecting the results; allowing fine control over resources invested.
• Anthropomorphising like mad, I've always thought of UCT as being almost human in its approach to lookahead. It considers one good move for a while (the Exploitation part of the algorithm), but will get a little worried after a while and look at the other moves for a while (Exploration) just in case it's missing something better.

Given my limited resources, computationally speaking, I have focused here on very small games, generally 3x3. Not all of these games are of equal complexity, though. In a game like Tic Tac Toe, pieces are undifferentiated and once placed on the board they never move; this is about as simple as it can get. Other games may allow stacking, differentiated pieces, or scoring (e.g. go); each of which effectively increases the amount of information to be tracked. For this reason, I have divided the games into three categories, based on the number of bits required to store the game state and the board size, as you'll see below. By way of example, Tic Tac Toe has 9 cells, each cell requires 2 bits (holding three states; empty/black/white), for 18 bits total (player to move can be calculated by counting the pieces on the board).

So, questions I try to answer here:

• Is the ladder an inherent property of the UCT algorithm, or of the game?
• Is the ladder related to the state complexity of the game?
• How does scaling a game affect the skill ladder?
• How does the swap rule affect the skill ladder?
• What's the best game to play on a 3x3 grid?
• What's the best komi for Go on a 3x3 grid?

The Algorithm

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.

Comparison of 3x3 Games

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.

It may seem counterintuitive, but I had a little trouble defining a 3x3 game. A lot of interesting small games get around the limited state space of a 3x3 game, in a variety of ways which I will discuss later. As a result, I have split my results into strict 3x3 games and larger games. I have defined 'strict' a following these rules:

• No stacking
• No differentiation between pieces
• All information is visible on the board, except for player-to-move

A useful measure of the strictness is the number of bits required to represent the state space (State Bits from now on), which is marked in the summary tables for reference.

Strict 3x3 Games

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.

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.

Bonus: Slightly Larger Games

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

Game	Levels	its (last level)	Converged to	Cells	Game Length	Mean Branching Factor	Est. State Space	State Bits	Notes
One Eye Go 3x3 (1.0 komi)	6	90	Draw	9	9.07	5.61	10^7.44	27	Scoring
Dao	8	8615	Draw	16	30	10.61	10^29.96	33	4x4
Go 3x3 (7.5 komi)	8	159	1st Wins	9	12.24	5.01	10^11.36	27	Scoring
Dots and Boxes 3x3	9	112948	1st player win	12	11.80	6.60	10^8.68	21	12 Lines, 4 Centres
Tic Tac Chess	10	3835	Draw	9	13.76	11.35	10^9.96	28	Differentiated pieces
Claustrophobia	11	9234	1st player win	7	19.26	3.62	10^9.17	36	14 Lines, 6 Dots
Sim	12	30726	1st Wins	15	13.84	10.85	10^9.31	30	6 Dots, 15 lines
Tak	12	10406	1st Wins	9 (stacking)	18.01	12.21	10^21.94	57	Stacking and differentiated pieces
27	13+	12592	2nd Wins	9 (stacking)	32.01	5.60	10^12.96	53	Stacking
Traffic Lights	14+	241691	???	9	22.03	7.83	10^18.23	19	Differentiated pieces
Traffic Lights 3x4	13+	471812	???	12	27.95	10.60	10^24.11	25	3x4, Differentiated pieces
Proteus	13+	18530	???	9	23.87	22.77	10^28.17	73	Differentiated pieces, multipurpose cells
Martian Tic Tac Toe	18+	9460	???	9	43.23	9.24	10^22.18	28	Differentiated pieces
Dodo	12+	3014	???	19	41.32	4.18	10^23.45	33	Size 3 hexboard

Follow-Up: Hex Progression

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!

Follow-Up: Go (various Komi)

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.

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

Follow-Up: Breakthrough Progression

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

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.

UCT Outcome Chains

The graphs in this section show how the first player wins, draws, and losses change as the AI strength increases. As a rule of thumb, you'll see a steady progression towards the game theoretical vlaue; but some games can show surprising trends. Chessline is a particularly interesting example - the combination shown looks like a win for the first player until the AI reaches a strength, after which the second player can force a draw. Note that these results are reproducible and not just features of the RNG.

Level Tables by Game

Key

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.

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.

The other tables and diagrams are hidden below, so they don't scare the natives. Click on the arrow to expand them!