triangular dots and boxes

The AI uses Monte Carlo Tree Search (MCTS). It knows the rules but no strategy. Instead, it plays out lots of quick imaginary games from the current position and picks the move that worked out best. Each imaginary game has four steps:

1. Select. Walk down a tree of the positions explored so far, at each step picking a move that has either done well so far or hasn't been tried much. Balancing the two lets it focus on promising moves without overlooking surprises.
2. Expand. Add one new position to the tree.
3. Simulate. Play the rest of the game quickly, the way a sensible beginner would: take any triangle on offer, otherwise avoid handing one over, otherwise move at random.
4. Backpropagate. Record who won in every position along the path, so that good moves get tried more next time.

It repeats this for up to 0.8 seconds, which is usually over 100,000 games, then plays the move it explored most. It stops sooner when one move is clearly best, and runs in the background so the page stays responsive.

One tweak helps: each move starts with a hint based on its kind. Taking a triangle looks promising, and handing one over doesn't. That saves time on obviously bad moves, while still letting the AI discover when giving up a triangle pays off.