# What kind of strategies are in this game?

1  2
• Created Monday, January 16th 2017 @ 23:47:34

I've been watching some games with UTTT in lockdown, and I was just curious what kind of things/strategies you look for. I can't really tell who is winning or losing. Like in the Tetris competition, a lot of players went for a T-spin strategy. What do you go for in UTTT?

• Created Tuesday, January 17th 2017 @ 06:00:59

I have no idea what to really look for when watching games, which is why I chose to use Monte Carlo Tree Search. In general, I think my bot struggles a little bit with moves that allow the opponent to play anywhere. Sometimes my bot overvalues them because it hasn't had enough time to deeply explore (because of state explosion), and mostly-random playouts have lots of draws.

• Created Tuesday, January 17th 2017 @ 18:36:29

I also had no idea. And I also experimented with MCTS, but with no good results. But I ended up with something MCTS-like anyway.

For every possible 3x3 square I precalculate the probilities { X wins, O wins, draw } by randomly filling that square until the 3x3 game ends.

Then I use a plain old alpha beta search with an evaluation function that is (almost) completely based on calculation of the overall probability(X wins on overall board) - probability(O wins on overall board).

And probability(Player wins on overall board) is calculated by combining the probabilities of the individual 9 3x3 squares at game state. I only do an estimation which is not correct in a mathematical sense, but it was the best I could come up with, since I started very late on this competition.

It seems that TParty too often wants to win each 3x3 square by ending on the middle square, which does not seem to be a good strategy. But I had no time to come up with anything better.

I think it is quite cool that to my surprise TParty sometimes happily sacrifices some 3x3 squares in the beginning so it has more stones than the opponent on the other squares; I guess such strategies are hard to implement in a good way using heuristic evaluation functions.

• Updated Wednesday, January 18th 2017 @ 00:10:58

Additional information on my bot. I was oscliating as high as #12 and as low as #30 with the same code (tight competition!).

Started with standard MCTS with fully random rollouts. Then I started making modifications, mostly discovered through this survey paper

### Optimizations

• Optimizations took it from doing 9k simulations per turn to 90k (eating a bit into the time bank). Just the added simulations moved my bot up the rankings quite a bit. The biggest single optimization was using bitboards instead of arrays of individual cells. Each bitboard represents a single 3x3 square, and generally represents one player's pieces in that square (though I use it for keeping track of dead boards and boards that are 'legal' to play on).

### Playout improvements:

• Moves are checked to see if they result in an immediate victory. If so, that is played instead of a random move. Small win rate improvement.
• Implemented "Last good reply with forgetting-2" paper. Basically, it keeps a table of "responses" that happened to work out well in other random playouts, and tries those again the next time the same move sequence comes up. With the two layer one, it's like "I did this, then you did that, so following the table, I should do X, since it won last time". The "forgetting" part is to remove items when they don't pan out.

### Tree improvements

• Implemented MCTS-Solver. Now each node of the tree contains information on guaranteed win/loss instead of just statistics/expected values. As the tree reaches end game states, it backpropogates guaranteed win/loss information. It usually knows how the game to end around 10-16 moves out. Before this, the bot could sometimes make mistakes late in the game.
• Implemented a history heuristic table that biases node selection in favor of better performing positions globally. So each player has its own global table for keeping track of the overall expected value of a given cell. These biases taper off as the number of simulations at a node increase.
• Created an opening playbook that sets the 'optimal' move for the first 7 moves (4 for the first player, 3 for the second player). This was built by simulating 300k moves for each position in the playbook and recording the best move. I wanted to do a million per move, but ran out of time to precompute it. Still, it allows me to not waste any of the timebank on the first few rounds, thus allowing me to spend more of that time later. This was my last improvement, we'll see how it does!

Some of the improvements (like the history heuristic and the "Last good reply with forgetting") showed significant improvements versus previous versions of my bot, but didn't really show much improvement versus the other bots on the ladder.

