Add Dynamic Programming

[VictorXjoeY]

I removed it because there were some issues with the whole pruning logic but it's now time to add it back!

The DP should look like this:

unordered_map<StateType, vector<OptimalMove>> dp;

And let's make sure we treat cycles properly. Likely with something like this:

unordered_set<StateType> in_stack;

We might need to consider the pruning values alpha and beta for storing pre-calculated states in the DP, therefore the code below is likely incorrect but it's a starting point.

vector<OptimalMove> &ans = dp[game.get_state()];

// Initializing all moves with the worst possible score.
if (ans.empty()) {
    ans.reserve(moves.size());

    for (const MoveType &move : moves) {
        ans.emplace_back(move, 2.0 * game.get_enemy());
    }
}

if (ans[0].winner.has_value() or ans[0].height >= height) {
    return ans;
}

[VictorXjoeY]

It's the Iterative Deepening that guarantees that the AI will always take the shortest path to victory because the move is returned as soon as it hits a depth in which it finds victory. This means that we will encounter issues if the AI has "memory", i.e.: if the DP is not empty when Minimax::get_move is called.

[VictorXjoeY]

Before adding the DP I should probably add the move-sorting heuristic by saving moves inside Minimax for each state and sorting them according to the score (according to the better_max and better_min actually).

"As the number of positions searched decreases exponentially each move nearer the current position, it is worth spending considerable effort on sorting early moves. An improved sort at any depth will exponentially reduce the total number of positions searched, but sorting all positions at depths near the root node is relatively cheap as there are so few of them. In practice, the move ordering is often determined by the results of earlier, smaller searches, such as through iterative deepening."