Skip to: site menu | section menu | main content

Artificial Intelligence

“The question of whether computers can think is like the question of whether
submarines can swim.” --Edsger W. Dijkstra
 

My Artificial Intelligence Work

Here you can see some of the work I've done in AI, listed in reverse chronological order. Feel free to contact me if you have any questions or comments.

See also my article on game trees.

Alquerque (2007-2008)

Alquerque

This was my entry for CodeCup 2008, an annual game AI competition held by the Netherlands. My program won several of the practice rounds, and ranked 3rd place in the final competition.

The task was to write a program that played the game Alquerque, a board game similar to checkers.

Programs competed against each other in tournament-style, and were ranked by total points.

Some of the features of my entry, which could search to depths of 7-10, or even higher:

  • Alpha-Beta pruning with various alpha-beta tricks, move sorting, quiescence searching.
  • Optimized board representation, using bitboards for fast operations.
  • Timed moves in order to search to the maximum possible depth for each move, within the allotted time limit for each move.
  • Material value calculated as a logarithm of a quotient rather than a difference, in order to encourage piece captures when program is ahead.
  • A complete endgame database used to perfectly solve 1 vs. 1 positions.
  • Heuristic strategies for position evaluation, apart from move searching, in order to lower probability of a draw game, and to finish games as quickly as possible.
  • "Fastest first" heuristic used to first search positions with high probability of a fast cut-off.
  • "Cache effect", similar to a killer-moves heuristic, which increases speed by trying recently moved pieces first.
  • Hash-tables (though the nature of the game made it so that they were not very useful, so I disabled them).

Reversi/Othello Solving (2006-2007)

Reversi solving

This program finds the perfect play for Reversi (Othello) on a 6x6 board.

It only takes a few hours to search through over 20 billion positions in order to determine that if both players always make the best move, the second player wins by 4 (20-16).

The program is highly optimized, using 64-bit bitfields to represent the board, preprocessed tables for quickly finding and making legal moves, midgame searches for move sorting, and various other optimizations to allow it to search through several million nodes per second on an AMD 64. (I wrote it with 64-bit processing in mind.)

Chess (2003)

Chess

This is a program that plays chess. It follows all rules of modern chess, including en passant captures and rules for drawn games.

I wrote the AI engine back in 2002 when I was a senior in high school. It uses an alpha-beta search for searching the game space, along with a few optimizations and improvements to allow it to search deeper. It isn't exceptionally strong, but it does look several moves ahead, and will win against an opponent that makes any mistakes. Its main lacking features are an opening book, and proper endgame strategy, though it plays a relatively strong middlegame.

Later on, in 2003, I wrote a very simple GUI for it, which is what you see here.

Download:
HamedChess - Windows Executable (1.03 MB)
HamedChess - Windows Executable - Zipped (294 KB)

Caïssa (2002-2003)

Caissa

This was my entry for CodeCup 2003, an annual game AI competition held by the Netherlands, in which my program ranked 4rd place in the final competition.

The main feature of the program, aside from the usual alpha-beta searching techniques and optimizations, was the way the various coefficients that controlled the game analysis and therefore gameplay were determined: by the use of an genetic algorithm that generated, combined, and mutated different versions of the coefficient set. The coefficient sets were played against each other in order to quantify fitness values.

Hence the name, DarwinCaissa.

Download:
DarwinCaissa Source Code and Coefficient Set(28 KB)

Reversi/Othello (2002)

Reversi

Before I wrote chess, I warmed up by writing standard Reversi (Othello).

Using move sorting and alpha-beta pruning, the program searches to a depth of at least 7-8 ply. Combined with a very good analysis function, the program is quite strong, and beats all but the strongest of human players.

Please forgive me for the choice of colors. It seemed like a good idea at the time! ;)

Download:
HamedReversi - Windows Executable (380 KB)
HamedReversi - Windows Executable - Zipped (184 KB)

Geometry Solving System (2001-2002)
Automated Geometric Theorem Prover

Geometry

In my junior and senior years of high school, I worked on an automated theorem proving system for plane geometry.

It takes as input, a series of facts as well as the hypothesis to prove, and uses its user-defined database of base theorems to attempt to construct a geometric proof of the hypothesis. If it is successful, the complete proof is written in an organized form, as output.

The program defines a language for description of geometric objects within a plane (such as lines, points, angles, and triangles) as well as their relationships with each other (parallel lines, equal angles, etc.).

The language is used to define the base theorems, as well as the desired problem to solve.

Deduction is performed by using known facts, applying theorems, and adding new facts, while storing the reasons behind every fact, in order to be able to write the complete proof. In other words, it implements a forward chaining algorithm on the implicit underlying first-order logic defined by the system.

Back to top