Gaming agents by reinforcement

Understand how an AI learns to play

Develop and compare agents in Rust, from the first grids to the Quarto. Explain their decisions through experiments, then observe and confront them.

Discover the project
010203
  1. 01

    Implement

    Construct the agents and rules of the games.

  2. 02

    Experiment

    Compare decisions, victories and calculation cost.

  3. 03

    Understand while playing

    Compare the explanations for the behaviour of the agents.

Build agents and understand their decisions

How can you learn to win without writing a rule for each situation? This project develops in Rust several agents capable of learning by trials and rewards, or of anticipating by simulation. The goal is to understand what each method learns, where it fails, and why.

From simple games to a real strategic problem

LineWorld and GridWorld are used to verify travel and rewards. The tic-tac-toe introduces an adversary; the Quarto makes the consequences more difficult to anticipate. We will follow the models, read their results, then find these mechanisms in a workshop where they can compete.

123The result feeds the rest
  1. 01

    Donate a coin

    Define what the opponent can play.

  2. 02

    They place it

    The placement can end the game.

  3. 03

    They choose your piece

    After placing, the same player gives.

Also choose the possibilities of the opponent

In Quarto, you win by aligning four pieces that share at least one attribute: color, size, shape or hollow. But we don't choose our own piece: it's the opponent who gives it to us. A good decision must therefore also avoid giving him a victory.

Two actions whose effects occur at different times

Placing a piece can make you win immediately. Giving a piece only reveals its quality after the opponent's response, sometimes several moves later. This difference makes the Quarto useful for studying learning: how to link a victory or a defeat to the decisions that prepared it?

123The result feeds the rest
  1. 01

    Observe

    The position or board describes the situation.

  2. 02

    Act

    A move changes the environment.

  3. 03

    Learn from the return

    Relate the result to previous decisions.

Learn from the consequences of your actions

In LineWorld, the agent moves along a line: one exit yields +10, the other −10. At first, it does not know which to choose. It observes its position, tries a move and receives a reward. A complete game, ending at an exit or the move limit, is an episode.

Why the reward should go back to the first choices

Intermediate trips earn zero. The agent must therefore link a favorable outcome to the actions that lead to it. The return adds up the future rewards, possibly giving less weight to the more distant ones. DQN learns to estimate this return; REINFORCE uses it to modify its choice probabilities.

  1. 01

    Observe the board

    Transform the situation into numbers.

  2. 02

    Estimate Q values

    Evaluate the consequences of each action.

  3. 03

    Correct by experience

    Revise estimates using memorized transitions.

Estimate what a blow can bring in

DQN addresses the problem by giving a value to each action: the expected reward, now and later. A network receives the game state and produces these Q values. To discover new possibilities, the agent sometimes explores randomly instead of following its best guess.

Reuse games to improve value estimates

The transitions are memorized: state, action, reward and next state. DQN draws mixed batches to avoid learning only on the last few moves. It compares its values to observed rewards and its future estimates. But if the latter are too optimistic, the error can propagate.

010203
  1. 01

    Current network

    Choose the future action deemed best.

  2. 02

    Target network

    Evaluate this action with less recent parameters.

  3. 03

    Correction

    Use this estimate to update the network.

Avoid reinforcing an overly optimistic estimate

Imagine a move looks excellent because of an estimation error. If the same network chooses and evaluates it, it may reinforce its own overestimation. Double DQN separates these roles: the current network chooses the future move and a target copy estimates its value.

Stabilize the target without freezing it forever

The copy is updated periodically. It therefore evolves less quickly than the network which learns. In this repository, DQN uses a single network and Double DQN adds this separate target. The mechanism aims for better stability; the curves allow you to check what is really changing.

Deposit curves · GridWorld. Different settings and durations; the blue DQN includes a correction.

A good peak does not guarantee a good ending

On GridWorld, the curves follow the success rate over the episodes. DQN rises quickly then declines. The red Double DQN also falls before rising again: the second copy therefore does not eliminate all the instabilities. At 5,000 episodes, these runs end up around 66% for DQN and 79% for DDQN.

Connect the curve to the mechanism, without concluding too quickly

These fluctuations motivate studying value targets and exploration. The corrected blue DQN, trained with a different learning rate, also follows a different trajectory. Settings must be compared and runs repeated before attributing a difference to the algorithm alone.

Deposit curves · Quarto V1. Different training modes, settings and budgets.

