Swarm intelligence

Real ant colonies appear to be very intelligent in some situations. For instance, every ant seems to know the shortest way to the food source. Yet this intelligence rises from very simple interaction among individuals (following the trail left by others). Swarm intelligence[4] has been applied in computer science to problems like rerouting traffic in a busy telecom network. The idea is that simple problem solvers are used in swarms and parts of those answers that happen to be successful, are reused and combined by others later on. Ants are typically stochastic, so that they cover the search space better.

In Go81, the ants are used to play the game twice to the end, once starting as black and once as white (see Figure 3). The game can be played further than people usually do, really capturing all the dead stones and filling own areas. This way, it is trivial to determine which areas belong to black and which to white. The areas, where these two possible futures differ, are the interesting ones. It is not yet determined, to whom they belong to. The blocks that might surround others or be surrounded and the border between black and white territories are the places where the focus of the game is. The swarm of two ant battles is used thus to rule out uninteresting areas. Also, it seems that large continuous neutral territories are more interesting than small ones.

**Figure 3:** Left: The search tree of Go81. The swarm consists of only two ants. Right: The vital point for white. If white is the first to play there, he forms three eyes (the empty points around the vital point, and the stones survive. If black plays there first, he will capture the whole corner.
$\begin{figure}\begin{center} \epsfig{file=tree.eps,width=0.2\textwidth} \hspace... ...extwidth} \epsfig{file=vital.eps,width=0.5\textwidth} \end{center} \end{figure}$

The possible futures are used also to find vital points. If there is a group of stones in the end that barely survived (it has no more than three eyes), the points that form its eyes are marked important. When a particular point is important to many eyes at once, it is called vital. The evaluation of playing in the vital point is increased for both players. Figure 3 shows an example of a vital point.

To conclude the evaluation of moves in Go81, the different terms are listed here: Evaluation = randomness + 3-by-3 shape + liberty changes + area interest + vitality. Note that moves are evaluated as opposed to evaluating the position that the move leads to. Only the liberty change term is defined such that it could be seen as the difference of the evaluations of the game state before and after the move.