Expert Systems and Logic Games
By ai-depot | June 30, 2002
Connect Four Winning Strategy
In Theory
An expert system for a game can be designed in a couple simple steps:
- Modelling the Game - this involves understanding the states and actions for each step of the simulation. The AI expert system will need to perform actions based on such states, so it’s a good idea to have them well identified.
- Understanding Advanced Strategies - obviously, if you stick to the intuitions you had when you first played the game, any expert system based on them will not perform well! Your job is to understand what makes a winning player, and model those moves mathematically.
- Selecting the Tactics - In many cases, there is more than one possibility at each stage of the game. It’s also your task to decide how to select a specific strategy. This can be done with more expert rules, or a more standard search.
Lets see how Connect Four can be tackled in this fashion.
In Practice
Understanding the Game
Connect four is a turn-based logic game. The concept is very simple� each player is given a set of tokens, which he inserts into the top of a 7×6 grid. Due to the way the game is designed, can freely drop down due to gravity. The aim is to have four tokens lined up, which secures a win. In some cases, neither of the players lines up four tokens, and the game is drawn.
You can experiment online at JGames for example.
Becoming an Expert
Connect 4 is very popular, and pretty much anyone has played at least once in their lives. Some of the more elaborate tactics of Connect Four, however, are not always grasped. Some details are neglected, or intuitively discarded for the sake of simplicity.
On the other hand, some experts have learnt about these strategies, and can take advantage of them. There’s a nice page which describes all this in gory details entitled Expert Play in Connect-Four. This will take you a step further towards being an expert: understanding what to do and when to do it. Then, all you need is to apply your knowledge as a computer program, and you’ll get an expert system!
VICTOR
You may be surprised to hear that Connect 4 has been solved this way! This is what Victor Allis did in his masters thesis (you can download his dissertation right here). Essentially, he has identified a set of 9 rules that need to be followed. Then, a decision is made which rule to apply to which situations, which allows the while player to always win. This is done by a simple search, which is nowhere near as complex as standard minimax searches typically used in logic games. Indeed, the size of the search space is much smaller due to the mapping onto the 9 basic set of rules. The expertise of the author came into play to reduce the cost of the search, which thereby manages to play the game in real-time.
Tags: none
Category: essay |
