Mårten Wiman

The bot challenges on HackerEarth have so far all been for two players, with perfect information and no randomness. As such, there are primarily two effective strategies for building bots, which are covered in this tutorial.

Alpha-beta Pruning

This intuitive approach builds on the idea that the best move is one that puts your opponent in the worst position. By extending this logic several moves into the future, we arrive at the Minimax or Negamax algorithm.

function negamax(state, depth):
    if depth == 0:
        return [state.evaluate(), null]
    bestScore = -infinity
    for move in state.getMoves():
        moveScore = -negamax(state.makeMove(move), depth-1)[0]
        if moveScore > bestScore:
            bestScore = moveScore
            bestMove = move
    return [bestScore, bestMove]

Evaluation Functions

An evaluation function estimates how favorable a position is. It returns a large positive value if good for player A, and a negative value if unfavorable. For example, in Reversi - Bot Challenge #5, a simple evaluation function could compute the number of valid moves for A minus those for B. More advanced functions could consider positional advantages like corners.

While complex evaluation functions offer more accuracy, they are harder to write, debug, tune, and evaluate quickly, possibly reducing search depth. It's best to start simple and improve incrementally, testing changes thoroughly.

Pruning

Alpha-beta pruning improves Minimax by skipping branches that won't affect the final decision. For instance, if move m1 leads to a best-case outcome of x1, and move m2 has at least one possible counter resulting in worse than x1, we can discard m2 early without further evaluation.

function alphabeta(state, depth, alpha, beta):
    if depth == 0:
        return [state.evaluate(), null]
    bestScore = -infinity
    for move in state.getMoves():
        moveScore = -alphabeta(state.makeMove(move), depth-1, -beta, -alpha)[0]
        if moveScore > bestScore:
            bestScore = moveScore
            bestMove = move
        alpha = max(alpha, moveScore)
        if alpha >= beta:
            break
    return [bestScore, bestMove]

Alpha-beta pruning is most effective when the best moves are searched first. Optimal ordering can double the search depth compared to Minimax. Even with random move ordering, it's significantly more efficient.

Monte Carlo Tree Search (MCTS)

MCTS is another popular strategy and doesn't require an evaluation function. Instead, it uses random simulations to estimate move quality. Each simulation has two phases: an informed selection phase followed by random moves.

To guide move selection, MCTS uses a formula balancing exploration and exploitation. It favors moves with high win ratios but ensures all moves are eventually explored:

function MCTS(state):
    if state.numberOfSimulations == 0:
        play rest of game randomly
        state.numberOfSimulations += 1
        if current player won:
            return "won"
        else:
            state.wonGames += 1
            return "lost"
    bestScore = -infinity
    for move in state.getMoves():
        childState = state.makeMove(move)
        if childState.numberOfSimulations == 0:
            moveScore = infinity
        else:
            moveScore = (childState.wonGames / childState.numberOfSimulations) +
                        sqrt(2 * log(state.numberOfSimulations) / childState.numberOfSimulations)
        if moveScore > bestScore:
            bestScore = moveScore
            bestMove = move
    simulationResult = MCTS(state.makeMove(bestMove))
    state.numberOfSimulations += 1
    if simulationResult == "won":
        state.wonGames += 1
        return "lost"
    else:
        return "won"

After running MCTS from the root many times, pick the move with the best win ratio or the most simulations. MCTS is better for games with complex dynamics (e.g., Go), where good evaluation functions are hard to design. Alpha-beta is preferred when strong evaluation heuristics are available.

Conclusion

This tutorial introduced alpha-beta pruning and Monte Carlo Tree Search, the two main bot strategies in two-player games. Many improvements exist for both, particularly alpha-beta pruning. For more, explore the Chess Programming Wiki, which contains techniques applicable across many games.

Interested in building bots? Participate in the #UNITEDBYHCL Hackathon and win a trip to Theater of Dreams, Old Trafford and prizes worth $10,000.

Register Now!

To learn more about Battle of Bots, read this article by Gaurav Sen, third place finisher in Battle of Bots 7.