Movatterモバイル変換

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

ANGKI OD

Pangki God is a retrograde analysis endgame database solver.It was created as a personal experiment to solve a simple perfect informationtwo player game (i.e. a game in which no luck is involved, and both opponentsknow 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,and3. I had a computer opponent to test the results against.Normally, retrograde analysis is used to solve as much of a game's endgame aspossible, but because Pangki is so simple, its entire game tree can fitinto 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 ofTop 50 Blazing Windows 95/98 Games):

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 singleopponent's piece all in the same row or column. This canresult in two captures in the same move. The fourthsquare of this row or columnmust be empty, which impliesthat you cannot capture a piece with three pieces in line witha single opponent piece, and you cannot capture either opponentpiece by sandwiching two of your pieces in-between two opponentpieces. The game ends when a player only has one piece remaining(as you cannot capture any further opponent pieces with onlya single piece), or when you have no legal moves(which is sometimes much quicker to do on a crowded boardwith only 4 empty squares, rather than tactically capture fiveopponent pieces).

Pangki God is a very basic retrograde analysis programthat was programmed in a single day. It has served its purposeto solve the game of Pangki, and no more time has been placed intoit to improve its efficiency.It is a Windows Console program that does not have any fancygraphics for the user interface. Again, it was not meant tobe 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 havethree 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 possiblepositions (including numerous illegal positions) byenumerating all possibilities of each of the 16 squares,resulting in 3¹⁶ (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, andstores 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 bycreating 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 actuallyonly two possible first moves. One of them allows the opponent toimmediately win a piece. I hope this does not ruin it for anyone,butPangki 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 forthe first move, and there is a drawing move, the game ofPangki issolved 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,721	100.0%
Total Wins:	22,332,007	51.9%
Total Loses:	17,838,462	41.4%
Total Draws:	2,876,252	6.7%

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 allpositions in which the game is already over),I have found the following (note that there may be positionswhich have the proper number of pieces, but may be impossible to reach):

Total Positions:	20,746,908	100.0%
Total Wins:	11,065,583	53.3%
Total Loses:	7,440,541	35.9%
Total Draws:	2,240,784	10.8%

These numbers are encouraging for the enjoyment of the game, since so manyof 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,680possible 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 computerwho had a copy ofTop 50 Blazing Windows 95/98 Games.It is installed under the name ofSolid Gold GamesbyCosmi Software.It includes a playable version ofPangki.The author of this product,John Hattan,claims he found out about thegame 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 theSolid Gold Games version of Pangki,and cannot beat the computer, I have playedPangki Godagainst it in all difficulty levels, and theSolid Gold Games version respondswith the same move for every optimal move thatPangki God plays for each level.Therefore, the same sequence of optimal moves produces the same winregardless of the difficulty setting. I should notethat theSolid Gold Games version doesnot play the same moveforevery board position in all three difficulty levels. The solution forany 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):

A2-B2
A1-A2
C1-C2
C2-C3
C3-C4
B2-B3
B1-C1
C1-C2
D2-D3
D1-C1
C1-B1

Note that the best line of play renders the opponent's piecesimmobile 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."

AIM HESS

Maim Chess was a 3^rd year Software Engineering(COMP 3653)project atAcadia University.The purpose of the project was to use the software engineering approaches covered in classto 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 to8 weeks and30 man hours, which was met. This time frame includedthe original and revised proposal, the engineering, designing, implementationand the 2,000 word final report of the project.Maim Chess was chosen as the name of the project as an incentive to createthe strongest playing program possible within the time constraints.

