Category: 1 Person

Gomoku AI

Posted on | by andrewlai61616

Although entering a department different from Computer Science (CS), I still had a majority of acquainted people in NTU-CS. One day, a friend of mine who was studying in CS challenged me of making an AI of some board game. The two of us would make AIs of that game and try to win the other one using the AI. Thinking it might be some challenging but interesting subject, I started to make this Gomoku AI.

Figure 1. Game playing demonstration of the Gomoku AI program.

Being a board game with so many possible states (more than the Othello AI I had made when I was in junior high school, which only has a 8×8 grid) , it is considered overly time wasting for the AI to traverse all the possible combinations, even just within 10 moves! Game tree graphs, graph traversal algorithms (e.g. DFS, BFS) and optimal searching algorithms (e.g. Alpha–beta pruning, A*) are usually implemented for decreasing computational time and achieving the best strategy. In this project, I only used the depth-first search (DFS) algorithm, along with some hard coded optimization decisions to create this program. Although being able to place a few initial pieces successfully, the program suffers from a large amount of computational time being spent. Most of the time after a few moves, the program will just run for a few hours (or days) before taking the next move, which is obviously very a serious problem for the AI.

Nevertheless, the environment and rules of the Gomoku game engine was successfully constructed, which allowed two players to play against each other. Nowadays, these board game AI are usually designed using deep neural networks, such as AlphaGomoku, an Alpha-Go-based Gomoku AI. Constructing these AIs would be a possible future work for optimizing this game agent.

Tic-Tac-Toe AI

Posted on | by andrewlai61616

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).

Heat Transfer Dynamic Plotting

Posted on | by andrewlai61616

It may often be increasingly hard to comprehend dynamic properties using only static figures shown on a textbook. There is more need for data visualization for better understanding the complicated world around us…

This is a demo program that I have written in a course of heat transfer. I served as the teaching assistant and assisted my professor for delivering the curriculum. In order to let the students understand some time-dependent properties between the temperature and position of a heat transferring process, I used Python and the library Matplotlib for customized visualization of the heat transfer process.

Compared with a static plot of the same process (Fig. 1), this dynamic plot (Fig. 2) intuitively demonstrated the nature of temperature change according to time.

Figure 1. Static plot of normalized temperature (1-Φ) vs normalized position (η) at different normalized time (τ) using OriginLab.

Figure 2. Dynamic plot of heat transfer.

T-Rex Game

Posted on | by andrewlai61616

This is a simplified game mimicking the T-Rex dino game appearing on the “No Internet” google page. The motivation for making this comes from a YouTube video where a program learns to play the game at superhuman level using genetic algorithm. It was quite fascinating knowing the fact that nothing has to be taught in order to let this program acquire the ability to jump over obstacles, dodge birds … etc.. I made this game using C, with the console being the gameplay screen. However, due to the fact that characters instead of figures were drawn, the screen will always be in a flickering condition for renewing the screen at a rate such quickly.

[Download Game]

Blackjack

Posted on | by andrewlai61616

Blackjack is a well-known gambling game and is the most widely played casino game in the world. Numerous researches about this game had been carried out, including machine learning of optimal actions for playing the game (see reinforcement learning for solving Blackjack).

I got particularly interested in machine learning during graduate school. Thus, I made this simple Blackjack game program in order to construct a game environment for reinforcement learning of game agents for future work.

The game process is a single round of Blackjack, starting from player 0 being dealt 2 cards from the dealer. The player can either choose to “hit”, “stand” or “split” according to his cards. After the “stand” action is chosen or if he goes busted, The next player follows on.

I wrote this game using C language, which runs on a command prompt. While being simple, It can provide useful insights to game agents which can further learn on its own for achieving optimal behavior.

NTU Library 3D Drawing

Posted on | by andrewlai61616

This is a model of the library of National Taiwan University (NTU) and was created using Solidworks. This project was originally a homework from the course “Engineering Drawing” of our department. Being fascinated by the features and functions provided by the 3D CAD drawing software, I took “the hard way” by choosing this architecture as the target for this homework.

Figure 1. Solidworks Components of NTU library.

Partial images were downloaded and pasted for being the surface material of individual components of the library. I searched for some 3D images of the library and managed to duplicate the outline and structures onto the parts (Fig. 1). Taking a large amount of effort constructing and assembling the pieces, I gained a lot of experience finishing this project. After completing this project, I learned some important concepts of 3D drawing which provided me to design other structures for 3D printing in further projects.

Figure 2. Diagonal view of the assembled NTU library.

Magic Cube Simulation Program

Posted on | by andrewlai61616

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)

Posted on | by andrewlai61616

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

Posted on | by andrewlai61616

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

Posted on | by andrewlai61616

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)