Could a simple AI beats us at connect 4 ?
Check the code »
Report Bug
•
Request Feature
The connect 4 is a simple game where you have to align four of your coins on a same row, column or diagonal. Usually, this game is played on a 7x6 grid. However, in this imlementation we complicated things by playing on a 12x6 grid.
Could an AI beats us at this simple game? Let's see.
The AI implementation use a simple and well known algorithm called minmax. This algorithm comes from the Game Theory and can be explained easly. Let's first concider the connect4 game. It's a sequential game, where all players know all the information of the game (eg position of all the coins). This game is not a cooperation game but a null zero sum game where each player action aims to increase its payoff and decrease the opponent's one. Therefore, the players actions tend to follow the MinMax von Neuman theorem where the game can be modelized in a normal shape and each action can be predicted using a backpropagation of the potential payoffs. Let's analyze the following example:
Here we see that the player 0 (max) can predict the payoff brought by each action by simulating for each of theses action the next most probable action of the player1.
This strategy is great, and have wonderful results for simple games. However, it's also a heavy method which require to explore the tree of the game until its end which for the connect4 game (and especially on a 12x6 board) is not possible. One of the optimisation we implemented is the alpha-beta pruning. But even by using this technic, the AI is block at a depth of 4 or 5. We are then forced to implement an heurisitic function which will be charged to approximate the payoff of a state of the board by concidering only the next actions at a depth of 1. The power of the AI is strongly determined by the type of heuristic you implement.
We choose to implement the following heuristic:
The score of a board state is the sum of the payoff of each actions minus the opponent payoff for each of these actions. Moreover an attack and defense coefficient is added to push to take risky decision or to play for equality.
Now we can analyse how do we compute the payoff of an action.
Here we compute the score of the action according to its relevancy on the current row, column and on the two diagonals. This score is computed using a simple rule:
For each 4-subsets of the row/column/diagonal we count how many of the player's coins are in the row and we set the fitness as a polynamial function of this count
Were are good with the explanations! Let's move to the tests.
You will just need python >= 3.0. You can check the version by using the following command.
> python -V
> 3.0.0You can follow the different steps inorder to get the programm working on your computer
- Clone the repo
git clone https://github.com/VictorGoubet/ConnectUltra.git
- Install python packages
pip install -r requirements.txt
- Execute the python script
python ConnectUltra.py
The windows should appear! The interface is pretty intuitive, have fun!
Victor Goubet - victorgoubet@orange.fr