Last active
April 27, 2025 00:19
-
-
Save partybusiness/8c3428c9806ca4fb8faf2aaa0162fb17 to your computer and use it in GitHub Desktop.
R commands for analyzing tic tac toe match where each player plays randomly
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # create 3x3 tic tac toe board | |
| board = matrix(0, nrow=3, ncol=3, byrow=TRUE) | |
| # each square can be 0 = empty, 1 = X, 2 = O | |
| # returns index of board state | |
| board_index <- function(board) { | |
| index = 1 | |
| x = 1 | |
| y = 1 | |
| for (i in seq(0, length(board) - 1)) { | |
| index = index + (3 ^ i) * board[y, x] | |
| x = x + 1 | |
| if (x > dim(board)[2]) { | |
| x = 1 | |
| y = y + 1 | |
| } | |
| } | |
| return(index) | |
| } | |
| # generates board from index | |
| board_matrix <- function(board_index) { | |
| board_index = board_index - 1 | |
| board = matrix(0, nrow=3, ncol=3, byrow=TRUE) | |
| x = 1 | |
| y = 1 | |
| for (i in seq(0, length(board) - 1)) { | |
| board[y, x] = board_index %% 3 | |
| board_index = floor(board_index / 3) | |
| x = x + 1 | |
| if (x > dim(board)[2]) { | |
| x = 1 | |
| y = y + 1 | |
| } | |
| } | |
| return(board) | |
| } | |
| print_board <- function (board) { | |
| line_content = "" | |
| x = 1 | |
| y = 1 | |
| for (i in seq(1, length(board))) { | |
| if (board[y, x] == 0) { | |
| line_content = paste(line_content, " ", sep="") | |
| } | |
| if (board[y, x] == 1) { | |
| line_content = paste(line_content, "X", sep="") | |
| } | |
| if (board[y, x] == 2) { | |
| line_content = paste(line_content, "O", sep="") | |
| } | |
| x = x + 1 | |
| if (x > dim(board)[2]) { | |
| x = 1 | |
| y = y + 1 | |
| print.noquote(line_content) | |
| if (y <= dim(board)[1]) { | |
| print.noquote("-+-+-") | |
| } | |
| line_content = "" | |
| } else { | |
| line_content = paste(line_content, "|", sep="") | |
| } | |
| } | |
| } | |
| print_board(board) | |
| # create a list of empty spots | |
| empty_spots <- function (board) { | |
| spots = c() | |
| x = 1 | |
| y = 1 | |
| for (i in seq(1, length(board))) { | |
| if (board[i] == 0) { | |
| spots = c(spots, i) | |
| } | |
| x = x + 1 | |
| if (x > dim(board)[2]) { | |
| x = 1 | |
| y = y + 1 | |
| } | |
| } | |
| return (spots) | |
| } | |
| # checks if a single row in board matrix is filled in with winning row | |
| check_row <- function(board, spots) { | |
| x_count = 0 | |
| o_count = 0 | |
| for (spot in spots) { | |
| value = board[spot] | |
| if (value == 0) { | |
| return(0) | |
| } | |
| if (value == 1) { | |
| x_count = x_count + 1 | |
| } | |
| if (value == 2) { | |
| o_count = o_count + 1 | |
| } | |
| } | |
| if (x_count == length(spots)) { | |
| return(1) | |
| } | |
| if (o_count == length(spots)) { | |
| return(2) | |
| } | |
| return(0) | |
| } | |
| # checks for winner of given board matrix | |
| find_winner <- function(board) { | |
| count_rows = c( | |
| check_row(board, c(1,2,3)), | |
| check_row(board, c(4,5,6)), | |
| check_row(board, c(7,8,9)), | |
| check_row(board, c(1,4,7)), | |
| check_row(board, c(2,5,8)), | |
| check_row(board, c(3,6,9)), | |
| check_row(board, c(1,5,9)), | |
| check_row(board, c(3,5,7)) | |
| ) | |
| if (sum(count_rows == 0) == 8) { | |
| return(0) | |
| } | |
| if ((sum(count_rows == 1) > 0) && (sum(count_rows == 2) > 0)) { | |
| return(3) # both have winning rows, should technically never happen | |
| } | |
| if (sum(count_rows == 1) > 0) { | |
| return(1) # X wins | |
| } | |
| if (sum(count_rows == 2) > 0) { | |
| return(2) # O wins | |
| } | |
| print("error") | |
| print_board(board) | |
| return(0) | |
| } | |
| possible_states = 3^9 | |
| transition_matrix_x = matrix(0, nrow=possible_states, ncol=possible_states, byrow=TRUE) | |
| transition_matrix_o = matrix(0, nrow=possible_states, ncol=possible_states, byrow=TRUE) | |
| # transition_matrix_o[x, y] represents odds of moving from x to y on O's move if O places an O at a randomly picked empty spot | |
| for (prev_index in 1:possible_states) { | |
| prev_board = board_matrix(prev_index) | |
| winner = find_winner(prev_board) | |
| if (winner > 0) { | |
| # if a winner is declared, it stays where it was | |
| transition_matrix_x[prev_index, prev_index] = 1.0 | |
| transition_matrix_o[prev_index, prev_index] = 1.0 | |
| } else { | |
| spots = empty_spots(prev_board) | |
| if (length(spots) == 1) { # special case to avoid | |
| spot = spots[1] | |
| # possible move for player X == 1 | |
| board_copy = prev_board | |
| board_copy[spot] = 1 | |
| transition_matrix_x[board_index(board_copy), prev_index] = 1.0 | |
| if (length(board_copy) > 9) { | |
| print(paste("error X ", spot)) | |
| } | |
| # possible move for player O == 2 | |
| board_copy = prev_board | |
| board_copy[spot] = 2 | |
| transition_matrix_o[board_index(board_copy), prev_index] = 1.0 | |
| } else if (length(spots) > 1) { | |
| for (spot in spots) { | |
| # possible move for player X == 1 | |
| board_copy = prev_board | |
| board_copy[spot] = 1 | |
| transition_matrix_x[board_index(board_copy), prev_index] = 1.0 / length(spots) | |
| if (length(board_copy) > 9) { | |
| print(paste("error X ", spot)) | |
| } | |
| # possible move for player O == 2 | |
| board_copy = prev_board | |
| board_copy[spot] = 2 | |
| transition_matrix_o[board_index(board_copy), prev_index] = 1.0 / length(spots) | |
| if (length(board_copy) > 9) { | |
| print(paste("error O ", spot)) | |
| } | |
| } | |
| } else { | |
| # length of spots == 0 | |
| transition_matrix_x[prev_index, prev_index] = 1.0 | |
| transition_matrix_o[prev_index, prev_index] = 1.0 | |
| } | |
| } | |
| } | |
| print_possible_boards <- function(board_state, possible_states) { | |
| for (state_index in 1:possible_states) { | |
| if (board_state[state_index] > 0.0) { | |
| print(board_state[state_index]) | |
| print_board(board_matrix(state_index)) | |
| } | |
| } | |
| } | |
| count_wins <- function(board_state, possible_states) { | |
| x_win = 0 | |
| o_win = 0 | |
| tie = 0 | |
| broken = 0 | |
| for (state_index in 1:possible_states) { | |
| if (board_state[state_index] > 0.0) { | |
| winner = find_winner(board_matrix(state_index)) | |
| if (winner == 0) { | |
| tie = tie + board_state[state_index] | |
| } else if (winner == 1) { | |
| x_win = x_win + board_state[state_index] | |
| } else if (winner == 2) { | |
| o_win = o_win + board_state[state_index] | |
| } else { | |
| broken = broken + board_state[state_index] | |
| } | |
| } | |
| } | |
| paste("X =", x_win, "O =", o_win, "T =", tie, "B =", broken, sep=" ", (x_win + o_win + tie + broken)) | |
| } | |
| board_state = rep(0, possible_states) | |
| board_state[1] = 1 # start with all empty squares | |
| board_state = transition_matrix_x %*% board_state | |
| count_wins(board_state, possible_states) | |
| board_state = transition_matrix_o %*% board_state | |
| count_wins(board_state, possible_states) | |
| board_state = transition_matrix_x %*% board_state | |
| count_wins(board_state, possible_states) | |
| board_state = transition_matrix_o %*% board_state | |
| count_wins(board_state, possible_states) | |
| board_state = transition_matrix_x %*% board_state | |
| count_wins(board_state, possible_states) | |
| board_state = transition_matrix_o %*% board_state | |
| count_wins(board_state, possible_states) | |
| board_state = transition_matrix_x %*% board_state | |
| count_wins(board_state, possible_states) | |
| board_state = transition_matrix_o %*% board_state | |
| count_wins(board_state, possible_states) | |
| board_state = transition_matrix_x %*% board_state | |
| count_wins(board_state, possible_states) | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment