NegaMax (Minimax)

The basis is MiniMax, a literal implementation would involve 2 methods that take turns (mutually recursive), 1 for each side.

Lazy programmers turn this into NegaMax, one method with a strategically placed - operator. - SO / wikipedia

Negamax search is a variant form of minimax search that relies on the zero-sum property of a two-player game. This algorithm relies on the fact that max ( a , b ) = − min ( − a , − b ) {\displaystyle \max(a,b)=-\min(-a,-b)} {\displaystyle \max(a,b)=-\min(-a,-b)} to simplify the implementation of the minimax algorithm.

Alpha/Beta pruning is keeping track of a Window of best moves (over multiple depths) to detect dead branches.

Negamax with a/b pruning

def negamax(game, depth = 0, alpha = -1000, beta = 1000, color = 1)
    return color * score_scenarios(game, depth) if game.game_over?

    max = -1000

    game.board.check_available_spaces.each do |space|
      game.board.place_marker(space, game.current_player.marker)
      game.change_turns
      negamax_value = -negamax(game, depth+1, -beta, -alpha, -color)

      game.board.place_marker(space, space)
      game.change_turns

      max = [max, negamax_value].max
      @best_score[space] = max if depth == 0
      alpha = [alpha, negamax_value].max
      return alpha if alpha >= beta

    end

    max
end