• Updated Tuesday, January 24th 2017 @ 13:28:44

I ended it up with MCTS solution with:

• roll outs with a search for a winning move
• sure win (or loss) back propagation
• 2-moves opening book

I also tried a MCTS guided by a neural network (NN), but it wasn't as good as as my MCTS bot.

### 1. Evaluate all the moves

• X: a vector representing both players boards before and after the move
• y: 1 if the player that moved won the game else -1 (values are not important here, it represents 2 classes)

The NN acts as a classifier ("Is this move a win ?"), 2 hidden layers (400/200), relu activations, softmax output, no dropout, binary cross entropy, a few epochs. When expanding a node in MCTS I would evaluate the odds for each possible move. I would keep only the promising nodes (win probability > 50%). If no nodes are good I would fall back to a classic MCTS and try them all.

Three weeks before lock down I discovered that my dataset had a serious flaw, it couldn't be fixed. I was able to recreate only 40% of it. At first the NN had a 70% accuracy, by adding more data it reached 75% of accuracy.

The MCTS-NN bot won about 30/35% of the games against my MCTS bot.

I also tried adding the winning probability to the MCTS UCT function and keeping all the nodes in the tree (win ratio + acoefficient x NN prediction + explorationfactor x sqrt(...)). Not a big success neither.

### 2. Predict the proper cell to play in

Here I tried to guess the best cell to play in (when it's limited to a 3x3 board, not when it can play anywhere on the 9x9 board). About the same NN architecture (with categorical cross entropy). I kept the winning moves to build the dataset:

• X: a vector representing both players boards before and after the move
• y: cell position in a 3x3 board

At best I had a 40% accuracy, but I didn't have time to check in which condition the NN was predicting the proper cell (if it has 5 free cells to play in, a random bot would have a 20% chance of making the proper move and then a 40% accuracy isn't that good). But by selecting the top 4 probabilities (for 9 potential moves) I had about 80/85% chance of studying the actual best move, which is good for reducing the branching factor of the MCTS. Unfortunately I couldn't implement it and test it before the lock down.

### My conclusion

This was a great project ! Thanks TheAiGames for this opportunity :-)

I got too enthusiast and I overlooked the dataset quality control... Otherwise this is very promising. NNs are powerful tools and it can be easily added to a pre-existing algorithms:

• sort nodes (killer moves)
• evaluation functions
• branching factor reduction
• be an other heuristic for the evaluation function

Drawbacks:

• I used Keras/Theano (Python stuff) from which I had to extract layers' weights and put them into java classes which is a real pain (try putting thousands of constants in a class and you will get an error about bytecode being too big...)
• Coding NN stuff in java (boooooring)
• Zipped bot weight must be < 2 Mo, something like 200 000 coefficients at max for the layers (I didn't try to cast floats to get rid of doubles)
• I used top 10 and top 20 players games of the leaderboard to build my dataset (thank you guys), because we were a lot to play there wasn't that much games every day (riddles.io here I come).
• Slow ! : big fat NN are great, precise and all, but mine were just to slow for this competition... Also I didn't worked with bitboards to speed up the MCTS roll outs.

I could have done:

• use games against strong MCTS (ie: MCTS with a lot of time to compute) to generate data
• balance between NN's accuracy and size (for the speed issue)
• experiment more with adding the NN prediction to the UC Tfunction
• use bitboards

I've read and learned a lot thanks to this competition, thanks again everybody.

• Created Tuesday, January 24th 2017 @ 20:54:44

@DaFish @ChickenCoop @Lysk

Did you pre-calculate your MCTS data and somehow store it in your bot's zip file? If so, how (this was a major problem when I tried to build a bot)? Or did you calculate moves during the game? Isn't that extremely computationally expensive?

• Updated Wednesday, January 25th 2017 @ 13:48:42

@QuestionCactus

The tree is computed and developed during the game at each turn. It is indeed a lot of computations, that's why optimizing rollouts is so important (bitboard, winning move...) and also time management.

From other post you'll see players talking about N tree nodes tested per seconds, for a given bot: the higher the better (for both MCTS and alpha beta pruning).

• Created Friday, January 27th 2017 @ 03:49:16

Wow, really cool to hear about your guys strategies. So many took the Monte Carlo route? Interesting :)

