In your childhood days, you might have played the popular game called ‘Connect 4’. This game was very interesting while we are playing with our friends because of its interesting rules. If you haven’t played let me tell you the description about connect 4 game.

The Connect 4 Board Game Rules are easy to understand. In fact, it is in the name. To win Connect Four, all you have to do is connect four of your colored checker pieces in a row, much the same as tic tac toe. This can be done horizontally, vertically or diagonally. Each player will drop in one checker piece at a time. This will give you a chance to either build your row, or stop your opponent from getting four in a row.

Artificial Intelligence

Have you ever heard about AI playing board games like chess and beating the world champions. This is quite interesting about intelligence and accuracy of a Machine. So, here what we have done is, we have made a model which can play with human player ‘Connect 4’ game. We have implemented it with several AI algorithms like:

  • Monte Carlo Tree Search (MCTS)
  • Minimax Algorithm
  • Deep Neural Network Agent
  • Random Rollout Agent

Now, let us discuss these four algorithm in brief with more insights about neural network agent.

MCTS

The idea behind this algorithm is to create a game tree, but instead of exploring all the possible games, only the most promising routes are chosen. Every node in the tree store 2 values: the number of times the node was visited, and the number of wins the player won when visited this node. The algorithm contains 4 steps which repeats multiple episodes.

  1. Selection — you start in the root —The most promising child nodes are selected with a small chance to explore.
  2. Expansion — when you get to a node where there are child nodes that have not yet been visited, pick one randomly and expand the tree.
  3. Simulation — play random simulation until the game is over.
  4. Back propagation — back propagate to all the visited nodes, increase by 1 the visit number and if you win, increase by 1 the winning number.
Image result for mcts connect 4
MCTS

Minimax

Minimax is a kind of algorithm that is back tracking in nature used in decision making and game theory to find the optimal move for a player, assuming that your opponent also plays optimally.

In Minimax the two players are called maximizer and minimizer. The maximizer tries to get the highest score possible while the minimizer tries to do the opposite and get the lowest score possible.

Image result for Minimax connect 4
Minimax

Random Rollout Agent

This algorithm works in a very simple way. For every turn it analyze every possible move by playing some number of random games and then decide to play a move out of available move which move have the highest chances of wins. Normally, only 50 walks are required to play efficient game but it can be changed by changing the value of ‘walks’ variable. 

Python code used two functions to implement this:

  1. random_rollout : which analyze every possible move.
  2. random_walk : It plays a random game for every possible move. And make score.

Neural Network Agent

This agent simply takes current state as an input and predict the best possible move which can make agent win. 

Neural Network is made up of 4 hidden layers including one input layer and one output layer. Each layer is having 26 neurons in it and output layer have 7 neurons. This 7 neurons represents columns of a board and Neural network gives best possible column to play move.  Softmax_cross_entropy is used for cost estimation and AdamOptimizer for optimization of cost of neural network while back propagating. Neural Network is trained using random rollout agent played against another one with different walks. Model is trained on 150,000 games which are won by AI agent.

This neural network returns vector of size 7 which contain probability values for each column and we can select highest one to make it closer to win.

Image result for neural network 7 output layer
Neural Network Representation

Conclusion

We have tested all the models and tested them against one another. They were giving superb result and they were unbeatable in any case. This was much intelligent system to play game. They can be compare with regards to efficiency as:

Neural > Minimax > MCTS > Random Rollout