Programming a board game AI

This semester, the final project of the problem solving class, which belongs to the computer science department, was to program an AI for a board game called Halma, whose variant is often known by the name Chinese Checkers.

Typical board game AI consists of following parts: move generator, evaluation function, and tree search. As the name implies, move generator generates possible moves; it encodes the rule of the game, judging which moves are legal and which moves are not. If move generator encodes the rule, evalution function encodes the "intelligence"; it is a function from the state of the game to some number. Usually, larger number means that the game is favorable to the player. But evaluation function doesn't need to be perfect; that's where tree search comes in. Tree search can "amplify" the minimal intelligence of evaluation function.

Because of such amplification effects, programming a board game AI is an eerie experience. When you program an unfamiliar game, it is a routine experience for your program to outperform you. It is more surprising since even the dumbest evaluation function can beat you. Often evalution function as simple as "substract the number of moves I can make from the number of moves the opponent can make" works surprisingly well. Notice that this function is not even game-specific.

In tree search, the program considers all moves I and the opponent can make to certain "depth", and passes resulting positions to evaluation function. The program assumes that the opponent tries to minimize the value of evaluation function, and tries to maximize the value of evaluation function after its move. The secret is that the program can examine a lot of positions quickly. In my case, the program searched to depth of 5 moves and examined millions of positions for a single move. This sheer quantity of positions compensate for poor quality of evalution function.

There are rich literatures concerning the programming of a board game AI. After all, people programmed computers to play chess as early as 1956. At this dawn of the programming, valiant programmers of Los Alamos laboratory programmed their huge cranking machine, which was actually less capable than cheap graphing calculators of today, to play a simplified version of chess on 6 by 6 board (see Wikipedia, Los Alamos chess). It won a game against a human who just had learned the game. We came a long way since then.

Geology

Shen Kuo(沈括) was a Chinese scientist of the 11th century. His work, Meng Xi Bi Tan(夢溪筆談), contains his scientific writings.

In one particularly stunning passage, he describes a theory of land formation by sedimentation, and an evidence for coastline movement. Following is the Chinese text and my translation. I got the Chinese text of Meng Xi Bi Tan from the Project Gutenberg.

余奉使河北, 邊太行而北, 山崖之間, 往往銜螺蚌殼及石子如鳥卵者, 橫亙石壁如帶. 此乃昔之海濱, 今東距海已近千里. 所謂大陸者, 皆濁泥所湮耳. (卷二十四)

When I was in Hebei, I went north, Taihang Mountains on one side, and between cliffs, often seashells and stones like bird's eggs crossed stone walls like a belt. Once this was the seashore, now a thousand li east of the sea. So-called continents are all submerged mud. (Volume 24)

This insight is comparable to that of James Hutton, a Scottish geologist of the 18th century, who is considered the father of modern geology. In Concerning the System of the Earth, its Duration and Stability, printed in 1785, he wrote:

Hence we are led to conclude, that the greater part of our land, if not the whole had been produced by operations natural to this globe; but that in order to make this land a permanent body, resisting the operations of the waters, two things had been required; 1st, The consolidation of masses formed by collections of loose or incoherent materials; 2dly, The elevation of those consolidated masses from the bottom of the sea, the place where they were collected, to the stations in which they now remain above the level of the ocean.

James Hutton is often unappreciated, but he must be considered as an equal of Isaac Newton and Charles Darwin. He published one of the most profound idea in the history of science, that the Earth is old. Like Darwin's theory, his theory challenged Christian doctrine, since it was incompatible with the account in Genesis. And it was the idea that the Earth is old, a half century later, that let Darwin think there was enough time for all life to evolve.

Witch on a journey

Some think that it is futile to translate poems, or lyrics for that matter. Many people try anyway. Here is my take on translating one of my favorite Korean pop songs.

Witch on a journey
included in "Welcome To My Beach", Kona (1997).

Now listen to my words
at least once a day
clean your crystal balls
get up early in the morning
drink a cup of white milk
and three lemon candies a day
don't forget to brush your teeth
before you sleep

A new wind is blowing for your journey
now raise your little broomstick
and fly to the blue sky
don't worry
and remember

Our beginning more mysterious than magic
the night and the shining promise
I will believe and wait
for the day you will come back to me
and we will start again
new days
in the wonderful world

Black cat's name's Pippi
and black dress is ironed
have you forgotten anything?
check again!

(Repeat)

Risk assessment

I know I am behind schedule in writing blog posts. Desperate, here is a quick translation of a short piece I wrote in Korean.

Risk assessment

In assessing risks, it is meaningless to assert that the risk of A is high because some B has the high probability of causing A. The high probability of causing A should be considered together with the probability of B itself.

Here is an example of the fallacy:

Mad cow disease has the high probability of causing death. Therefore, it is highly probable to die from mad cow disease.

Compare with:

Mad cow disease has the high probability of causing death. However, mad cow disease is rare. Therefore, it is unlikely to die from mad cow disease.