Dominion Strategy Forum

Miscellaneous => General Discussion => Topic started by: GeoLib on January 09, 2015, 07:51:37 pm

Title: Evaluation Function for Ultimate Tic-Tac-Toe
Post by: GeoLib on January 09, 2015, 07:51:37 pm
So one of my winter break projects has been teaching myself C. I've made it through K&R. For fun I also wrote an AI for tic-tac-toe. So pretty straightforward.

Now what I want to do is write one for ultimate tic-tac-toe (description (http://mathwithbaddrawings.com/2013/06/16/ultimate-tic-tac-toe/)). Unlike tic-tac-toe, I'm probably not going to be able to build the full decision tree, so I'm struggling to come up with a good evaluation function for a given UTTT game state. Obviously I could give some sort of bonus for having won the mini-boards. Probably weighted with center > corner > side, but what about evaluating incomplete boards? I could give a point value to squares in there and see how that turns out. I could also give points for every miniboard where you're one away from winning, though this is a little harder to evaluate and might not be worth the time. I'm curious though if any fuhduhsies have some clever ideas. I'm storing each miniboard as two shorts (one for x and one for o) where each of the bottom 9 bits represents the square being taken by that player. Any ideas?
Title: Re: Evaluation Function for Ultimate Tic-Tac-Toe
Post by: blueblimp on January 09, 2015, 08:23:42 pm
You may be aware of this already, but the standard for games where you don't have an evaluation function is to use Monte Carlo Tree Search, usually the UCT algorithm. The general idea is that instead of trying to hardcode some idea of whether a state is favourable, instead you just finish the game using random moves a few times and see whether you win more than you lose. MCTS was a breakthrough for computer Go, where even dedicated research had failed to find a good enough evaluation function, but it also can work well for games where you just don't happen to have an idea for an evaluation function yet.

That said, thinking of an evaluation function can be more fun. I haven't played UTTT so it's hard to guess about it. I'd be up to play some games at http://bejofo.net/ttt to get a feel for it, if you want.

(By the way, I assume this was intended for "Other Board Games" or "General Discussion".)
Title: Re: Evaluation Function for Ultimate Tic-Tac-Toe
Post by: GeoLib on January 09, 2015, 09:11:38 pm
You may be aware of this already, but the standard for games where you don't have an evaluation function is to use Monte Carlo Tree Search, usually the UCT algorithm. The general idea is that instead of trying to hardcode some idea of whether a state is favourable, instead you just finish the game using random moves a few times and see whether you win more than you lose. MCTS was a breakthrough for computer Go, where even dedicated research had failed to find a good enough evaluation function, but it also can work well for games where you just don't happen to have an idea for an evaluation function yet.

That said, thinking of an evaluation function can be more fun. I haven't played UTTT so it's hard to guess about it. I'd be up to play some games at http://bejofo.net/ttt to get a feel for it, if you want.

(By the way, I assume this was intended for "Other Board Games" or "General Discussion".)

Ah, I had not heard of that. That's cool, thank you! I may give that a try too.


My current best idea for an evaluation function is to go through each miniboard and evaluate them individually and multiply by a weighting function (maybe 5 for center, 3 for corner, and 1 for side). For each miniboard assign say 100 points to a win (-100 to a loss, 0 for a full board that's a draw). Otherwise, 5 for a center, 3 for a corner, 1 for a side (- for os). I also don't really know the game well enough to know whether this makes any sense. I've only played around 10 times and my main method for evaluating boards when playing was basically "how many miniboards can they not send me to." It seemed like winning the center board was pretty important. I'd be up for some games though to develop some more intuition.

Yeah, I meant to put this in general discussion. I reported it to Theory.
Title: Re: Evaluation Function for Ultimate Tic-Tac-Toe
Post by: Titandrake on January 09, 2015, 11:57:06 pm
In addition to MCTS, you can also combine MCTS with an evaluation function. In plain MCTS, you pick moves randomly, which somehow gives you good move decisions when you simulate enough games. However, if you already have a decent evaluation function, you can use that to bias how you randomly select moves: if a move has a higher value, then you probably want to pick that move more often when doing the simulations.

In my experience, minimax search isn't very good without a strong evaluation function, but this biased-simulation lets you use okay evaluation functions to get good play. You may also want to look into methods that find optimal weights for you, once you decide what your evaluation function is looking at. Stochastic gradient descent and temporal difference learning are the methods I know of.

(I am kinda-sorta doing research here so I've been fiddling with similar things...)

For Ultimate Tic-Tac-Toe in particular, you should probably play the variant where you cannot be sent to an already-won square. There's a pretty simple strategy that wins 100% of the time as first player, and once someone points it out to you it's hard to not play it, or to not bias your evaluation function to follow that strategy more.
Title: Re: Evaluation Function for Ultimate Tic-Tac-Toe
Post by: GeoLib on January 10, 2015, 12:06:12 am
In addition to MCTS, you can also combine MCTS with an evaluation function. In plain MCTS, you pick moves randomly, which somehow gives you good move decisions when you simulate enough games. However, if you already have a decent evaluation function, you can use that to bias how you randomly select moves: if a move has a higher value, then you probably want to pick that move more often when doing the simulations.

In my experience, minimax search isn't very good without a strong evaluation function, but this biased-simulation lets you use okay evaluation functions to get good play. You may also want to look into methods that find optimal weights for you, once you decide what your evaluation function is looking at. Stochastic gradient descent and temporal difference learning are the methods I know of.

(I am kinda-sorta doing research here so I've been fiddling with similar things...)

For Ultimate Tic-Tac-Toe in particular, you should probably play the variant where you cannot be sent to an already-won square. There's a pretty simple strategy that wins 100% of the time as first player, and once someone points it out to you it's hard to not play it, or to not bias your evaluation function to follow that strategy more.

Thanks! I will continue looking into improved techniques. Mostly this is just for fun and a project with which to learn a language, but if I have time during the semester I will continue working on it. I like games (I'm sure I'm the only one on the forum who does... :P)

What do you mean "the variant where you cannot be sent to an already-won square." As in sending your opponent to an already-won square is not a legal move (so if someone wins the top right miniboard then all top-right squares in the miniboards are off limits)?

Edit: Ok. I looked up this winning strategy. I see what you mean. So the version I had heard of was that once a square was won and you were sent there you could go anywhere, which is I assume the variant you were suggesting I use. All is well
Title: Re: Evaluation Function for Ultimate Tic-Tac-Toe
Post by: ShereKhan on April 22, 2015, 09:58:44 am
Hello, sorry to intrude!

I've just developed an Ultimate Tic-Tac-Toe game myself, maybe you can use it to get inspired, it has an additional rule to the "classic" UTTT game: the oldest 4th piece of the same player in a board will get erased. This eliminates the possibility that boards end up in ties and makes matches much more fun to play.

You can play this game for free on Steam: http://store.steampowered.com/app/360870 (http://store.steampowered.com/app/360870).

You can play against the AI, but also challenge your friends, play ranked matches, see the global leader-boards, win achievements a.s.o.

Enjoy!
Title: Re: Evaluation Function for Ultimate Tic-Tac-Toe
Post by: Ghacob on April 22, 2015, 11:16:34 am
Last summer I created my own varient of this (I was unaware that UTTT existed already at the time)
In this version, players may go wherever they choose and ties are counted as victory for both players
I haven't done any formal testing, but it's possible to always force a tie, so maybe this isn't the best way to play. However, I would be interested in successful strategies other than always attempting to tie your opponent.
Title: Re: Evaluation Function for Ultimate Tic-Tac-Toe
Post by: GeoLib on April 22, 2015, 01:18:42 pm
Last summer I created my own varient of this (I was unaware that UTTT existed already at the time)
In this version, players may go wherever they choose and ties are counted as victory for both players
I haven't done any formal testing, but it's possible to always force a tie, so maybe this isn't the best way to play. However, I would be interested in successful strategies other than always attempting to tie your opponent.

The forced movement is kind of critical to UTTT.

If there is always a way for either player to force a tie then it's impossible for either player to get a win with correct play from their opponent. Therefore there don't exist "successful" strategies other than playing for the tie. This is exactly the problem with regular TTT.
Title: Re: Evaluation Function for Ultimate Tic-Tac-Toe
Post by: Jack Rudd on April 22, 2015, 02:15:42 pm
Last summer I created my own varient of this (I was unaware that UTTT existed already at the time)
In this version, players may go wherever they choose and ties are counted as victory for both players
I haven't done any formal testing, but it's possible to always force a tie, so maybe this isn't the best way to play. However, I would be interested in successful strategies other than always attempting to tie your opponent.

The forced movement is kind of critical to UTTT.

If there is always a way for either player to force a tie then it's impossible for either player to get a win with correct play from their opponent. Therefore there don't exist "successful" strategies other than playing for the tie. This is exactly the problem with regular TTT.
It's exactly the problem with all games of pure skill. The only way to make them work as games is to make them complex enough that they are really hard to analyse out.
Title: Re: Evaluation Function for Ultimate Tic-Tac-Toe
Post by: GeoLib on April 22, 2015, 04:21:52 pm
Last summer I created my own varient of this (I was unaware that UTTT existed already at the time)
In this version, players may go wherever they choose and ties are counted as victory for both players
I haven't done any formal testing, but it's possible to always force a tie, so maybe this isn't the best way to play. However, I would be interested in successful strategies other than always attempting to tie your opponent.

The forced movement is kind of critical to UTTT.

If there is always a way for either player to force a tie then it's impossible for either player to get a win with correct play from their opponent. Therefore there don't exist "successful" strategies other than playing for the tie. This is exactly the problem with regular TTT.
It's exactly the problem with all games of pure skill. The only way to make them work as games is to make them complex enough that they are really hard to analyse out.

Yeah TTT and the game that Ghacob suggested both fail in this, which is why they don't work.
Title: Re: Evaluation Function for Ultimate Tic-Tac-Toe
Post by: popsofctown on April 22, 2015, 11:39:57 pm
It seems plausible that ultimate tic tac toe has a tie-or-better strategy for player one.
Title: Re: Evaluation Function for Ultimate Tic-Tac-Toe
Post by: popsofctown on April 22, 2015, 11:44:53 pm
If it contributes at all to the discussion to hear, another variant of tictac toe is to play it in 3D, and change the size from 3x3 to 4x4 (so actually 4x4x4) 
Title: Re: Evaluation Function for Ultimate Tic-Tac-Toe
Post by: Grujah on April 22, 2015, 11:59:51 pm
And call it Vulcan Tic-Tac-Toe.