I wonder if anyone took a heuristic approach. I'm excited to watch the competition!

• Updated Friday, January 27th 2017 @ 21:07:28

I think most did minimax varients, just us MCTS users are pretty vocal :P

There is another thread before (here) where several top users share how deep their bots are searching. I'm hoping that more users will share in depth details of their bots.

• Created Monday, January 30th 2017 @ 07:45:43

My approach is very similar to Dafish's, I also had a score based on win probability. And a number of other improvements:

• The most interesting one was that I refined the scoring function using reinforcement learning. The model was very simple for performance reasons, I used a simple linear logistic regression to predict wins where the features was the scoring function from above and one value per cell indicating who played on it. After a day of training, it turned out to be surprisingly positive, my trained bot was beating the original one about 60% of time. The speed impact was very small which was nice. But I had a suspicion that I kinda overfit against my own bot because of the way I trained it, I did this toward the very end of the contest, so it was hard to tell how much it improved over other bots. I didn't investigate further

Other traditional improvements to minimax that I did:

• Transposition table
• Move sorting based on best moves found
• Some limited bitboard, mostly just for lookup a table of 3x3 probabilities, I couldn't find many uses for it
• Quiescent search. I only included capture moves after mac depth was reached. The horizon effect was still very strong and I couldn't find a better approach to it
• Pruning of very bad moves -- this one was pretty strange, I was expecting to make the search faster with this but it didn't and was still very positive
• Opening table from from first 2 plies plus other common positions against other bots, normalized for rotation and transposition of the board.
• Pondering
• Updated Monday, January 30th 2017 @ 15:50:01

It is nice to see others have the same strategy as I have. I also used a probability based score. I calculated the score of each combination of 3x3 boards by assuming that each empty square has an equal probability to stay empty, be occupied by O or be occupied by X. The score of a players is then simply the sum of each winning possiblity in the large board, where the winning posibilty is the product of winning each of the small boards needed. Due to the inclusion-exclusion principle this score is not accurate, but for some reason my bot did better when I did factor the inclusion-exclusion principle.

The evaluation function was the thing I spend the most time on but unfortunately I was not able to find a better function. When searching in some games my bot thought it has a clear advantage, when suddenly in deeper plies it disovered a win for the other player.

For the search algorithm I used a alpha-beta search with improvements. The improvenets I have

• PVS with late move reductions and aspiration windows
• Null move pruning, but only the first 30 moves or so since else the bot was more likely to fall in traps
• Depth extensions when a player takes a small board or when a player only has one move possible
• Transposition tables
• Move ordering based on killer moves, history heuristic, 0 score when the move sends the other player to a full small board and a high score when the move wins a small board
• Optimizations like bitboards and generating as much static data before the game starts.
• Pondering, although I do not like it, it is almost a neccesity in the top since (almost) all bots have pondering
• 2-move opening book
• I tried pruning and razoring, but they resulted in the bot falling into more traps

• Updated Monday, January 30th 2017 @ 17:35:45

I have wanted for a long time to try MTCS, and this contest was a good opportunity for me. I also could not help recycling my usual alpha-beta framework coming from my chess program BugChess2 and which has already been used for a few AI contests. The idea was to have a sparring partner that i would improve with the MTCS bot to have more reliable tests and maybe try a hybrid approach somehow. What happened was that after trying naively all ideas from the same paper as ChickenCoop, the MTCS bot was barely reaching 40% against my first working alpha-beta bot. I did not really know in what area I should have insisted, whereas I had lots of ideas for the alpha-beta bot, so I gave up MTCS...It seems to me now that rollout policy and optimization are the keys. So I am really impressed to see how strong the top MTCS bot are, and am very interested in knowing what allowed them to reach this level.

