Dominion Strategy Forum

Please login or register.

Login with username, password and session length
Pages: [1]

Author Topic: Evaluation Function for Ultimate Tic-Tac-Toe  (Read 9809 times)

0 Members and 1 Guest are viewing this topic.

GeoLib

  • Jester
  • *****
  • Offline Offline
  • Posts: 965
  • Respect: +1265
    • View Profile
Evaluation Function for Ultimate Tic-Tac-Toe
« on: January 09, 2015, 07:51:37 pm »
+2

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). 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?
Logged
"All advice is awful"
 —Count Grishnakh

blueblimp

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2849
  • Respect: +1559
    • View Profile
Re: Evaluation Function for Ultimate Tic-Tac-Toe
« Reply #1 on: January 09, 2015, 08:23:42 pm »
+4

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

GeoLib

  • Jester
  • *****
  • Offline Offline
  • Posts: 965
  • Respect: +1265
    • View Profile
Re: Evaluation Function for Ultimate Tic-Tac-Toe
« Reply #2 on: January 09, 2015, 09:11:38 pm »
0

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.
Logged
"All advice is awful"
 —Count Grishnakh

Titandrake

  • Mountebank
  • *****
  • Offline Offline
  • Posts: 2210
  • Respect: +2854
    • View Profile
Re: Evaluation Function for Ultimate Tic-Tac-Toe
« Reply #3 on: January 09, 2015, 11:57:06 pm »
+2

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.
Logged
I have a blog! It's called Sorta Insightful. Check it out?

GeoLib

  • Jester
  • *****
  • Offline Offline
  • Posts: 965
  • Respect: +1265
    • View Profile
Re: Evaluation Function for Ultimate Tic-Tac-Toe
« Reply #4 on: January 10, 2015, 12:06:12 am »
0

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
« Last Edit: January 10, 2015, 12:12:08 am by GeoLib »
Logged
"All advice is awful"
 —Count Grishnakh

ShereKhan

  • Pawn
  • **
  • Offline Offline
  • Posts: 1
  • Respect: +1
    • View Profile
    • Tigerish Games
Re: Evaluation Function for Ultimate Tic-Tac-Toe
« Reply #5 on: April 22, 2015, 09:58:44 am »
+1

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.

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!
Logged

Ghacob

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 149
  • Shuffle iT Username: Gender
  • J. They/them
  • Respect: +204
    • View Profile
Re: Evaluation Function for Ultimate Tic-Tac-Toe
« Reply #6 on: April 22, 2015, 11:16:34 am »
0

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.
Logged
Gender happened.

GeoLib

  • Jester
  • *****
  • Offline Offline
  • Posts: 965
  • Respect: +1265
    • View Profile
Re: Evaluation Function for Ultimate Tic-Tac-Toe
« Reply #7 on: April 22, 2015, 01:18:42 pm »
0

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.
Logged
"All advice is awful"
 —Count Grishnakh

Jack Rudd

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1323
  • Shuffle iT Username: Jack Rudd
  • Respect: +1379
    • View Profile
Re: Evaluation Function for Ultimate Tic-Tac-Toe
« Reply #8 on: April 22, 2015, 02:15:42 pm »
+3

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.
Logged
Centuries later, archaeologists discover the remains of your ancient civilization.

Evidence of thriving towns, Pottery, roads, and a centralized government amaze the startled scientists.

Finally, they come upon a stone tablet, which contains but one mysterious phrase!

'ISOTROPIC WILL RETURN!'

GeoLib

  • Jester
  • *****
  • Offline Offline
  • Posts: 965
  • Respect: +1265
    • View Profile
Re: Evaluation Function for Ultimate Tic-Tac-Toe
« Reply #9 on: April 22, 2015, 04:21:52 pm »
0

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.
Logged
"All advice is awful"
 —Count Grishnakh

popsofctown

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 5477
  • Respect: +2860
    • View Profile
Re: Evaluation Function for Ultimate Tic-Tac-Toe
« Reply #10 on: April 22, 2015, 11:39:57 pm »
0

It seems plausible that ultimate tic tac toe has a tie-or-better strategy for player one.
Logged

popsofctown

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 5477
  • Respect: +2860
    • View Profile
Re: Evaluation Function for Ultimate Tic-Tac-Toe
« Reply #11 on: April 22, 2015, 11:44:53 pm »
0

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

Grujah

  • Mountebank
  • *****
  • Offline Offline
  • Posts: 2237
  • Respect: +1177
    • View Profile
Re: Evaluation Function for Ultimate Tic-Tac-Toe
« Reply #12 on: April 22, 2015, 11:59:51 pm »
0

And call it Vulcan Tic-Tac-Toe.
Logged
Pages: [1]
 

Page created in 0.051 seconds with 21 queries.