Let's Connect! (Hard version)

This is the hard version of Connect4Bot. The only difference between this and the easy version is the strength of play required to defeat the grader. Solving one version does not guarantee solving the other.

This is an interactive problem.

Implement the class Connect4Bot, which plays the game Connect 4 with the goal of winning. Connect 4 (or Connect Four) is a classic two-player strategy game where players drop colored discs into a vertical grid, aiming to be the first to get four of their own color in a row (horizontally, vertically, or diagonally) before their opponent does.

In this version, simple heuristics are not sufficient. Your bot is expected to reason about future game states and select moves based on their long-term consequences. A correct solution should evaluate multiple plies of play and account for the opponent’s optimal responses. Solutions are expected to use recursive evaluation of game states (e.g., minimax-style search with pruning or equivalent techniques).

The interactor is adaptive, meaning the judge will adjust its strategy in response to your bot's behavior.

Methods

move(board)

• board is the current state of the game board as a subscriptable 2-dimensional container. This board is guaranteed to be $7\times 7$ in size.
• board is accessible with as a custom type Board which is guaranteed to be subscriptable. You should be using this type Board rather than a default container like std::vector.
• board's columns are labeled 0-6 from left to right, and rows are labeled 0-6 from bottom to top.
• Each board[i][j] has an integer value. This value is either 0, 1, or 2.
  • 0 indicates an empty square at row i and column j.
  • 1 indicates your bot's piece at row i and column j.
  • 2 indicates the judge's bot's piece at row i and column j.
• The function should return an integer between $0$ and $6$, inclusive, indicating the column in which your bot chooses to drop its disc.

Notes

• You do not need to implement any input/output parsing.

• Your submission will be evaluated against our reference bot. It plays at approximately the same strength level expected from your Connect 4 bot, but is intentionally slightly nerfed.

• Slower languages like Python may not pass the judge in the time limit. For this reason, this problem has been unrated.