AI Factory Publications - A list of academic publications, lectures, keynotes and international events created or contributed to by AI Factory Ltd staff on AI.

Many classical games are best solved using the standard algorithm "Minimax", with the "Alpha-beta" algorithm. This solves problems by exploring a tree of possible move sequences, working out the best sequence the player can force, assuming perfect play. There have been thousands of articles and enhancements published for this basic technique. Our in-house generic implementation is designed to allow the search process to be sub-divided to a node-at-a-time analysis, allowing the UI to repeatedly call the search until complete, while still performing UI tasks. This is ideal for small devices that do not support multi-threading.

Our implementation is also enhanced to support advanced search mechanisms as yet not in the public domain. These allow minimax to search with very high efficiency (It is these techniques that allowed our Shogi program Shotest to so rapidly advance in the World Championship).

The search mechanism based on Minimax assumes perfect information. Many games cannot make this assumption, e.g. card games, where the user cannot see the opponent's hand. In this situation it iis not possible to do a simple minimax evaluation. The alternative is to use possible projections of what the hidden information is, and then do a minimax search on that. This can be repeated and then the most successful move strategy found for the range of alternative values of the hidden information. This is called "Monte-Carlo" searching, and is effective in games such as Bridge and Poker.

This uses analysis of opponent play to infer what cards/pieces they have and gradually build up a model of what they have (the hidden information). This is a pre-requisite for Monte-Carlo above, but can be used for a simple linear evaluation that weights plays based on the probability of what value the hidden information has. This has the advantage of being very fast, and works well for games such as Dominoes and card games such as Hearts and Spades.

This can take many forms, but relies on generating a range of possible plays and applying a linear evaluation to these. If the evaluation is good, then this can yield intelligent play. In the example to the left, from 3D Pool, maps are created after projecting a shot to determine the influence that the cue ball will have in the follow-on shot. This kind of evaluation can yield quite subtle and complex play.

This is a very strong area at AI Factory. Computer opponents often suffer from bland or predictable behaviour. For the former of these problems, AI Factory has a generic module providing meaningful characterisation that can be plugged into many games. This has been tested in 10 games to date, and (for example) provides the range of 80+ characters in 3D Pool. These characters are tuned and tested against each other in the AI Work Bench to provide opponents with genuinely interesting characteristics.

Player predictability is a different problem, but has been tested in one game that has successfully demonstrated that it can quickly learn against human opposition, and modify and greatly improve its play. The game tested is Gobang (aka Pente), which was able to learn faster than the player testing it, and eventually became almost unbeatable. These techniques have not been widely tested yet, but will certainly be developed and featured in our new engines to come.