As we plan our AI robot to play Connect-4, we have decided that Python would be a good programming language for the job, as it is widely used for many of the tasks we will need to do:

• Computer vision
• Artificial intelligence
• Hardware control

Therefore, we spent time this week brushing up on Python. Following the same approach that we had used previously to move from Scratch to C, we looked at how we would move from programming in Scratch to Python.

Here is the full set of notes (PDF): CoderDojo-Hackers-IntroToPython

Kevin then spent time explaining how to write a basic Python program to read an image from a webcam. Here is the code:

# We are using OpenCV
import cv2

# Capture webcam image
camera=cv2.VideoCapture(0)
val, img = camera.read()

# Display the image
cv2.imshow("Window display", img)

# Stop using the camera
camera.release

The Goal

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:

1. 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.
2.  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).
3. An AI decision-making system (see below)
4. 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:

• https://towardsdatascience.com/how-a-chess-playing-computer-thinks-about-its-next-move-8f028bd0e7b1
• https://www.youtube.com/watch?v=l-hh51ncgDI