Ultimate Tic Tac Toe [Puzzle discussion]

Puzzles
#126

I would like to know how the smaller board is chosen each turn.

I use an empty list in my code, and append each valid_action_count to this list each turn.
Then I use the debug print to determine how many and what actions are available each turn.
What I see is that on turn 1, I have 91 ( 9x9) actions to choose from. Excellent.
However on my second turn, I have only 9 actions in the valid_action_count list.

Am I correct in observing that after the first turn I am forced to place my mark in a random smaller board rather than one of my own choosing?

#127

From the rules:

When a player plays on a small board, he also decides where the next player will be allowed to play: for example, if a player has played in the bottom left square of one of the small boards, the next player will play on the small board located at the bottom left square of the main board.

If a player is sent to a board that is either already won, or full, then that player is allowed to play in any empty square.

1 Like
#128

Thanks, for some reason when I read that the first time I misinterpreted it to mean that the next player has to play on the same small board. I’m not sure why I understood it better with your copy paste, but I appreciate it, thanks.

#129

I implemented minimax for wood league, but it always times out. Any suggestions?

import sys

PLAYER = 1
OPP = -1
EMPTY = 0
def findBestMove(board): 
    bestMove = [-1, -1]
    bestVal = -1000
    for i in range(len(board)):
        for j in range(len(board[0])):
            board[i][j] = PLAYER
            moveVal = minimax(board, 0, False)
            board[i][j] = EMPTY
            if moveVal > bestVal:
                bestMove = [i, j]
                bestVal = moveVal
    return bestMove

def minimax(board, depth, isMax):
    score = evaluate(board)
    if score == 10 or score == -10:
        return score
    if (isMovesLeft(board) == False) :
        return 0
    if isMax:
        best = -1000
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == EMPTY:
                    board[i][j] = PLAYER
                    best = max( best, minimax(board, depth + 1, not isMax) )
                    board[i][j] = EMPTY
        return best
    else:
        best = 1000
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == EMPTY:
                    board[i][j] = OPP
                    best = min( best, minimax(board, depth + 1, not isMax))
                    board[i][j] = EMPTY
        return best

def evaluate(board) :
    for row in range(3) :    
        if (board[row][0] == board[row][1] and board[row][1] == board[row][2]) :       
            if (board[row][0] == PLAYER) :
                return 10
            elif (board[row][0] == OPP) :
                return -10
    for col in range(3) :
        if (board[0][col] == board[1][col] and board[1][col] == board[2][col]) :
            if (board[0][col] == PLAYER) :
                return 10
            elif (board[0][col] == OPP) :
                return -10
    if (board[0][0] == board[1][1] and board[1][1] == board[2][2]) :
        if (board[0][0] == PLAYER) :
            return 10
        elif (board[0][0] == OPP) :
            return -10
    if (board[0][2] == board[1][1] and board[1][1] == board[2][0]) :
        if (board[0][2] == PLAYER) :
            return 10
        elif (board[0][2] == OPP) :
            return -10
    return 0

def isMovesLeft(board):
    for i in range(len(board)):
        for j in range(len(board[0])):
            if board[i][j] == EMPTY:
                return True
    return False

# game loop
target = [-1, -1]
boardState = [[EMPTY, EMPTY, EMPTY], [EMPTY, EMPTY, EMPTY], [EMPTY, EMPTY, EMPTY]]
while True:
    print(boardState, file=sys.stderr, flush=True)
    opponent_row, opponent_col = [int(i) for i in input().split()]
    if opponent_row != -1:
        boardState[opponent_row][opponent_col] = -1
    valid_action_count = int(input())
    target = findBestMove(boardState)
    print(target[0], target[1], sep = ' ')
#130

no max depth …
maybe not a good idea :wink:

4 Likes
#131

How is the time measured?
Because sometimes I get a timeout, and sometimes, if I rerun it with same settings, it works.

#132

the timer start after first input reading in a turn

1 Like
#133

Better give yourself some 5-10ms buffer. Though sometimes you can get lucky and get away with ~110ms in turn.

1 Like
#134

is the bronze bot beatable without MCTS? or am I wasting my time?

#135

MCTS is only needed for Legend. Some even got by without. If I remember well, bronze is a 3x3 TTT which can be solved within CG time constraints.

1 Like
#137

bronze is already 3x3x3x3

#138

Ouch ! Then it depends on how high you wanna go. Going the MCTS route is difficult but it will pay off for many other multis. Pro tip: use C++ or Rust for speed. You will need it.

2 Likes
#139