Here are the major improvements I found in my alpha-beta searcher with Principal Variation Search:

*** Evaluation. It seems i followed the same path as DaFish, rahenri and pepijno, at least at first. I switched in my 2nd version to a probability based evaluation then an approximation that was better and faster and consisted in summming the probabilty of the 8 possible lines of a mini board. I experimented a lot on the miniboard probability generation in 2 different directions:

1-- playing randoms games (a kind of MTCS limited to a mini board). I started with purely random games. Then I found the following significant improvements while trying to approach what was happening in a real game.

-> Playing the best move (according to my previous evaluation) but choosing a random player each time improved a lot the results.

-> Same as before but playing the best move in 60% of the cases and the 2nd best move the rest of the time gave me a +30 elos.

-> Then i worked on the number of moves to simulate that most miniboards were not played until the end. I tried various percentage and got the best results at 55% random reduction on the maximum number of moves left. (~+20 elos) I tried to index the distribution of number of moves to play on 2 things using real games (on the % of moves leading to the square, the total number of moves lefts), seemed improving things a bit (maybe 5 - 10 elos), but complicated structures too much as i was running out of time.

2-- Extracted from games played by my bot. After a lot of false hopes and inconsistent results (partially due to the fact that it depended a lot on the chosen opening books and probably opponents), i gave up this direction (still convinced it could be worthwhile with more time). I tried many many things that worsened notably the level of my bot ;) (indexing stats on various parameters of the miniboard in the meta board (total number of moves left, % of moves leading to the meta square, max number of aligned square with this meta square, etc...)

*** LMR Late Move Reductions lead to great improvement in most chess programs (i do not remember exactly, but in mine it was more than 100 elos, maybe 200) In chess programs, moves are traditionnaly reduced by 1 sometimes 2 plies (it can also be a general formula involving depth and number of move like it was at a time in Stockfish, one of the 2 current strongest programms). To my surprise, i was able to go as far as reducing depth by 5 plies in this game ! The best scheme i found was reducing move n by n plies (starting at 0) with a max reduction of 5 (so no reduction increase after the 6th move).

*** Null Move To adjust null move to Ultimate TTT, i made the obvious assomption that the next player was able to play everywhere on the board. Null move is also a very big improvement in most chess programs (between 100 and 200 elos in mine). After applying my huge LRM reductions, i discovered that null move had hardly any positive effect. With a huge R=8 ply reduction and other tunings (typically 2-3 in chess) , it finally gave me 10-15 elo...

*** Quiescence search I worked a lot on this one. In the first implementation only moves winning a miniboard were played. Then i implemented a static detection of forced succesions of moves (up to 3 moves) leading to a win/loss. If such a situation was detected, the standpat condition was ignored in the QS and all moves were generated for the defending side, and winning candidates for the attacking side. Around +30 elos.

Pruning miniboard winning moves according to the expected eval impovement also helped a bit, as well as generating "neutralizing" moves (moves that makes a meta line unwinnable for the opponent), and then i used precomputed best miniboard moves (according to the precomputed miniboard winning stats).

*** H Table Nothing fancy, I kept my old 2 slot scheme (one keeping the last search result and the other the deeper, with an agin system).

*** Move ordering I tried various things but did not succeed in finding much improvement, almost changed nothing: H move, then 2nd H move, killers and all remaining moves sorted with history scores. Indexing killer moves on miniboards was a small gain.

*** 1-move opening book :-)

*** pondering (with which I gave myself quite a scare in the final week because of an obscure bug)

My main regret in this competition was not to have spent more time building good tools first, starting with a good testing framework (I built it within the AI, which led to mistakes and my opening books was no good) - i was too impatient to start the real thing :)

