Summary:
At this point I have based my research on the book "Introduction to Computer Programming". I have
implemented a version of Matchsticks (as suggested in the book above) where the second player was an AI
player. As a result, after a short learning session AI player was extremely tough (probably unbeatable).
The game of Matchsticks starts out with 20 or so Matchstics lying on the desk. During his turn, a player can take one
two or free matches from the pile. The object of the game is to be the last person to take matches from that pile.
It is very neat how a computer first takes first steps like a baby (looses) but then starts crawling and walking
and then running wiping the opposition (me) out of existence on the battlefield.
The following was cut and pasted out of one of the test runs.
For anyone to play a better game of Matchsticks, one should base his moves on the outcomes of previous
games. Winning should reinforce tendencies and loosing should decrease the tendencies to move according
to strategies that brought the defeat. The exact same technique applies to the AI player. During it's learning
period and thereafter, computer keeps an important statistic of it's moves during the game. The statistics are
kept in an array of the size of the number of positions in the game. In the case of Matchsticks, for each
possible number of Matchsticks left (from 0 to the starting number of matches). As the game progresses,
computer keeps track of it's moves. When the game is over depending on the outcome, computer either adds
or subtracts one to the array (that keeps statistics) in the places that correspond to the moves taken. In the
next and later games computer bases it's moves on the values in that array.
Here is the values of the array after 21 matches (for match statistics look above).
15 -3 -3 -3 15 -2 -2 -2 12 -1 -1 -2 5 3 -1 -1 8 0 0 0
This means that when the computer starts out second, after it's move there should be left either 0, or 4 or 8
or 12 or 13 or 16 matches. For the correctness of this assumption look at the statistics above. That was the
devastating result of those games.
Such way for learning to play a game does not promise the best solution, but it always gives a very good one.
Click here to view the source code that had produced the Match Statistics and the array.
To check out the continuation of my AI project view the
design and implementation of the AI player for Checkers.
References:
My predecessor (in NEU CCS honor program) in the field of AI
Kaya Bekirogluhad build a fine introductory page to
AI
so if you have not checked that out already then I suggest you do so ASAP.
NOTE: This is Honor Program project of Mikhail Golitsine.
Last Modified: 1:16am 03/15/98
Match Statistics:
You won 9 games.
Computer won 15 games.
How an Artificial Intelligence Player Learns to Play Matchsticks.
Introduction to Computer Programming
Walter S. Brainerd, Charles H. Goldberg, Jonathan L. Gross.
Harper&Row, Publisherss, Inc., 10 East 53rd Street, New York, NY 10022