Jason Doucette / Xona Games
 
hometown – Yarmouth, NS, Canada
residence – Seattle, WA, USA
university – Acadia University
college – COGS
contact – (other methods)
    social networks
    tech – Project/Games · Graphics Tech · Artificial Intelligence · World Records/Number Theory
personal – Home · Resume · Transcripts · Contact
twin – Matthew Doucette of Xona Games
old – Petzold's Programming Windows 5th ed Errata · Domain Hacks · Wallpapers
blog – The First Pixel



Artificial Intelligence

Back to Main Resume Page

Name Description Time Commenced Computer
1. Pangki God
2. Maim Chess
3. Triple Jump
4. Tic-Tac-Toe
Retrograde Analysis Game Solver
Chess Engine
Checkers (Draughts) Engine
Tic-Tac-Toe Playing Program
November 18, 2001
January 28, 1998
October 16, 1997
June 11, 1993
Athlon 750
486/66
486/66
286/8

Windows program PANGKI GOD

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, and 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 is played on a 4x4 board. The starting position is shown below (taken from a screen shot of Top 50 Blazing Windows 95/98 Games):

Pangki Starting Position
Source: thecodezone.com
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 opponent pieces).

Pangki God is a very basic retrograde analysis program that was programmed in a single day. It has served its purpose to solve the game of Pangki, and no more time has been placed into it to improve its efficiency. It is a Windows Console program that does not have any fancy graphics for the user interface. Again, it was not meant to be a program to play the game of Pangki - but just to solve it.

