Adversarial Search Methods

In computing, it is usually required to solve a logical problem. As the complexity of the problem increases, it also becomes harder to find a or the best solution. Search methods is a broad field that aims to solve problems by defining different states of the problem and then transitioning through the states to find the optimal solution.

Search methods are a form of Artificial Intelligence. AI is a vast field as it is understood as the technique to use computers to mimic human behaviour. This is why pretty much every algorithm could be considered as Artificial Intelligence. Search methods are part of the cognitive simulation approach of AI as they simulate human cognitive abilities (e.g. problem-solving, object recognition).

As stated, search methods transition through a problem space. For a travelling salesman problem (TSP) each node of the problem space is the next city the salesman could travel to. In this scenario, the problem state is purely defined by the actions of the salesman. The algorithm can evaluate the quality of each node without making any assumptions. However, this changes entirely if a second salesperson comes into play, who compete against each other. Now the quality of the next node also depends on the actions of the other salesman, the opponent. For these kinds of scenarios, or any kind of scenarios with an opponent in the search space, adversarial search can be used.

As part of my master studies, I looked at different adversarial search methods for two-player games. I implemented four different algorithms that can be applied to either a game of Tic Tac Toe or Connect Four. I chose to build this web application, to conducted various experiments to gain a better understanding of their strength and weaknesses.

I provide a brief explanation of the boards and algorithms. At the bottom of the page, a single game or multiple games can be simulated. Additionally, my report can be viewed. Please note, that this page is only partially optimised for mobile devices. Also, be aware that all calculations are performed on the client, your device. Therefore, the performance of your device results in the performance of this app.

Boards

Tic Tac Toe

A board with 3x3 fields, where any player can access every empty field at any time. The game is won by the player who has three connected fields vertically, horizontally or diagonally.

The depth (number of simulated moves) is set to the maximum of the number of available fields.

Connect Four

A board with 7x6 fields, where players can only access fields if the field below is already occupied by any other player (this excludes the first row). The game is won by the player who has four connected fields vertically, horizontally or diagonally.

The depth (number of simulated moves) is set to 4.

Algorithms

Random

This algorithm simply picks a random, accessible field.

Minimax

The minimax method utilises a score that one player tries to minimise while the other aims to maximise it. If a player uses the minimax method, it looks at the next n moves and all possible game states S after each move. It assumes that the opponent tries to minimise the score and then makes the move that should result in the overall highest score after all n moves.

For Tic Tac Toe the number of next moves is the number of available fields. For Connect Four, the number of next moves is limited to a maximum of four.

Alpha Beta Pruning

This algorithm is an optimisation of the minimax method. Rather than looking at all possible game states the algorithm ignores certain game states, that have no chances of being selected. This is done by keeping track of already visited nodes (possible moves).

Even though this method does not evaluate as many game states as the minimax method, it may still take a long time to process.

Genetic Minimax

In games, time is usually a constraining factor that might not allow for the use of the minimax or alpha-beta pruning algorithm. For complex problems with a large set of possible solutions, it is sometimes better to make random decisions instead of evaluating all possible nodes. Genetic (or evolutionary) algorithms make use of that. They start with a random set of solutions and evolve this population over n generations.

The genetic minimax method does that and evaluates the population using the central concept of the minimax algorithm. While it may not always find the best solution, it may find a near best solution in a shorter period.

Select Mode