• Created Monday, January 30th 2017 @ 19:40:14

Nice to see similar strategies being used by other people.

One challenge I faced that I wish I spend more time with was on evaluating my bot. Due the limited randomness of my player (i would pick a random move among the ones with highest score, most of the time there was only one), just playing many games from the beginning didn't feel like a good way to test. There were cases where an improvement against previous version would not translate into an improvement against other bots. I wonder if anyone did anything more sophisticated. I think a better approach is to pick a set of interesting positions and start from one of those instead of from the beginning. Creating a good set doesn't seem easy though, I have no other idea other than maybe pick a sample from games by top players.

• Updated Tuesday, January 31st 2017 @ 09:23:33

I think it is fun to read about your approaches. It is really nice to see ideas such as using wild card moves for null move pruning, though I still have trouble to see how null move pruning is implemented. This is a small write-up of what I did. Unfortunately I was a bit late to the show, so I am not sure that version I have in the competition is correct - I had a last minute idea of how to detect draws early which was implemented very quickly. Also there are some "techniques" that I use, that I really doubt adds anything to the bots playing strength.

I went with a very typical negascout solution with A/B-prunning, transposition tables, weak move ordering, quiescence search, early draw detection and pondering. The most interesting idea I had was to generate all normal tictactoe-boards and do some analysis on them, which is used for both for my heuristic, move ordering, terminal-detection and early draw detection.

## Tictactoe-boards

For each ttt-board I have the following values. Each position is for each player given a value based on the strongest line it is part of. - If it is the missing position for winning the board its value is 3. - If it is part of a line with two missing pieces its value is 2. - Three missing has the value 1 - Not possible to win has the value 0 These values are kept in different other forms as well for performance reasons.

## Heuristic

I was inspired by (I stole) some ideas from maek on how to make a heuristic. For each ttt-board I take its macro-position value and multiplies it with the maximum position-value of its board. The sum of these values is my basic heuristic. In order to give strong macro-lines a higher evaluation I multiply the values of all lines and add them to the heuristic with a weight. I also have small weights giving a larger value to a ttt-board if it can be won without giving the opponent a wildcard move.

## Other uses

The ttt-boards are also used for to detect draws early, when all macro positions evaluate to 0 the game is drawn. I am not sure how much it helps, but from very limited testing it seemed like it gave a ply from around move 20, which seems reasonably strong. The ttt-boards can also be used to detect whether a move is forcing which is used for the quiescence-search, and it is also used for move ordering since it can be used to figure out whether a move will result in a wildcard move for the opponent.

## Problems

I think my main problem with my bot is that its heuristic fluctuates a lot from ply to ply. Placing either a cross or a circle will almost always improve the heuristic value for the placing player. This gave me quite some difficulties when I experimented with differing search depth, because odd search depths are not comparable with even. In order for the quiescence search to work the depth is increased with increments of two when a forcing move i detected, however I even think it is problematic to compare odd and even search-depths with themselves. I never saw any improvement with late move reductions which I suspect is because of the same reason. I think the fluctuations also makes my bot more likely to play for draws even in better positions, if the fluctuations are from positive to negative the bot will go for a draw when one is seen. I think fixing this problem could improve the bot quite a bit. Lastly I wasted a lot of hours testing broken versions of the bot without realising it, I spend 5 hours testing a version of a bot that played illegal moves after the first ply. I also had some problem using and debugging in C++ which is quite new to me. Next time I do something like this I will make sure that my bot is testable from the beginning.

Thank you all for sharing, I really enjoyed making this bot, if I find the time I will join the Go or Hack-man competition as well.

• Updated Saturday, February 4th 2017 @ 18:28:09

>> Move ordering I tried various things but did not succeed in finding much improvement

Did you try moves that lead an opponent to the current miniboard again?

1  2