The program looks at the game based on the fact that each square can have three possibilities: 1. contain a white piece, 2. contain a black piece, or 3. be empty. Because there are 16 squares on the board, we can index all possible positions (including numerous illegal positions) by enumerating all possibilities of each of the 16 squares, resulting in 316 (43,046,721) different positions. Although this includes positions that are illegal, this number is a definite maximum limit for the number of legal positions in the game. The program makes an array of this size, and stores one byte per element - which stores the number of moves to lose/win (or a draw score) for player 1. It does not store the result for player 2 to move. If we wish to acquire this score, we can simply invert this position (swap all pieces for an opponent's piece) and solve it for player 1. This is only one of the numerous ways symmetry can reduce the size of the database, and speed up the solving process (however, it is the only one Pangki God uses). Each position's index into this array can be computed by creating a base-3 16-digit number from the 16 squares in the board, assuming each of the squares can contain only 0, 1, or 2.

Because of the symmetry of the starting position, there are actually only two possible first moves. One of them allows the opponent to immediately win a piece. I hope this does not ruin it for anyone, but Pangki God has solved this position as a Win in 15 for the opponent. The other move, which does not allow the opponent an immediate capture, is solved as a draw. Since there are no winning moves you can play for the first move, and there is a drawing move, the game of Pangki is solved as a draw.

I have analyzed all of the positions (again, including numerous illegal positions) from this program, and have found the following:

Total Positions:43,046,721100.0%
Total Wins:22,332,00751.9%
Total Loses:17,838,46241.4%
Total Draws:2,876,2526.7%
All positions, including illegal.

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

Total Positions:20,746,908100.0%
Total Wins:11,065,58353.3%
Total Loses:7,440,54135.9%
Total Draws:2,240,78410.8%
Only legal positions, except game-over positions.

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

I found out about the game of Pangki while on a friend's computer who had a copy of Top 50 Blazing Windows 95/98 Games. It is installed under the name of Solid Gold Games by Cosmi Software. It includes a playable version of Pangki. The author of this product, John Hattan, claims he found out about the game from a giant collection of obscure books of game rules from other countries. He recalls it being a popular game for kids from Southeast Asia.

If anyone has a copy of the Solid Gold Games version of Pangki, and cannot beat the computer, I have played Pangki God against it in all difficulty levels, and the Solid Gold Games version responds with the same move for every optimal move that Pangki God plays for each level. Therefore, the same sequence of optimal moves produces the same win regardless of the difficulty setting. I should note that the Solid Gold Games version does not play the same move for every board position in all three difficulty levels. The solution for any difficulty level are the following moves (assuming chess-like position index, where A1 is the lower-left square, and D4 is the upper-right square):

  1. A2-B2
  2. A1-A2
  3. C1-C2
  4. C2-C3
  5. C3-C4
  6. B2-B3
  7. B1-C1
  8. C1-C2
  9. D2-D3
  10. D1-C1
  11. C1-B1
Note that the best line of play renders the opponent's pieces immobile for the win.

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

MS-DOS program MAIM CHESS v0.31

Maim Chess was a 3rd year Software Engineering (COMP 3653) 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.

Despite an obvious weakness in search depth due to the lack of transpositional tables (which could not be added due to time constraints), Maim Chess still plays at an estimated rating of about 2000 at 3 minutes / move (average time per move in tournament play) on a 200 MHz system. Playing at the standard 10 seconds / move, this rating would be approximately 150 points lower, given only 1/18th the amount of thinking time (given twice the thinking time, a chess engine plays with a rating of approximately 50 to 70 ELO points higher against other computers, assuming optimizations such as transpositional tables exist, which Maim Chess does not have). This is good enough to demolish any beginner. To beat it, you will need to have a good understanding of positional play (probably better than the knowledge programmed into it), as the program is very unforgiving in tactical play. Given the fact that I understand all knowledge programmed into the game, since I have programmed everything I know about chess into it, the program plays at a disadvantage with me as I can often predict its moves.

Screen Shots:
Maim Chess Maim Chess Maim Chess

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 by Eric Bentzen.


(If a chess board does not appear above, you do not have Java on your machine. Please download it from http://java.sun.com/.)
Credits: MyChessViewer 2.2 Java PGN viewer: Michael Keating
Chess Alpha font / piece set: Eric Bentzen
Rendering of font / piece set for applet: Jason Doucette

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

MS-DOS program TRIPLE JUMP v0.30

Triple Jump is a checkers (draughts) playing program. It was a project created during my 3rd year Artificial Intelligence course (COMP 3613) 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.

The name Triple Jump was chosen after the program was tested for the first time. This consisted of about 10 games against people on my floor. These games were played before any positional evaluation was programmed. The program was playing purely on tactics and no clue of where to place its checkers to higher its chances of winning - it was moving blindly. Only when human error introduced positions where it could benefit from tactical play within the scope of its search could it play anything meaningful. Needless to say, the program made short work of these opponents achieving a triple jump in every game, and finishing them off before even reaching the end game. It is very good at finding shots - where you give up pieces, but force a position to occur where you can gain back what you lost plus more. Once this happens, you will be down at least a piece, and should ultimately lose the game (with perfect play).

The program's main weakness is from lack of transpositional tables (repetition of a position in the search tree), and I will rewrite the program from scratch once I have time to implement this. The program suffers enormously from this for several different reasons. Notably, without these tables:

  • Triple Jump does not realize a repetition of position is a draw. Although there is no rule in checkers (unlike chess) that states a repeated position x number of times is a draw (3 for chess), the computer should understand that if the game position repeats, nothing is being accomplished for either side, and is thus a draw. There is no purpose to reevaluate such positions over and over again, especially within the same search tree, such as where both players just keep moving a king back and forth.

  • Triple Jump does not realize that a potential outcome of a position it is searching may have already been analyzed through a different sequence of moves. For example, move a checker to the left, then to the right. Now reset the board, and move that checker to the right first, and then to the left. You have arrived at the same position. Without these tables, Triple Jump will analyze this same position twice. This will happen at every level of the search causing re-searches of the same position numerous times. This is a consequence of the above point, but you should note that these identical board positions can happen during 'normal moves' of the game, not just 'stupid' moves like moving a king back and forth.

  • Another consequence of the above point is during end game play. For example, in a 2 King vs. 1 King ending, which is an easy win, Triple Jump requires at least a 15-ply search to solve this - and that's when the 2 Kings already have the 1 King trapped in the double corner. 15-ply is far out of reach for Triple Jump - and therefore you can easily draw against it if you are down 1 King to 2. However, with these tables, every possible position of a 2 King vs. 1 King ending (a little over 200,000 positions) could be evaluated for a win, loss or draw in under 2 seconds (remember that with the tables, no position needs to be evaluated twice), stored in the table, and properly retrieved to allow Triple Jump to solve the win, regardless of piece placement.

  • Triple Jump has no idea which moves were evaluated to be the best moves at a shallow search depth, so that they can be research first for the next deeper search, and thus help the program to disregard the bad moves more quickly. Therefore it will research all the moves at the larger depth by blindly searching whichever moves it finds first. Why does this matter? With these tables, Triple Jump could search the principle variation (the best line of play) first, and using the Alpha-Beta Heuristic (which it has been programmed with), cut off more sections of the search tree. These cut-offs, if performed optimally (which never happens, but can be approached), can reduce the number of nodes (positions) searched by the square root of the original number. That means if it took 1,000,000 positions without it, it would only take 1,000 with it running optimally. This means instead of my program searching only to 7 - 8 ply in a 1 second / move game, it would search exactly twice as far, from 14 - 16 ply, given the same amount of time!

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

    Screen Shots of Amazing Wins:
    Human vs. Triple Jump - Craziest win I've seen in a real game! - White to win in 8 Human vs. Triple Jump - White to win in 6, sets up wicked triple jump Position by D.Oldbury - Amazing! - White to win in 9 Matthew Doucette vs. Playsite Player - Red to win in 8 Human vs. Triple Jump - White to win in 9, Red still has 9 pieces on the board! Triple Jump vs. Human - sets a trap, if White falls into it, Red wins in 5 Position by J.Doucette - White to win in 9 The Famous Hundred Years Problem (197 Years Problem)

    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 first picture above, Triple Jump plays the most amazing win I have ever seen against an expert human player. Although Triple Jump is up by 2 pieces, and is going to win easily, it announces a White to Win in 8 moves in under a second in the position seen. Can you see the forced win? I could not see it until the very end of it's 8 move winning strategy. White sacrifices 6 pieces to force Red into a loss. The winning line of play is in the following table:

    Triple Jump's Craziest Win in a real game
    White (Grey)
    Black (Red)
    21-17, White to Win in 8, sacrifices a piece
    3-8, sacrifices a second piece
    18-15, sacrifices a third piece
    23x14x7, double jump to sacrifice a fourth piece
    19-15, sacrifices a fifth piece
    27-24, sacrifices a sixth piece!
    32x23x14x5, triple jump!
    29x22, jumps last piece, White Wins
    14x21, forced jump
    4x11, forced jump
    11x18, forced jump
    2x11, forced jump
    11x18, forced jump
    20x27, forced jump
    21-25, only move
     

    In the third picture above, Triple Jump solves an amazing position composed by D. Oldbury 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!

    Derek Oldbury's Amazing Example Position
    White (Grey)
    Black (Red)
    27-24, White to win in 8 moves
    14-9
    15-11
    11-7
    18-4-2, double jump
    23-14
    19-16
    2-6
    6-15-24-31-22-13, White wins with a quintuple jump!
    20-27
    7-14
    1-10
    13-6
    15-18
    10-17
    12-19, or 3-10
    3-10, or 12-19
     

    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 kids game.

    I have a new found respect for checkers, now that I have played my computer program. The game is best described in this quote, from Marion Tinsley: "Playing chess is like looking out over a limitless ocean; playing checkers is like looking into a bottomless well." The quote is fairly accurate, as anyone can see that an ocean is limitless, however, it takes a greater amount of inspection to notice that a well is bottomless. Marion Tinsley was the World Checkers Champion for 45 years, losing only 5 games, of the thousands that he played, to only 3 individuals. This near perfection has been unmatched by any individual, in any other sport, ever. As quoted from the American Chess Journal, "To get an idea of the embarrassingly wide margin by which Tinsley surpasses his nearest competition, consider his defense of the world title in 1989 against the challenger Paul Davis. Tinsley drew 23 games, won 9, and lost 0."

    Download: Triple Jump v0.30 (212KB)

    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.

    QuickBASIC program TIC-TAC-TOE

    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.

     
    72,410 visitors since May 12th, 1999
    2,404,710 total page views since May 13th, 1999
    Jason Allen Doucette | Xona Games | The First Pixel