|
In this article I discuss some of the AI techniques employed by the Connect6 bots on this site. This article is the second in a series, the first was titled Othello Bots.
As I develop the bots for Vying Games, I have a few overriding goals: The bots should be fast and competitive, ideally playing at a variety of skill levels.
Balancing speed with quality play was the most difficult aspect of developing bots for Connect6.
Evaluation Functions
In Connect6, evaluating the quality of a position is relatively easy. The bots on this site all use slight variations of the same strategy. In brief, a list of all threats is made. Each threat is assigned a score and the sum represents the value of the position.
A threat, in Connect6, is a line of N stones that could, potentially, be turned into a 6-in-a-row. There are threats of differing severity -- for example, a 4-in-a-row is a fairly strong threat because it can be turned into a winning 6-in-a-row in one turn. We can further break down 4-in-a-row threats into two categories: open and closed. An open threat is one that requires two stones to block (one on each end of the line), and a closed threat only requires one stone to block. It should be obvious that open threats are more dangerous.
VegaBot, SiriusBot, and CapellaBot vary in how they score threats. VegaBot has strong negative weights for opposing threats (thus, leading to more defensive play), SiriusBot is relatively balanced, and CapellaBot gives less weight to opposing threats (thus, an emphasis on offensive play).
Forward Pruning
The games I've implemented so far have all been amenable to alpha-beta pruned, minimax search. Due to the high branching factor in Connect6, minimax search cannot be employed without some kind of forward pruning. The trick to finding decent play is more in developing the right pruning strategy than in developing the right evaluation function. A poor pruning strategy can completely negate a quality evaluation function.
Threats
The first pruning strategy I tried was to sort all threats by severity, keeping only moves that were a part of the most severe threats. If a threat is severe enough, like an open/closed four or five, I look only at that threat. This is still the strategy used by SiriusBot, though it leads to generally flawed play.
SiriusBot is prone to over-extending a line (creating an open / closed five, when it would be better to create an open / closed four, and use its second stone to create a new supporting line). Over the course of a game, this strategy severely impacts SiriusBot's chances of forcing an unblockable win. In fact, serendipity seems to be its winning strategy. SiriusBot wins most often through luck or an opponent's mistake.
Neighbors
One pruning strategy is to keep only moves that place a stone next to another stone (a neighbor). Neighbors grow quickly, so this strategy can only be employed with a very small look ahead. With my goal of returning a move in under one second, I can only look ahead one move with this strategy. In Connect6, despite the two stones per turn rule, each stone is considered a separate move. So, with a one move look ahead, there are severe horizon problems (eg, the bot can win in two stones, but due to the one move look ahead, cannot see the win, so instead chooses to block).
Despite the horizon problems, the neighbors pruning strategy worked surprisingly well at building up a good foundation of moves early in the game. This fact led me to believe that the evaluation function is fairly accurate. The irony is that the bots could often get into winning positions, but were unable to see that they were in winning positions. I can't express how frustrating it is to watch to bot ignore winning move after winning move, only to play into a draw or loss.
Threats Revised
Eventually, I returned to a threats based strategy. This time, though, I didn't sort threats by severity. Rather, I sample threats of varying severity. I found that keeping a couple moves from each of an open / closed five, open / closed four, open / closed three, and a couple randomly chosen neighbors, seemed to create a better set of moves.
The number of moves kept from each sampling category varies based on availability and urgency (if there are lots of open fours, none of the other categories are relevent).
This revised strategy is used by CapellaBot and has led to the strongest play of the bots I've developed so far.
Lessons Learned
It's easy to see why so little is thought of forward pruning. It's a difficult technique to get right. Even with a good evaluation function, poor pruning can lead to terrible play. Further, from a programming perspective, forward pruning feels like a kludge. There's a lot of natural overlap between the pruning function and the evaluation function.
When using forward pruning, it's important to have an actual reason for pruning or keeping a move. Arbitrary cuts don't work. Poorly thought out pruning strategies don't work. Ultimately, I had to spend a lot of time in trial-and-error mode before I found a strategy that was a noticeable improvement over earlier strategies. In some ways, more time and care should be spent on the pruning function than the evaluation function.
Also, I can't stress enough how important it is to have metrics when developing AI bots. You need to be constantly measuring one strategy against another. Whether it's a pruning function or an evaluation function, it's far too easy to get lost in "improvements" that don't actually improve play. Often in AI development good ideas fall victim to either emergent behavior, or the law of unintended consequences. Without metrics, it can take too long to realize that what seems like a good idea is flawed.
Further Reading
While writing this article, I really wanted to work in a link to Searches, tree pruning and tree ordering in Go (and, now I have). Go and Connect6 share many of the same properties (starting with the large branching factor). The aforementioned article is an excellent resource if you're interested in this area of AI.
|