Despite an obvious weakness in search depth due to the lack of transpositionaltables (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 beapproximately 150 points lower, given only 1/18^th the amount of thinking time(given twice the thinking time, a chess engine plays with a rating of approximately 50 to 70 ELO points higheragainst 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 willneed to have a good understanding of positional play (probably better than theknowledge programmed into it), as the program is veryunforgiving in tactical play. Given thefact that I understand all knowledge programmed into the game, since I have programmedeverything I know about chess into it, the program plays at a disadvantage with me asI can often predict its moves.

Screen Shots:

Download:Maim Chess v0.31 (135KB)

The program should run on a 386+ processor.

Here is a game I played againstMaim Chess set to think 10 seconds per moveon a Pentium III 550 MHz processor.Although I made a tactical error, whichMaim 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 computersto understand, even with deep analysis.Please view the game below using theMyChessViewer 2.2 Java PGN viewer,which I modified to use my own rendering(specifically for this applet)of the beautifulChess Alpha font / piece setbyEric Bentzen.

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

RIPLE UMP

Triple Jump is a checkers (draughts) playing program.It was a project created during my 3^rd year Artificial Intelligencecourse(COMP 3613)atAcadia University.The project was not required for the course,but the course raised my interest in ArtificiallyIntelligent programs. So, I decided to implement one on my own.The project was completed in 2 weeks.

The nameTriple Jump was chosen after the program was tested for the first time.This consisted of about 10 games against people on myfloor. These games were playedbefore any positional evaluation was programmed. The program was playing purely ontactics 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 benefitfrom 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 findingshots -where you give up pieces, but force a position to occur where youcan 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), andI 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 positionis a draw. Although there is no rule in checkers (unlike chess)that states a repeated positionx 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 toreevaluate such positions over and over again,especially within the same search tree, such as where both players just keepmoving a king back and forth.

Triple Jump does not realize that a potential outcome ofa position it is searching may have already been analyzed through a different sequenceof moves. For example, move a checker to the left, then to the right. Now reset the board,and move that checker to theright first, and then to the left. You have arrived at the same position.Without these tables,Triple Jump will analyze thissame position twice.This will happen at every level of the search causing re-searches of the same positionnumerous times.This is a consequence of the above point, but you should note that these identical board positionscan 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 a2 King vs. 1 King ending, which is an easy win,Triple Jump requires at least a 15-ply searchto 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 forTriple Jump - and therefore you can easily draw against it if youare down 1 King to 2. However, with these tables,every possible positionof a 2 King vs. 1 King ending (a little over 200,000 positions) could be evaluated for a win, loss or drawin under 2 seconds (remember that with the tables, no position needs to be evaluated twice),stored in the table, and properly retrieved to allowTriple Jump to solve the win, regardless ofpiece 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 researchfirst 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 Jumpcould search the principle variation (the best line of play) first, and using theAlpha-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 thenumber of nodes (positions) searched by the square root of the original number. Thatmeans 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 plyin a 1 second / move game, it would search exactlytwice as far, from 14 - 16 ply, given thesame amount of time!

It also suffers from the lack of an end game database, and therefore playsthe endgame poorly.Regardless, you have to be a very good checkers player to beatTriple Jump -you will only notice it's weak endgame playif 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 itquadruple jumped all of the opponent's remaining pieces.Obviously embarrassed, the opponent left without saying a word - I wouldexpect that this was probably the only game ever in which an experienced playersuffered a quadruple jump to lose the game.This is just an indication that you cannot start to play carelessly at any pointduring a game, or you will probably lose.

Screen Shots ofAmazing 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, orrendered 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 thefirst picture above,Triple Jump plays the most amazing win I have ever seen againstan expert human player. AlthoughTriple Jump is up by 2 pieces,and is going to win easily, it announces aWhite to Win in 8 movesin 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 sacrifices6 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 asixth 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 thethird picture above,Triple Jump solves an amazing position composed byD. 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 thesixth 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.Whitewill win one of the two checkers in it's next move.Why wouldTriple 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 youmust jump, ifyou can. This adds a lot of strategy to the game. It is, by no means, only akids 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, fromMarion 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 Tinsleywas the World Checkers Champion for45 years,losing only 5 games, ofthe 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 theAmerican Chess Journal,"To get an idea of the embarrassingly wide margin by which Tinsleysurpasses 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.

IC-AC-OE

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 everwritten in grade II, this was not a very challenging course, needless to say.The final project was a random question out of the finalchapter of the book. Since my question was very simple, I asked to program anartificially 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 programmedvia patterns in the board. There are 4 levels of difficulty, each level checks for morepatterns (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.

73,011visitors since May 12^th, 1999
2,413,367total page views since May 13^th, 1999

[8]ページ先頭