Tic-tac-toe

FINAL PROJECT REPORT

INTRODUCTION:

This semester has been one of the greatest for me as a student in this institution. Even though it had some rough times, it is still counted as one of the greatest. Eight mates including myself took the robotics class and to be honest, we were thrilled with the various activities we were engaged with. In each task, we were required to share our experiences in the form of reports. However, this is our final report, which is also part of our requirements in this course on our final project. Each student worked on a unique project and finally presented it on Tuesday, December 12, 2012. At the end of the day, each student, in my view, felt fulfilled and the purpose of this report is to give you the breakdown on my unique project.

BACKGROUND:

My project dubbed Tic-tac-toe, is a very common game that most people play. It is a two player game that is played in a 3×3 grid cell. To win in this game, you have the option of choosing either ‘X’ or ‘O’ as your character, and make sure that they all line up vertically, horizontally or diagonally. Furthermore, the game is referred to as a zero sum game, which is, when we add the number of wins and losses after a couple of games, the sum is zero. Tic-tac-toe is not the only zero sum game, we also have games like chess, checkers and others that are also known as zero sum games. The question is, what is unique about this project? There is not much difference in this project because it has the same rules in the mode of play however, the major difference is that, this time you are not going to be playing with a fellow human, if you are familiar with the game, but a robot – an NXT robot – that is smart and unbeatable. You may ask, what makes this robot smart and unbeatable, and the answer is quite simple. The robot uses two major methods, which I refer to as its “brain power”, which I will be discussing in a short while.

APPROACH:

As said earlier, my project is for a robot to be able to play the tic-tac-toe game with a human, and the method it uses to perform this task are two algorithms – Minimax, which is the main brain power for the robot to play the game; and wavefront algorithm for path planning, that is, to be able move through the 3×3 grid cells when the robot has decided where to play.

In details, the wavefront algorithm is used in path planning, to find the shortest and optimal way from a starting point to a goal regarding obstacles in various positions in a given map. Obstacle cells are labelled with the number 1, as in the figure below, and in my project, cells that were played by either the robot or human were considered as obstacle cells for the robot
after every move. So that the robot does not move through those occupied cells.

wavefront

The whole purpose for this algorithm is to prove to the human that the robot had identified the various moves made by both players, and will not tamper with those cells. Below is a true representation of how the game board, in this case, floor tiles was used to play the game.

grid
The second method was the minimax algorithm which has been proven to be one of the best algorithms for such games. It’s quite slow because of its complexity O(bx) but unbeatable. It is a very interesting algorithm and this report will give a brief description on So the region shaded was where the game actually took place (that is the 3×3 grid cell) and the unshaded region was the path in which the robot used to get to its goal whenever it was its turn to play. On the grid cell, you’ll find at the lower left corner, a cell labelled S, that cell was the robot’s starting point, that is, after every move, the robot finds itself at that location waiting for its turn. The second method was the minimax algorithm which has been proven to be one of the best algorithms for such games. It’s quite slow because of its complexity O(bx) but unbeatable. It is a very interesting algorithm and this report will give a brief description on how the algorithm works.

400px-ab_pruningsvg1

The figure above is a simple representation of the minimax algorithm in a typical game using a tree. The tree is made up of different parts. We have rows labelled “MAX” and “MIN”, and this will help explain the process. In the row labelled “MAX”, the algorithm checks all nodes and finds out which node has the highest heuristic (i.e. number on the node), then returns it to the parent node. In the case of the “MIN” row, the algorithm does the same check but this time returns the least heuristic to the parent. For instance, the first row for MAX from the bottom has different values. Let’s take the children 7, 4 and 5. The least among these is 4 so in the next row, that is MIN, the algorithm returns 4 recursively and this is done till it gets to the root, taking into consideration the MAX row as well.

Basically, these were the main components for my project. Breaking it further, my project was divided into 3 milestones:

  1. Implement the minimax algorithm.
  2. Implement the wavefront algorithm.
  3. Combine the two algorithms mentioned above into one program.

Each milestone had a duration and it lasted at least one week before the final day of presentation. So work had to commence immediately the project and its milestones were clear.

RESULTS:

The project was successful after the duration given us, however, milestone 3 couldn’t be accomplished, but I had two different programs, that is, milestone 1 and 2 ready. Milestone 3 couldn’t be done because I had to translate the minimax algorithm from the C language to ROBOTC, the language for the robot. Some of the syntax in the C language were not as the syntax in ROBOTC, and it really was a struggle, but it didn’t stop me from having my final presentation. So I deduced a way for my presentation, which was to run both programs together but on different platforms. It was successful, that is, the robot could play a game with a human but it was just slow. A typical game could take 4 to 5 minutes before it ended, whereas it could have been shorter if milestone 3 was completed.

CONCLUSION:

“There are no secrets to success. It is the result of preparation, hard work, and learning from failure from failure” – Colin Powell. Even though my project didn’t see full completion, it was hard work that brought to me even to the point of presenting a pretty good work. It has been an honour to be part of this journey.

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s