Change the experiments the agent learns from

On Quarto, the DDQN trained against chance peaks at around 44% in the orange run. The green run in self-play progresses to around 78%. In self-play, the agent encounters saved versions of itself: training situations evolve with the strategies learned.

Why more episodes aren't always enough

Repeating against the same weak opponent can maintain the same habits. Changing the adversaries enriches the situations encountered, but also makes learning less stable. These runs also differ in their settings: the graph motivates controlled tests, it does not alone isolate the effect of self-play.

010203
  1. 01

    A policy

    Probabilities on authorized shots.

  2. 02

    Part

    A sequence of actions and a final result.

  3. 03

    An update

    Reinforce or discourage the choices made.

Learn directly which moves to choose

DQN learns values, then chooses a move. REINFORCE directly learns choice probabilities: its policy. It plays a game, observes the outcome, then makes favourable actions more likely. Choices remain sampled: the same position can lead to different moves.

Why the Quarto complicates the attribution of the result

REINFORCE waits until the episode ends to adjust decisions. A good piece given early can be followed by a placement mistake; the final result mixes their effects. Updates become variable. The next experiment explores how to make this learning signal more useful.

010203
  1. 01

    Result obtained

    What the rest of the game brought back.

  2. 02

    Expected result

    The reference estimated by the critic.

  3. 03

    Advantage

    A gap that guides policy correction.

Compare the result to what was expected

Winning from an easy position does not teach the same thing as winning from a difficult position. A baseline provides a reference: is the return obtained better or worse than expected? The critic learns this reference from the game state.

A more informative fix for REINFORCE

Without a baseline, the update uses the game’s return directly. MeanBaseline subtracts a mean; CriticBaseline subtracts a value predicted for the position. This difference, called the advantage, reduces update noise when well estimated. The critic does not choose the move in place of the policy.

REINFORCE report · campaign 2. WR: average rate; FWR: last window. 50k = 50,000 episodes.

The critic helps more than just encoding

The graph compares mean win rate, WR, with final-window win rate, FWR. At 50,000 episodes in V1, moving from a mean baseline to a critic raises FWR from about 64% to 70%. In this experiment, the learned reference provides a more useful signal.

Learn better without solving the whole strategy

Critic variants also finish ahead of mean-baseline variants in V2. This supports a position-dependent reference. The result remains local to these experiments: with a small budget, MeanBaseline can do better because it has no additional value network to learn. But do these scores against random play hold up against another agent?

010203
  1. 01

    First batch · 40 parts

    REINFORCE J1 / DQN J2: DQN wins 40 times.

  2. 02

    Roles reversed · 40 parts

    DQN J1 / REINFORCE J2: REINFORCE wins 40 times.

  3. 03

    An anomaly to examine

    Exploratory batches, without proof of a universal advantage of J2.

REINFORCE report, sections 1.2 to 1.5. These batches do not measure the models’ absolute playing strength.

Reversing the players reverses the result

After measuring scores against random play, we played against REINFORCE: some moves seemed coherent. Then a duel against DQN surprised us. With REINFORCE as P1, DQN wins all 40 games in one batch. Swapping positions, REINFORCE wins all 40 in turn. The apparent ranking reverses.

Why look at the role before ranking models

In Quarto, P1 gives the first piece and P2 makes the first placement. The networks may have learned these responsibilities unevenly. However, the small tests that follow do not show a systematic P2 advantage. This observation suggests two directions: specify the role in the network input, and examine giving pieces separately from placing them.

010203
  1. 01

    V1 · 87 valeurs

    Board, pieces and give/place phase.

  2. 02

    V2 · 88 valeurs

    The same description, with the current player.

  3. 03

    A controlled comparison

    Separate the effect of information and budget.

Know whose decision it is

The first encoding of the Quarto, V1, describes the board, the attributes of the pieces, the piece in hand and the game phase with 87 values. V2 adds the current player. The hypothesis is simple: knowing its role can help the network interpret a favorable or dangerous situation.

Test the hypothesis instead of assuming it is true

With the same budget in campaign 2, V2 does not produce a net gain. The following campaign, out of seven initializations, obtains a small advantage for V2, but with twice as many episodes. We cannot therefore attribute this gain to the added information alone. The rules of the game remain the same.

DRL Report Figure · two opponents reveal two difficulty levels. V1 and V2 have different budgets.

Playing well against chance is not enough

