I am happy to say that I have finished programming my Draughts game. If you have been following my Twitter then you may have noticed that there is one thing holding me back from releasing it, memory leaks. I personally expected to have a few since I haven’t had a great deal of experience writing more sophisticated applications in C/C++. I got around to checking these leaks the day before I was heading back to University for the semester so I haven’t been able to address all of them yet but plan to soon. For the mean time I would like to discuss the AI that I have used in this game.

One of the fundamental concepts behind AI is the Turing Test as discussed in Alan Turing’s 1950 paper “Computing Machinery and Intelligence“.

A human judge engages in a natural language conversation with one human and one machine, each of which tries to appear human. All participants are placed in isolated locations. If the judge cannot reliably tell the machine from the human, the machine is said to have passed the test. In order to test the machine’s intelligence rather than its ability to render words into audio, the conversation is limited to a text-only channel such as a computer keyboard and screen.

With this in mind I decided to brainstorm several things that would cause my game to fail this Turing Test. The first notable thing is moving a piece into a position in which the opponent can jump that piece when there are other more advantageous positions on the board. The second is if the computer player doesn’t take the obvious jumps and double jumps. To put these into play I decided to assign a priority to all of the possible moves that a computer opponent could take. Any moves which resulted in capturing an opponents piece would would receive an increase in priority and any moves that resulted in being captured by the human player resulted in a decrease in priority. The computer would then take a random move out of the list of moves with the highest priority.

The system described above is the crux of the AI. Overall effect works really well towards the start of the game but sort of falls apart as the pieces become scattered across the board since the AI moves pieces at random. I’d like to think that the aggressiveness of the computer early on makes its flaws less apparent towards the end but this not always the case.

Thanks for reading. Hopefully towards the end of this week you should be seeing the source code of Draughts here. For now enjoy some of these screen shots.

So far I’ve been working on the Draughts project for several hours over the last week and I am happy with the progress that has been made. I am right on target to meet both deadlines that I have set. One thing that I have underestimated is the amount of planning that was required. Initially the overall game structure was planned out. This included things such as the data structures used, object orientated models and code structure. There are two things that I didn’t plan for and I want to talk about them today.

The first issue I found is how the player should move their pieces. I wanted to make this process as intuitive as possible, so intuitive that the user wouldn’t need the controls explained to them. I came up with two strategies to solve this issue.

Drop and Drag

The drop and drag method involved the player clicking on the piece and then dragging it to the location they desired. My first thought was that this approach was rather intuitive since it mirrors the movements that someone would take in real life. I then thought back to my experience with other games that required you to move pieces such as Puzzle Quest and Bookworm Adventures. Both of these games don’t make you drag pieces across the screen and there is a good reason for it. After a while it becomes a tedious process. Other issues arise such as collision detection between pieces and squares as demonstrated below. Technically it also ads to the code complexity and processing oomf that is required.

Refresh five times or twice?

Click and Select

This method is the one I used in my version of Draughts. It is simple to program and simpler for the user. You simply click on the piece that you want to move and then click where you want to move it. One of the greatest benefits compared to the previous approach is that you are required to update the screen less often. You only need to refresh the screen once the player has made a choice and then refresh the squares that are modified in that choice which tends to be two squares. The square where the piece existed and the square where the piece moves to. Whereas with the drop and drag approach you have to update the screen every time you incrementally move the mouse, in order to create the result of the piece following the cursor. What makes this worse though is that you also have to refresh the squares that the piece moves over.

The second issue that I came across was how to handle the multiple jumps in draughts. Initially I wanted to show all of the possible moves a player could make in one turn and highlight the respective squares. This became impossible when you think about trying to represent it on the screen. What struck me though was that by showing all of the possible moves to a player was that I was showing them too much. So I decided to limit the scope of what was shown. This was restricted to a domain of one jump. Since most players would naturally recognise one jump moves I decided that there was no real advantage of showing them the potential moves. To handle multiple jumps I decided to break the moves up into single jumps in which subsequent jumps are still highlighted and forced the player into not being allowed to revert their previous jump. I also allowed the player to choose to not undertake a subsequent jump if they choose not to.

Double meaning

By the time you read this I should have finished the base functionality. I was intending on posting my current progress online but I am requesting permission to use some music and haven’t received that yet so I will hold off until I finish it. Will be done soon.

As I mentioned in my last blog post the first project that I plan to share is a draughts game. The aim of this project is to give myself some practice with SDL and an idea at the sort of time frame I can produce small games in. Below is a rundown of the current specifications and milestones of the project.

Draughts Game

Programming Language: C++

Libraries: SDL, SDL_image, SDL_ttf

Baseline Functionality:

• Human Controlled Game of Draughts for two players
• Piece Movement and capture
• Piece advancement
• Graphics Blitting
• Background Music and Sound Effects
• Simplistic Game Configuration

Advanced Functionality:

• AI based Opponent
• In Game Configuration
• Game Menus and Restarts
• Move Count
• Match Timer

Time Frame: Baseline Functionality 10 days – 21st February

Advanced Functionality 15 days – 26th February

Over the development period I will post some details about how things pan out. Hopefully I can finish everything well before the expected time frame.