Hey all! I got some good inspiration from comments in this forum, I was able to go from 800th in gold league (using python with heuristics and pseudo-MCTS) to 30-50th in legend currently (C++ and pure MCTS), so I would like to leave here some small tips that I think haven’t been commented (or I don’t remember seeing them):

-be very mindful with data types: if you can do something with a short rather than an int, do it. That was commented already, but also take into account the functions too: changing “log” to “logf” and “sqrt” to “sqrtf” gave me 20% more iterations!

-avoid recalculations as much as possible: use lookup tables, or save them in your nodes if it’s specific for them. Things like that can also give another +20%

-once I tried to save in code a 512x512 lookup table and went way past the size limit, however, generating it takes ~6ms, so it doesn’t give any problems even when playing as second player (and you save time in more important turns)

-at least in my code, UCT seems to be much better than minimax for move selection, that alone got me from 110th to 35th in legend! Also reduces the risk of timeouts

4 Likes
#140

Here’s an argument suggesting that it is highly improbable the second player wins given optimal play. We define a new game as Ultimate Tic Tac Toe with Passing. The rules are the same as Ultimate Tic Tac Toe, except a player can ‘pass’ (not make a move, and then the opponent will have full access to the entire board to make their next move).

1: There is almost always a move at least as good as passing.
The only way passing could be the best move is if somehow, all playable squares must be reserved for ‘later’ in optimal play (a zugzwang position). However, I have never seen such a position.

2: The second player cannot win in Ultimate Tic Tac Toe with Passing.
We proceed by contradiction. Suppose the second player had a winning strategy. Then, the first player passes and (by symmetry) proceeds to use the second player’s supposed winning strategy against them, contradiction.

Now, I do believe that a classical alpha-beta engine would be best at the top level. For example, in chess, with incredibly strong pruning, Stockfish can reach average branching factors of ~ 1.6 at high depths. With this info, I estimate that a hypothetical state-of-the-art minimax engine would be able to consistently get depth 20+ almost instantly. This is of course assuming that one is willing to spend effort (training NNUE and optimizing the engine).
Additionally, there is a solver that can completely solve the game after about 20 plies (in ‘only’ a few hours of CPU-time), which is several orders of magnitude better than anything I’ve seen here.

#141

I think this is agreed upon that either p1 wins or a draw can be forced. There is some guy trying to prove ultimate tic tac toe Solving Ultimate Tic Tac Toe | Ramblings on game trees . Note that in CG version if no player has 3-in-row in main board, the player with more miniboards won wins. This probably further makes the p1 player better, but also we can’t stop proving at drawn positions until we are sure all miniboards are solved.

I think guided search would be better to try solve this game than minimax. I’m using mcts “ept” with one-hots NN (very similar to NNUE), and afaik reCurse uses mcts with CNN for his bot. The average branching factor seems like about 5, but thanks to robust NN this can be muchly reduced and resources on promising paths can be spent better.

#142

In terms of solving, proof-number search and its variants are widely agreed to be the best known methods. They are far better than minimax, but minimax is more efficient to just find a good move without computing its theoretical result. Based off chess, AlphaZero style search seems to reduce the branching factor to 1.5-1.6, and this should be roughly equal to the branching factor of the best minimax engines.

The issue with solving uttt is that to completely solve the game requires a large amount of work that cannot be reduced. Assuming your statement of average branching factor of 5, a complete proof totals to perhaps 10^16 nodes (plus or minus a couple of orders of magnitude). Additionally, we do not have perfect OR-node searching. Taking this into account, I estimate that the work required to solve uttt is approximately the amount of work to compute 10 men tablebases in chess. (as that website says, theoretically possible with current technology, but not practical)

1 Like
#145

UTTT is not THAT difficult (compared to designing a Chess Engine), but it is quite annoying when you designed a 3x3 bot and have to change the minimax algorithm for a 3x3x3x3 board :frowning: Lots of learning that can happen on this journey :slight_smile:

#146

I keep getting a timeout and dont understand why my code runs in 0.076 seconds in my ide…
has anyone encountered a similar problem? im running a basic negamax algo

#147

Maybe you forgot an input?

#148

Hello Great MCTS Java Programmers

Could you please share how did you manage to get to Legend in ?
I’m especially interested if anyone managed to get to legend with MCTS in Java.
I’m about 60-90 in Gold with pure MCTS in Java with about 2000 simulations in first moves. I have read that to get to Legend you should do about 20.000 - ten times more - and wonder if anybody managed to perftun his java bot so much or just used some other approach (eg minimax, nn).

@wala @dbdr @Yu_212 @Nerchio @BrunoFelthes @P.Greze @Mathkute @LaurentTrk @luigi_gelato @dacr