The same REINFORCE goes from around 68–71% wins against chance to only 5% against a heuristic. This opponent follows two rules: win immediately if possible, and avoid offering an immediate victory. The graph therefore reveals a tactical weakness hidden by the first score.

Back to the difference between giving and putting

The results are compatible with the hypothesis of a credit difficult to attribute to the given pieces. They do not prove it alone: the errors should be measured in each phase. In the workshop, pay particular attention to the parts offered. This leads to another approach: simulating the consequences before choosing.

010203
  1. 01

    List the moves

    Start from authorized actions.

  2. 02

    Simulate their consequences

    Repeat random endgames.

  3. 03

    Compare averages

    Select the best-rated move.

Try out possible sequences before playing

Random Rollout evaluates each action by simulating random endgames. He chooses the one which obtains the best average result. Unlike trained networks, it starts this calculation again with each decision: it uses the rules to explore the consequences of the present board.

A simple, but expensive reference

In tic-tac-toe, a comparison of the report measures around 39% wins for Random Rollout versus 35% for UCT Arena, but only 223 games/s versus 692. This local gain therefore costs around three times more time per game. Distributing simulations between all moves also wastes computation on unpromising options. MCTS seeks to better distribute this budget.

One decision, several possible outcomes
  1. 01

    Select a branch

    Balancing estimated interest and lack of information.

  2. 02

    Simulate

    Explore possible consequences.

  3. 03

    Refresh tree

    Use the result for the next search.

Focus research on promising moves

MCTS builds a tree of possible futures. UCT guides its exploration: returning to the branches that seem good, while trying those that are still little visited. After each simulation, the result goes back up the tree to guide the next search.

Why budget and depth change the choice

Too little exploration can miss a trap; too much exploration disperses the calculation. The report does not find a universal setting. On Quarto, stopping a simulation too early can hide the consequence of a given piece. In the workshop, increasing the budget allows you to observe how the decision evolves.

Analytical report figure · Legacy/Arena comparison of repository, not ValueUCT or browser.

Speed up the search without changing its rule

MCTS also spends time creating and browsing nodes. The Arena version stores them in a contiguous array and connects them with indices. It avoids some of the allocations of the Legacy version and reuses its memory between searches.

Distinguish software speed and game level

The graph compares the throughput of the two implementations, in parts per second. The gains vary depending on the environment: cloning the game and simulating moves remain expensive. The UCT principle is identical. Better memory organization accelerates calculation without constituting, in itself, a new strategy.

010203
  1. 01

    Explore by UCT

    Choose a position to examine.

  2. 02

    Estimate its value

    Query the network rather than simulating an entire ending.

  3. 03

    Continue searching

    Reuse this estimate in the tree.

Replace simulations with an estimate

Networks decide quickly, while MCTS explicitly explores the consequences. ValueUCT combines the two: a value network estimates the quality of a position and replaces part of the simulations. This saves computation, provided the estimate is reliable.

A compromise measured in the report

In the benchmark against a random agent, the ValueZero variant achieves around 92.65% wins in Quarto, compared to 92.89% for UCT Arena, with almost six times higher throughput. These figures relate to the Rust engine and this specific protocol; they do not measure the browser demonstration.

010203
  1. 01

    Game quality

    Victories, defeats and draws.

  2. 02

    Regularity

    Multiple parts, roles and initializations.

  3. 03

    Decision cost

    Learning time and simulations per move.

A quick estimate must remain reliable

Compared to UCT Arena, ValueUCT campaigns are less stable: peaks of success can drop sharply. In tic-tac-toe, many games end in draws. A low proportion of victories therefore does not have the same meaning as a high proportion of defeats.

Observe the choices to understand the scores

A value error can direct the tree towards a bad branch; the exact causes of the falls remain to be isolated. The whole project shows why it is necessary to combine adversaries, roles, stability and cost. The workshop now makes it possible to compare these explanations with the DQN, DDQN, REINFORCE networks and research agents.

An experience to explore in this chapter.

Observe, play and make the agents compete

Start with REINFORCE against MCTS and advance with “One Shot”. The commentary distinguishes the choice of model and its visible consequence. In Quarto, spot the pieces that offer an immediate victory. Then reverse the agents and start again to observe the effect of the roles.

Experiment Settings

In Quarto, examine both the given piece and its placement. Compare REINFORCE to MCTS, then vary the research budget. One part illustrates behaviour; several parts are necessary to discuss the level of a model.