Using the Pentago AI Player Testbench I'm trying out two different approaches for players. The first is based on pattern matching and the second is using a game tree which is pruned by using influence mapping.
The pattern based player is quite limited since it must be instructed by example. It can only "react" to a certain game state by trying to match either the whole board or a square against a pattern. For example the square-pattern
* * *
1 1 0
* * *
finds all vertical and horizontal two-in-rows by player 1. To find all two-in-rows by player 1 you also have to test for:
1 * *
* 1 *
* * 0
The upside to this is that you know exactly where to place your marble if a pattern is matched. The downside is that you have to generate a lot of patterns to test for and you also have to figure out in which order the patterns should be applied.
The influence mapping player is both better and is a lot less code but instead it's a lot more complex. What happens is that for each turn a game tree is calculated using an influence map. The influence map is basically a 6x6 matrix holding a score for each position. The higher the score the better it is to place the marble there. The map takes advantage of the fact that there are only 32 ways to position five marbles in a row. The score depends on how many of those are still "possible" and how many that "this" particular position is included in. Only the highest ranking position is added to the game tree and calulated further (the influence map is used to calculate what move the other player does as well). Once the maximum depth (or game over) is reached the game state is stored in the leaf node as -1 (game is not over) , 0 (tie), 1 (player 1 wins) or 2 (player 2 wins). Selecting which move to make is simply a matter of selecting which leaf node works out the best for me.