ALPHA_BETA.md

rubot: alpha_beta

The goal of the Bot is to take a decision tree and output the optimal decision.

At each depth of this tree we either want to maximise or minimize the resulting fitness.

In a competitive two player game, maximizing depths are the turns in which the bot is active, and during minimizing depths the opponent is able to make a decision.

Note that we do not expect a specific order of minimizing and maximizing turns. It is for example completely valid to have a game in which some actions allow additional actions for a player.

Let's first introduce the notation used from now on:

• a n := the bot is active, meaning we want to take the path which results in the highest fitness. the node itself has a fitness of n.
• o n := the opponent is active, meaning that we want to achieve the lowest possible fitness.

Each level of indentatation represents one action.

- a 0
  - o 7
  - o 3

The above tree means that the bot is active and has the choice between the action [0], with a fitness of 7 and [1] with a fitness of 3. To maximise the fitness, [0] would be chosen.

Paths are represented as a list of indices.

Examples

- a 0
  - a 12 # child 0
  - a 7  # child 1

optimal action: [0], with fitness: 12

If the bot is able to analyse the complete decision tree, only the leaf nodes are relevant.

- a 0
  - a 12
    - a 6
  - a 7

optimal action: [1], with fitness: 7

While the bot wants to maximise the achieved fitness, the opponent is expected to choose the path with the worst fitness.

- a 0
  - o 12
    - a 3 # The opponent would choose this, changing [0] to have a fitness of 3
    - a 7
  - a 6

optimal action: [1], with fitness: 6

Cutoffs

Unlike the brute bot, alpha beta pruning allows us to skip subtrees if it is provable that they always result in a less desirable outcome than an already computed path.

- a 0
  - a 6
  - o 12
    - a 3
    - a 7

Walking through this decision tree from top to bottom, we know by visiting [0] that there is a path with the fitness 6. While analysing [1], we realise that our opponent could chose [1][0], which would result in a fitness of 3.

As 3 is smaller than 6, we can stop looking at [1] entirely, without having seen [1][1].

It is also possible to apply this in the other direction:

- a 0
 - o 0
   - a 6
   - a 0
     - a 7
     - a 3

While analysing [0], the opponent first looks at [0][0] which ends up with a fitness of 6. Once they see [0][1][0] with a fitness of 7, they known that we would always be able to choose a path at [0][1] with a fitness > 6. This means that they are also able to skip [0][1][1] entirely.

• alpha: the best already certainly possible fitness at the current depth.
• beta: the worst already certainly achievable fitness by the opponent.
• alpha cutoff: skips paths where the opponent could choose an option which is smaller than alpha.
• beta cutoff: while minimizing, skips paths where we could choose an option better than beta.

It is of note that alpha can only be changed while maximizing, and beta is only changed while minimizing.

Let's look at the actual alpha and beta values while we traverse the above tree depth first:

- a 0
 - o 0
   - a 6     1. alpha: None      beta: Some(6)
   - a 0
     - a 7   2. alpha: Some(7)   beta: Some(6) => cutoff
     - a 3   3. skipped

Both alpha and beta do not propagate upwards however.

TODO: Add an example here, improve examples in general.

Other optimizations

alpha_beta uses iterative deepening, meaning that it first only checks the next moves directly, then it looks two moves ahead, then three and so on.

This makes it easier to run under some time constraint, as if we are unable to finish an iteration in time, we can always use the data from previous, shallower iterations.

It is also faster, as we can use the knowledge of previous iterations to adapt the order of our tests, which hugely influences the branches we can skip due to a cutoff.

The current implementation only remembers the best path of the previous depth. It may be advantageous to also store the best path the opponent can take for all other options, which may greatly improve the amount of possible cutoffs.

In case we were able to fully analyse an arm of the decision tree at depth n, we can use its fitness in all following iterations without having to recompute this possibility.

More interestingly, we can have arms which did not reach the current depth n and ignored sections due to an cutoff. As the alpha and beta values are often based on incomplete data, it is possible that the ignored section at depth n may be the best option at depth n + 1.

We therefore store all partially terminated arms with their best possible fitness, and only retest them in future iterations if their best possible fitness is greater than the current alpha value.

The fitness of the best fully terminated path is used as the initial alpha value of future iterations. This means that all partially terminated paths with a maximum fitness less than this alpha value can be ignored. This is implemented in fn add_complete and fn add_partial of struct Terminated.