In this session, we started planning how we will build an intelligent robot that can play the game of Connect-4. Our aim is that it will be like playing against a human, with a physical Connect-4 set, not just a computer game. This is the plan we had come up with during our brainstorming the previous week, so this week we started to figure out how we can achieve this.
This will be a challenging project that the whole group will work on together. It will require lots of teamwork, collaboration, and learning.
The Major Components
We spent time thinking about the major components that our system will need, and planning the major tasks for these components on the whiteboard. They will include:
- A robot mechanism to play a move, which will involve moving to one of the positions 1-7 at the top of the board and dropping in a token, then reloading for the next time.
- A camera to view the board and analyse what it sees, to figure out which spaces have a red token, which have a yellow token, which are free, and whether anyone has won (4 in a row) or has a promising state (one or more 3-in-a-row).
- An AI decision-making system (see below)
- A software version of the game that we will find online and modify so that our AI can play it, so that we can work on the AI before the physical robot is ready.
For each component, we identified some major tasks and people volunteered to work on 2 major components each.
We also agreed that Python is a good programming language for the task, so we will have to brush up on Python next.
The Artificial Intelligence
The group spent some time playing rounds of Connect-4 against each other, in order to get us thinking about how we would design a computer strategy to play the game. Then we returned to the whiteboard, where people gave their ideas about the main strategies to be followed – these are on the right side of the whiteboard.
Some of the strategy ideas people proposed:
- Work towards 4 in a row (obvious but important!)
- recognise states with the potential for 4 in a row
- have multiple paths to win
- try to block your opponent.
This made me think of a general AI algorithm for playing 2-person games, called the Minimax Algorithm. This is based on constructing a game tree of all possible future moves, by yourself and by your opponent, for a number of steps into the future (called the lookahead or depth limit). Then, we evaluate all possible future game states using a utility function (also called fitness function): this will return a low value (e.g. -20) if we lose, a high value (20) if we win, or some other intermediate score if the game is not over, such as a count of the number of 3-in-a-rows we have, minus the count of our opponent’s (this will definitely be between 20 and -20). We will then pick the move that should lead to us a state with as high a utility as possible. Also, if we assume our opponent is rational, they will pick the move that will give us as low a utility as possible, so we can use the game tree to predict what their best possible move is, and be prepared for them! Each time they take a move, we can re-calculate the game tree to plan a new best move.
We then looked at the strategy ideas people had proposed, and saw how they are achieved by the Minimax algorithm, even though it’s a general algorithm, not just for Connect-4!
There are some good videos and tutorials about the minimax algorithm on line. Here are two that I liked: