|1. Pangki God
2. Maim Chess
3. Triple Jump
Retrograde Analysis Game Solver
Checkers (Draughts) Engine
Tic-Tac-Toe Playing Program
|November 18, 2001
January 28, 1998
October 16, 1997
June 11, 1993
Pangki God is a retrograde analysis endgame database solver.
It was created as a personal experiment to solve a simple perfect information
two player game (i.e. a game in which no luck is involved, and both opponents
know the full exact state of the board at any given time).
Pangki was chosen because 1. it is an extremely simple game,
2. I could not find that it had already been solved,
3. I had a computer opponent to test the results against.
Normally, retrograde analysis is used to solve as much of a game's endgame as
possible, but because Pangki is so simple, its entire game tree can fit
into the memory of a regular home computer, and thus it can be solve in its entirety.
Pangki Starting Position
Legal moves involve moving any one piece orthogonally
(either left/right or up/down)
into an adjacent empty square.
Captures involve placing two of your pieces directly against a single
opponent's piece all in the same row or column. This can
result in two captures in the same move. The fourth
square of this row or column must be empty, which implies
that you cannot capture a piece with three pieces in line with
a single opponent piece, and you cannot capture either opponent
piece by sandwiching two of your pieces in-between two opponent
pieces. The game ends when a player only has one piece remaining
(as you cannot capture any further opponent pieces with only
a single piece), or when you have no legal moves
(which is sometimes much quicker to do on a crowded board
with only 4 empty squares, rather than tactically capture five
For all of the positions that have a legal number of pieces for both sides
(with the exception of one side having only a single piece - which are all
positions in which the game is already over),
I have found the following (note that there may be positions
which have the proper number of pieces, but may be impossible to reach):
These numbers are encouraging for the enjoyment of the game, since so many
of them are non-drawing positions. Any game which is too easy to draw
is not usually a fun game to play.
Out of these 20,746,908 legal positions, there are 123,439,680
possible legal moves, making an average of 5.9 legal moves per position,
which approaches the average number of legal moves for both checkers (draughts)
and othello (about 7 and 8 legal moves per position, respectively).
Download: Pangki God (53KB)
Note: The creation of the database can take hours, depending on the speed of your computer. It takes 51 minutes on my Athlon XP 2500+: "Pangki has been solved in 3037 seconds."
|MAIM CHESS v0.31
Maim Chess was a 3rd year Software Engineering
project at Acadia University.
The purpose of the project was to use the software engineering approaches covered in class
to engineer, develop, and implement a program of my choice in its entirety from scratch.
I chose a chess engine because of my interest in Artificial Intelligence.
The entire time frame of the project was restricted to
8 weeks and 30 man hours, which was met. This time frame included
the original and revised proposal, the engineering, designing, implementation
and the 2,000 word final report of the project.
Maim Chess was chosen as the name of the project as an incentive to create
the strongest playing program possible within the time constraints.
Download: Maim Chess v0.31 (135KB)
The program should run on a 386+ processor.
Here is a game I played against Maim Chess set to think 10 seconds per move
on a Pentium III 550 MHz processor.
Although I made a tactical error, which
Maim Chess capitalized on, I cramped its King and Bishop into the corner,
rendering the Bishop useless, and its King in an awkward position.
A cramped position like this is something that is relatively hard for computers
to understand, even with deep analysis.
Please view the game below using the
MyChessViewer 2.2 Java PGN viewer,
which I modified to use my own rendering
(specifically for this applet)
of the beautiful
Chess Alpha font / piece set
(If a chess board does not appear above, you do not have Java on your machine. Please download it from http://java.sun.com/.)
Here are several annotations of the game above available for download:
Download: .PGN File - Jason Doucette's Annotation, Chessmaster 8000 Score Analysis, Chessmaster 8000 Auto Annotation
Download: .TXT File - Maim Chess Output
|TRIPLE JUMP v0.30
Triple Jump is a checkers (draughts) playing program.
It was a project created during my 3rd year Artificial Intelligence
at Acadia University.
The project was not required for the course,
but the course raised my interest in Artificially
Intelligent programs. So, I decided to implement one on my own.
The project was completed in 2 weeks.
It also suffers from the lack of an end game database, and therefore plays the endgame poorly. Regardless, you have to be a very good checkers player to beat Triple Jump - you will only notice it's weak endgame play if you can reach the endgame. And even then, you cannot play carelessly - Triple Jump was once down 3 pieces to 4 against an experienced player, and it sacrificed a piece to set up a position in which it quadruple jumped all of the opponent's remaining pieces. Obviously embarrassed, the opponent left without saying a word - I would expect that this was probably the only game ever in which an experienced player suffered a quadruple jump to lose the game. This is just an indication that you cannot start to play carelessly at any point during a game, or you will probably lose.
Some of the above pictures show amazing wins that Triple Jump solves.
And you thought that checkers was a kids game...
To announce a forced win, Triple Jump must analyze every possible outcome of the current position,
all the way to the end of the game - where one side has either lost all his pieces, or
rendered them immobile.
For example, Triple Jump must see 17 moves ahead to announce a "White to Win in 9"
- 9 moves for white, and 8 response moves for red.
In the third picture above, Triple Jump solves an amazing position composed by
as a win for white in seconds.
In case you are curious, best play for both sides is shown in the following table:
Try it, and see!
In the sixth picture above,
Triple Jump is about to play 10-15, which appears to be an error!
The move allows white's king to split the advancing pieces (by playing 7-10),
something a complete beginner can see.
White will win one of the two checkers in it's next move.
Why would Triple Jump make such an error?
It has not made an error - Triple Jump has just played a trap.
Would you have fallen into it? If white falls for it by playing 7-10,
red wins in five moves. Can you see the win?
(Hint: first move to lead to win is 14-18 or 15-18)
Remember, the official rules for Checkers is that you must jump, if
you can. This adds a lot of strategy to the game. It is, by no means, only a
The program should run on a 386+ processor. I know the user interface is not the greatest in this program, and I apologize for this.
Tic-Tac-Toe was a grade XII computer programming final project. The course taught Q-BASIC, and the second-to-last project covered double-nested loops! Considering that I used a FOR-NEXT loop in probably one of the first BASIC programs I had ever written in grade II, this was not a very challenging course, needless to say. The final project was a random question out of the final chapter of the book. Since my question was very simple, I asked to program an artificially intelligent tic-tac-toe program instead, and the teacher accepted.
The program is coded in BASIC, and does not use search tree methods. All AI is programmed via patterns in the board. There are 4 levels of difficulty, each level checks for more patterns (threats) and plays tougher. The highest level, as you probably guessed, will never lose.
Download: Tic-Tac-Toe (290KB)
Q-BASIC (included) is required to run the source code.