Othello AI

Othello (a variant of the traditional game Reversi) is a two-player strategy board game played on an 8×8 square field, where each player takes turns placing black or white pieces and capturing the other player’s pieces.

Figure 1. Othello board game.

The Othello AI program is the second board game AI that I have written in junior high school (the first is the Tic-Tac-Toe AI). Just like the programming strategy for the tic-tac-toe AI, I used the logic thinking experiences that I had learned while playing this game, and hard-coded some summarized strategies into this program.

Compared with the tic-tac-toe AI, which has a game-tree complexity of 9! = 362880, Othello is much more complex, yielding a stunning complexity of approximately 1058. This makes the game still mathematically unsolved up to this very day. Therefore, instead of calculating the definite winning strategy, this Othello AI rather tries to find relative advantageous points (e.g. the corners), and moves that will temporarily maximize the number of pieces which it occupies by the coded algorithm, making it a beginner ~ intermediate level AI.

Here is a demonstration of using the Othello AI program:

[Download Othello AI program]

[Source code for the Othello AI program (Visual Basic 6.0 form file)]

Sudoku AI

Sudoku is a commonly known logic puzzle game, and had been one of my favorite puzzle games.

Having the experience for creating the simple Tic-Tac-Toe AI, I started to take on this challenge for creating an AI that can solve Sudoku.

Figure 1. The initial and complete board state of an expert-level Sudoku game.

I had written this AI program when I was in junior high school using Visual Basic 6.0. Having no prior knowledge for algorithms and data structures (which I learned in senior high school), I came up with a rough version of the backtracking algorithm myself, and implemented it on the AI. Here, the backtracking algorithm is a kind of depth-first search (DFS), and is guaranteed for finding a valid solution. Constraint programming is also integrated with the backtracking algorithm, since it is a very intuitive way for solving the puzzle.

Here is a clip demonstrating the Sudoku Solver program solving a hard-level Sudoku in around 5 seconds:

Here is another one that solved an expert-level Sudoku in around 44 seconds:

[Download program for the Sudoku Solver]

[Source code for the Sudoku Solver (Visual Basic 6.0 form file)]

Tic-Tac-Toe AI

Artificial intelligence (AI) has long inspired me, and had spurred me on to come up with interesting programs or projects that I had not imagined before. Since great oaks from little acorns grow, this tic-tac-toe AI project is the first and one of the most important programs I have made that can be said to possess artificial intelligence. (~age 15, 2011)

Either with the player playing first or the computer, the AI will never lose! Being a very simple game that one could easily master, tic-tac-toe can yet be quite complex in a way in that there is actually a total of 255168 possible outcomes! Fig. 1 illustrates all the possible board states until the 5th move using an optimal strategy with the 1st move at the center (States that can arise from mirroring or rotating the shown states are excluded). The green circled states are those which the circles have won, and the yellow ones are those which the circles will eventually win while continuing to implement the optimal strategy. We can see that it actually gets quite complicated after the 3rd move.

Figure 1. Possible states of Tic-Tac-Toe until the 5th move starting from the center.

Since back then I knew nothing about algorithms (which I had started to learn at senior high school), I hard coded almost all the conditions using very basic syntax: If…Else…End If and For…Loop. The AI will sometimes move randomly, but it will always follow an optimized strategy. It took me ~650 lines of code and several days of hard work to complete.

This project demonstrated the possibility of programs to achieve human level performance for playing simple games. Although objectively not considered an astonishing one, I was surely amazed and unprecedentedly inspired by the potential of programming algorithms for AI; which further on motivated me to create AI programs of increasing difficulties (refer to Gomoku AI, Sudoku AI, Othello AI, Nonogram AI, Guess the Number AI, Minesweeper AI).

Magic Cube Simulation Program

Magic cube, or the Rubik’s cube, is a popular 3D puzzle known by almost everyone in the world. There was a time when a lot of classmates in our class (including me) were crazy about this game. Everyone was trying to remember the awkward patterns and formulae for not only figuring out this puzzle but beating each others time records. Being very fond of designing games using Visual Basic and inspired by this puzzle, I constructed this simulated program for playing the magic cube.

