2
$\begingroup$

I guess this problem is encountered by everyone trying to solve Tic Tac Toe with various flavors of reinforcement learning.

The answer is not "always win" because the random opponent may sometimes be able to draw the game. So it is slightly less than the always-win score.

I wrote a little Python program to calculate that. Please help verify its correctness and inform me if it has bugs or errors.

$\endgroup$
2
  • 1
    $\begingroup$ Who moves first? Agent always moves first? $\endgroup$
    – Taw
    Sep 4 at 7:09
  • $\begingroup$ @Taw Yes, currently. I may make it an option in the program. $\endgroup$ Sep 4 at 8:26
1
$\begingroup$

This blog post suggests that when playing against a random opponent, if the agent goes first, the win rate is 97.8%, and if they go second, the win rate is 79.6% (and the rest are draws).

$\endgroup$
13
  • $\begingroup$ Your numbers may be compatible with my answer. I will modify my program to calculate the win/lose rate also.... $\endgroup$ Sep 4 at 8:30
  • $\begingroup$ Using your numbers, if agent goes first, 20 * 97.8% + 10 * 2.2% = 19.78 which is different from my answer = 19.9479... $\endgroup$ Sep 4 at 8:39
  • 1
    $\begingroup$ @YanKingYin There may be a difference between perfect play and maximising play against a specific opponent, especially as you have incentivised a draw differently to the usually assumed zero-sum game in your code. Perhaps re-run your code with draw scoring 0? $\endgroup$ Sep 4 at 10:37
  • 1
    $\begingroup$ @YanKingYin They are guaranteed the same when your opponent also plays perfectly (related fact - this is a Nash equilibrium, neither player can benefit from changing their policy). However, against a random opponent, the maximum reward policy and perfect play policy will be different in some states. that is because perfect play is always defensive against assumed perfect play by the opponent, it is about "not making mistakes". If you want to see proof, ask on the site. $\endgroup$ Sep 8 at 14:17
  • 1
    $\begingroup$ As a simpler example, you could construct an opponent P2 which was almost perfect, but reliably made a losing mistake in a specific reachable state S, that would normally be a losing state for P1. It is trivial to see that maximising play from P1 would attempt to reach this state, whilst perfect play would do the opposite and avoid it. The perfect player would expect a draw at best, but the maximising player may expect to win. $\endgroup$ Sep 8 at 14:25
1
$\begingroup$

Here I asssume:

  • Both players avoid illegal moves perfectly
  • Player X always chooses the move with maximum expectation value
  • Player O chooses all available moves with equal probability

Result depends on the scoring scheme:

  • (This scheme is used in one version of Gym Tic Tac Toe)

    For win=20, draw=10, lose=-20:

    Optimal expectation value =

    • X plays first: 19.94791666666666...

    • O plays first: 19.164021164021...

  • For win=20, draw=0, lose=-20:

    Optimal expectation value =

    • X plays first: 19.89583333333333...

    • O plays first: 18.497354497354....

It also helps to verify the program with some pre-played board positions, included in the code.

Here is the program:

import math     # for math.inf = infinity

print("Calculate optimal expectation value of TicTacToe")
print("from the perspective of 'X' = first player.")
print("Assume both players perfectly avoid illegal moves.")
print("Player 'X' always chooses the move with maximum expectation value.")
print("Player 'O' always plays all available moves with equal probability.")
print("You may modify the initial board position in the code.")

# Empty board
test_board = 9 * [0]

# Pre-moves, if any are desired:
# X|O|
# O|O|X
# X| |
#test_board[0] = -1
#test_board[3] = 1
#test_board[6] = -1
#test_board[4] = 1
#test_board[5] = -1
#test_board[1] = 1

def show_board(board):
    for i in [0, 3, 6]:
        for j in range(3):
            x = board[i + j]
            if x == -1:
                c = '❌'
            elif x == 1:
                c = '⭕'
            else:
                c = '  '
            print(c, end='')
        print(end='\n')

if test_board != 9 * [0]:
    print("\nInitial board position:")
    show_board(test_board)

# **** Calculate expectation value of input board position
def expectation(board, player):

    if player == -1:
        # **** Find all possible next moves for player 'X'
        moves = possible_moves(board)

        # Calculate expectation of these moves;
        # Player 'X' will only choose the one of maximum value.
        max_v = - math.inf
        for m in moves:
            new_board = board.copy()
            new_board[m] = -1       # Player 'X'

            # If this an ending move?
            r = game_over(new_board, -1)
            if r is not None:
                if r > max_v:
                    max_v = r
            else:
                v = expectation(new_board, 1)
                if v > max_v:
                    max_v = v
        # show_board(board)
        print("X's turn.  Expectation w.r.t. Player X =", max_v, end='\r')
        return max_v

    elif player == 1:
        # **** Find all possible next moves for player 'O'
        moves = possible_moves(board)
        # These moves have equal probability
        # print(board, moves)
        p = 1.0 / len(moves)

        # Calculate expectation of these moves;
        # Player 'O' chooses one of them randomly.
        Rx = 0.0        # reward from the perspective of 'X'
        for m in moves:
            new_board = board.copy()
            new_board[m] = 1        # Player 'O'

            # If this an ending move?
            r = game_over(new_board, 1)
            if r is not None:
                if r == 10:             # draw is +10 for either player
                    Rx += r * p
                else:
                    Rx += - r * p       # sign of reward is reversed
            else:
                v = expectation(new_board, -1)
                Rx += v * p
        # show_board(board)
        print("O's turn.  Expectation w.r.t. Player X =", Rx, end='\r')
        return Rx

def possible_moves(board):
    moves = []
    for i in range(9):
        if board[i] == 0:
            moves.append(i)
    return moves

# Check only for the given player.
# Return reward w.r.t. the specific player.
def game_over(board, player):
    # check horizontal
    for i in [0, 3, 6]:     # for each row
        if board[i + 0] == player and \
           board[i + 1] == player and \
           board[i + 2] == player:
            return 20

    # check vertical
    for j in [0, 1, 2]:     # for each column
        if board[3 * 0 + j] == player and \
           board[3 * 1 + j] == player and \
           board[3 * 2 + j] == player:
            return 20

    # check diagonal
    if board[0 + 0] == player and \
       board[3 * 1 + 1] == player and \
       board[3 * 2 + 2] == player:
        return 20

    # check backward diagonal
    if board[3 * 0 + 2] == player and \
       board[3 * 1 + 1] == player and \
       board[3 * 2 + 0] == player:
        return 20

    # return None if game still open
    for i in [0, 3, 6]:
        for j in [0, 1, 2]:
            if board[i + j] == 0:
                return None

    # For one version of gym TicTacToe, draw = 10 regardless of player;
    # Another way is to assign draw = 0.
    return 10

print("\u001b[2K\nOptimal value =", expectation(test_board, -1) )

Example output (for X's turn to play):

enter image description here

$\endgroup$
2
  • 1
    $\begingroup$ There is either a typo in your post, or bug in your code, because if win = 10, draw = 0, lose = -10, it's impossible that the expectation is 19.90. $\endgroup$
    – Taw
    Sep 4 at 7:14
  • $\begingroup$ @Taw: Thanks, corrected. $\endgroup$ Sep 4 at 8:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.