@nickstadb
Blog FeedBetween March and June 2009 I entered a student programming competition ran by the British Computer Society. The aim was to create an artificial intelligence player for the game Connect 4 using Java and a provided Connect 4 framework. The competition was split into beginner and open branches with the definition of a beginner entry being one that doesn’t recursively build and analyse a tree of possible moves. Entrants had a 3 second time limit per move and were unable to store any state information between moves.
“SimpleBloor”
I chose to enter the beginner strand of the contest because it sounded more challenging to create a strong player that was not able to analyse thousands of possible moves. I based my strategy around the fact there are only 69 possible ways to win Connect 4. The final result looks ahead one move and it was beating recursive players that analyse tens or hundreds of thousands of moves about 30% of the time.
| Entry Name | Games Played | Games Won | Games Drawn | Games Lost |
|---|---|---|---|---|
| SimpleBloor | 1,950 | 1,332 | 62 | 556 |
I won the first prize in the beginner contest and received an additional prize for professionalism, which was described as “defining and presenting code in a comprehensible, easy to read and easy to follow manner”. Dr James Heather from the University of Surrey who helped organise the contest said:
“The code for the winning non-recursive entry was very good, I was very impressed by it and I strongly suspect that if that way of analysing the board was used to build a recursive strategy that it would absolutely thrash every other entry in the contest”
The final results table and full details of the contest can be found online at the BCS student contest website and a video of the awards evening is available through YPG.tv titled “YPG Student Programming Competition Awards”.
Play Against SimpleBloor
I have written a Connect 4 Java applet and adapted my Connect 4 player to work as an opponent in the applet. Click here to play Connect 4 against SimpleBloor. Please note that your web browser must support Java in order for the applet to run.
How I Created SimpleBloor
Using the fact that there are 69 possible ways to win (win lines) on a standard Connect 4 board I began by having the player create a list of all 69 possible ways to win a Connect 4 game – there are 24 horizontal lines, 21 vertical lines, and 24 diagonal lines. The idea was to look at the board and remove lines that couldn’t be completed due to an opponent piece lying somewhere along the line. Each board position sits on 3 to 13 different win lines with the central positions sitting on more lines than the edge positions. The first version of SimpleBloor used the number of potential win lines as the sole measure in selecting a move to play and as a result was very weak but able to beat a random player most of the time! Observing some test games I noticed that SimpleBloor would at times be one move away from winning but it wouldn’t make the winning move because another move lay along more potential win lines and hence had a higher value.
The value of each position on the Connect 4 board.
For the next version I adjusted the value of each move by also looking at how complete the potential win lines are. A move is favoured if it lies on a win line that already has other friendly pieces on it. This version highlighted a simple fact that I overlooked – the number of pieces required to complete a line isn’t equal to the number of moves required!
Both of these potential win lines for red require two pieces to complete, however the one on the left requires three moves to complete as opposed to two.
Move valuation was changed to take into account the number of moves required to complete potential win lines, as opposed to the number of pieces required. At this stage the biggest remaining flaw was that SimpleBloor had no defensive capabilities at all – it could be beaten in 4 moves with a horizontal line across the bottom row!
This is how easy it was to beat an early version of SimpleBloor!
This was actually quite easy to solve – whilst analysing the board to find potential win lines and move values I also analysed win line data for the opponent and used that to affect the value of potential moves. A move is then selected based on the following criteria:
- If a win can be achieved on this move, play the winning move
- If an opponent win line needs blocking then play an appropriate defensive move
- Play the move with the highest value
Further testing and observation revealed another flaw in move selection and lead to SimpleBloor looking ahead one move – at times SimpleBloor would play a move where the position directly above that move would allow a win for either player.
The light red moves would allow yellow to prevent or achieve a win at the position immediately above.
The competition deadline was closing in by this point so the final addition to SimpleBloor was to detect and avoid these situations.
Pingback: My Connect 4 AI Player – Source Code | NickBloor.co.uk
Hi, we met on the day of the BBC interview, I mentioned that I designed an AI for Connect4 too.
I followed a similar route to yours, but the requirements for my AI involved a board without a fixed size, and the length of the line to win the game depended on the size of the board, e.g. a 12×12 board required a line of length 8 to win.
My AI involved searching the board and generating a list of lines made on the board. I then had a function that searched the board for moves that would complete lines. This allowed me to play defensively and offensively at the same time, and worked well! The AI would look for lines that it could complete and win, and if it couldn’t, it would look for lines that the other player could complete and win. Then I repeated this, looking for lines with a shorter length.
I had to design this in a day though, as I was making a whole Connect4 game for my university project. I didn’t manage to get much further than that, but it still put up a good fight against most challengers
I had the same problem as you did though, with my AI only looking ahead one move. I’ll try to fix this problem and implement the value feature you have in your AI, and send you the result some time
I’m not sure how I’m going to value a resizable board, but I’ll give it a shot.
Did you design and build it in a day? That’s impressive! I went through many short development iterations with my AI, each followed by some serious testing.
Let me know if you make use of the board valuation idea, I’ll be happy to help if you need it. The value of each board position is simply the number of win lines that go through that position, so for example in a 3*3 noughts and crosses board with lines of length 3 the values are:
[ 3 ][ 2 ][ 3 ]
[ 2 ][ 4 ][ 2 ]
[ 3 ][ 2 ][ 3 ]
If we use the same 3*3 board and lines of length 2 then the values become:
[ 3 ][ 5 ][ 3 ]
[ 5 ][ 8 ][ 5 ]
[ 3 ][ 5 ][ 3 ]
I hope this helps!
Nick, I am in the process of modifying your code so that 2 people can play it. I have a couple of questions:
i. How does the code know to loop back to the begining if the game isn’t won. After the second AI move that is?
ii. Do I have to use seperate mouseclick events for both players?
Regards.