Tic Tac Toe — Minimaxing

tl;dr — I built a minimax in ruby for Tic Tac Toe(TTT) that allows my TTT to play the following battles: COMPUTER vs. COMPUTER, HUMAN vs COMPUTER, or good old HUMAN vs. HUMAN


To put it in plain English, my TTT:

  • Looks at a TTT board and sees what available moves there are
  • For each available move, (A) evaluates all the possible “next” moves until the board is filled up (terminal state), (B) gives each available move a “score” based on if the move allows the player to win or not in the terminal state (e.g., +100 for a winning move, -100 for a losing move, 0 for all other cases)
  • The current player then plays the “move” with the highest score
  • The next player does the same and so on….

To highlight some of the logic in code:

  • Score function: takes in a TTT board and depth* and assigns points to the state of the board. E.g., my function assigns player “O” 100 points if “O” wins
def score(board, depth)
if over?(board)
if draw?(board)
0
elsif winner(board) == "O"
100 + depth
else
-100 - depth
end
else
0
end
end
  • Minimax function: returns the highest possible score given the available moves for the current player. If there are still free moves left after playing 1 move, it recursively checks the next move until the board reaches a terminal state
def scores_of_free_pos(board, depth)
player = current_player(board)
free_pos = possible_moves(board)
free_pos.collect do |pos|
new_board = board.clone
move(new_board, pos, player)
minimax(new_board, depth - 1)
end
end
def minimax(board, depth)
if over?(board) || depth == 0
return score(board, depth)
end
  player = current_player(board)
scores = scores_of_free_pos(board, depth)
  if player == "O"
scores.max
else
scores.min
end
end
  • Best_move function: returns the position of the best move (e.g., index of board) given we know which free position gives the highest score
def best_move(board, depth)
free_pos = possible_moves(board)
scores = scores_of_free_pos(board, depth)
if current_player(board) == "O"
best_score = scores.max
else
best_score = scores.min
end
move_index = scores.index(best_score)
free_pos[move_index]
end
  • Play function: that ties the whole game together and allows me to call on my #human_get_index and/or #comp_get_index methods to determine who the players are
def play(board)
until over?(board)
turn(board, method(:human_get_index), method(:comp_get_index))
end
draw?(board) ? (puts "Cats Game!"):(puts "Congratulations #{winner(board)}!")
end
The Cheating Robot
  • ***Depth????? This depth variable allows me to control how many “steps” I want my Minimax to look ahead (e.g., if there’s only one available move left, depth = 1 would tell me the winning move)
Like what you read? Give Cpan a round of applause.

From a quick cheer to a standing ovation, clap to show how much you enjoyed this story.