A player can enter in commands on the input field according to the description (e.g. k = turn right face 90° clockwise, a = Reset cube …) in order to control the cube. The program would only show the front, right and top side of the cube, so the player should have to rotate the whole cube using certain commands for observing every side. Although it is more difficult to solve a scrambled cube for a normal human using this program, it is still possible if one takes time :). Lots of geometric concepts were used when designing this program. For instance, how should the data structure look like in order to record every block of color on the 6 sides of the cube? How can the variables be permutated if a certain command (e.g. turn top face 90° counter clockwise) is executed? How to even draw the cubes diagonal view?

I learned a lot myself from creating this program, gaining insights into various seemingly simple but somewhat counter intuitive geometric and algorithmic concepts.

[Download Program]

Guess the Number (Windows)

This project is the first of the three “Guess the Number” projects that I’ve completed (before Guess the Number (iOS) and Guess the Number AI). I had played this game long before I wrote this program. During the period when I was self-learning Visual Basic, I decided to make a program of this game which the player guesses the number randomly generated by the program.

The two-player game is also named Bulls and Cows, which one player thinks of a four-digit number with every digit being unique and the other player trying to guess that number. During each turn, the player who guesses speaks a number while the other replies with how many A’s and B’s according to the relationship between the guessed number and answer. The number of A’s indicate how many digits in the guessed number are identical with those in the answer and are on the same location; the number of B’s indicate how many digits are identical but aren’t on the same location (e.g. 2A1B should be replied when a guessed number is 1234 and the answer is 1532). The player guesses until the answer is guessed and the round ends. Players may take turn playing the opposite role and try to guess as few times as possible.

This mini-project encouraged me to design more complex programs, and is an important milestone in my journey of programming.

[Download Game]

Racecar

Once upon a time, when cell phone screens were only black and white…

This game “racecar” had been the most interesting one on my first Motorola cell phone. Learning Visual Basic on my own, I had tried to mimic and construct games that I’d played before, hoping one day I could make up some fantastic ones of my own. Racecar is a simple successive one at the initial stages of my self-learning of programming.

The player first picks a game level from 1 to 9, game starts after the countdown of 3 and three adjacent blue squares representing a racecar travels down a track where obstacles will be encountered frequently. The player can move left or right in order to dodge the obstacles, and the longer he survives, the more points he will get.

This project is the first game for me to implement programmable drawn shapes as the objects, and led me into the discovery of the important fundamentals of program logic.

[Download Game]

Bomberman

Bomberman has always been a popular online multiplayer game. Having the experience of creating several applications and games using Visual Basic (VB) (Racecar, Guess the Number (Windows), Simple Magic Cube, Tic-Tac-Toe AI, Sudoku AI, Othello AI, …), I decided to design a multiplayer game using VB. This is the final project for using VB as the programming language in my junior high school period.

Figure 1. Snapshot of game start on a 10×10 grid.

In this game, the players decide the size of the game grid (an NxN square grid), the number of walls and the total number of items. Then player 1 starts at the bottom right corner and player 2 starts at the top left corner of the grid (Fig. 1). Player 1 and 2 walk around and drop bombs at preferred locations and the placed bombs would explode after a few seconds. A player wins if the other player is within the explosion range of an exploded bomb. A wall would disappear after being hit by a bomb. Initially, the players can only wait for a bomb dropped by themselves to explode before dropping another bomb, and the explosion range is a cross section extending one lattice away from the dropped bomb’s location. The number of available bombs and explosion range can be increased by obtaining items that were initially hidden behind the walls. The images used in this game are shown in Fig. 2.

Figure 2. Images used in bomberman. (Left to right: player 1, player 2, wall, bomb, bomb explode fire, bomb increase item, explode range increase item.)

Although being a highly simplified version of the original online game, this project demonstrated the ability of using VB for designing multiplayer games and deepened my programming abilities.

[Download Game] (The jpg files need to be in the same folder as BBMan.exe)