Details

Minimax

Minimax explores a tree of legal moves. It chooses the move with the best outcome assuming the opponent always chooses the strongest reply. In this zero-sum game, an advantage for one player is a disadvantage for the other.

Here, search stops at the selected depth, measured in individual moves by either player. Unfinished positions are scored using open pairs, triples, and positional weights that favor the center. Immediate wins and moves that avoid an immediate loss are checked at the root. A limited-depth search can still miss a threat beyond its horizon.

Minimax tree: the opponent reduces leaf scores 3 and 7 to 3, and 2 and 9 to 2. We choose the left branch with value 3. — Figure 1. MinimaxA small example with scores from our perspective. The opponent takes the minimum; we take the maximum. Higher is better for us.

Shannon (1950), Programming a Computer for Playing Chess (PDF) — foundational game-tree search and position evaluation.
Minimax Visualizer: run, pause, and step through a tree. Choose View Example, then Run > Minimax.

Alpha-beta

Alpha-beta computes the same minimax value while skipping branches that cannot improve the decision. Alpha bounds what the maximizing player can secure; beta bounds what the minimizing player will allow. When those bounds meet, the remaining branch can be pruned.

Both search agents use the same evaluator and center-first move ordering. At equal depth they choose the same move; pruning lets alpha-beta search deeper with less work.

Alpha-beta visits the left branch and secures value 3. In the right branch, seeing a 2 lets it skip the last leaf. — Figure 2. Alpha-beta pruningSame tree, same decision. Once the right branch can offer at most 2, its remaining leaf cannot improve on the 3 already available.

Knuth & Moore (1975), An Analysis of Alpha-Beta Pruning — correctness, move ordering, and search efficiency.
Watch the same tree with alpha-beta pruning. Choose View Example, then Run > Alpha-Beta Pruning.

DQN · CNN · Adversarial

The neural opponent learns an action value, Q(s, a), for dropping a piece in each column. Its CNN sees three board planes: its pieces, the opponent's pieces, and empty cells. Convolutions share spatial pattern detectors across the board; each column's value is read at the cell where its piece would land. At play time it chooses the highest-valued legal column in one forward pass.

Our pieces, opponent pieces, and empty cells form three input planes. A CNN produces seven column values, and the highest legal value selects column 3. — Figure 3. CNN policyThe browser policy: three input planes, one CNN pass, seven action values. Illustrated values are examples, not a prediction from the saved model.

Training uses adversarial Double DQN. After one move, the successor board is viewed from the opponent's perspective. The online network chooses that opponent's best legal action, and a periodically synchronized target network estimates its value. For a nonterminal move, the learning target is:

1. Choose the opponent's best legal action.

a^{*} = \underset{b \in A (s^{'})}{arg max} Q_{online} (s^{'}, b)

2. Discount its value and reverse the perspective.

y = - γ Q_{target} (s^{'}, a^{*})

Here, s′ is the next board from the opponent's perspective, A(s′) contains its legal columns, and a* is the selected action. y is our training target.

The minus sign turns the opponent's advantage into our disadvantage; γ discounts future outcomes. Winning moves target +1 and draws target 0, without bootstrapping. This approximates a best response using learned values, so it does not guarantee optimal play.

An estimated opponent value of positive 0.8 becomes our target of negative 0.792 after discounting by 0.99 and reversing the sign. — Figure 4. Adversarial targetExample of the perspective change, with a discount of 0.99. This is a learning target, not a win probability.

Training mixes random, tactical, search, and frozen historical neural opponents. Replay memory, mirrored boards, legal-move masking, and a separate target network support learning. Weights stay fixed during browser play.

Mnih et al. (2013), Playing Atari with Deep Reinforcement Learning — CNN-based Q-learning and replay.
van Hasselt, Guez & Silver (2016), Deep Reinforcement Learning with Double Q-learning — separating action selection from evaluation.

The opponent-relative, negative target above is this project's zero-sum adaptation of Double DQN; it is not the single-agent Atari objective in those papers.