Teaching a Computer to Play Hnefatafl

Thursday, 11th September 2014

Today's blog post is mainly of interest to people who want to write a computer program to play hnefatafl. So please take this as a warning of technical content ahead!

Computer opponents in hnefatafl, and similar games, work by simulating a move and looking at the resulting board position. The computer opponent will, given a position, examine each possible move and the human player's possible responses. If time allows, it will then look at the possible following moves and their responses. This is known as look-ahead, and is common to all board games like hnefatafl, where each player alternately moves any one piece of his or her choice.

The examination will look not at the moves themselves, but the resulting position of the board after a move is made, to see how it benefits the computer player's chances of victory, if at all. This part of the process is known as evaluation, and unlike the look-ahead part of a computer opponent, will vary in nature from one game to another. It is the evaluation part of the process that the rest of this blog post will deal with.

An evaluation function generally reduces the intricacies of a board position down to a single number, a score, which allows two or more board positions to be compared to see which is the best. The better the score, the better a position is deemed to be. Things advantageous to the computer player are added to the score, things advantageous to the human opponent are subtracted.

The first thing an evaluation function needs to check for is actual victory or defeat. These should have the highest and lowest possible scores, so that a move which leads to a victorious position is preferred to one that makes any other kind of gain - and a move leading to defeat would always be avoided if possible.

Other things that an evaluation function should check for can include material, with an increase in score for each piece that the computer player has, and a decrease for each piece that the human opponent retains. Manoeuvrability could also be a factor: how many choices do the pieces have? And in many games, positions of individual pieces will have an effect on the evaluation: hnefatafl is a great example, in which a higher score might be given to the defending player when the king is closer to his exit.

The evaluation I used in my Java applet on this site checks a couple of these things: material, and the proximity of the king to the edge or corner of the board. There is something else I introduced, too: control of ranks and files. A player has "control" of a row if they own the outermost pieces (or the only piece) on that row. This encourages the computer attacker to try and surround the defending human, and encourages a computer defender to prevent the attacking human from doing likewise by pushing defenders to outlying positions.

There are some things in which my hnefatafl applet's evaluation function are weak. Although the king's position is evaluated, the positions of other pieces are not. This makes the computer particularly weak in games where pieces are restricted in movement; in such a game, it is not always possible to move a piece directly to the square where it is most beneficial. The intervening positions, where a piece moves towards its destination, are not always beneficial in and of themselves. The computer player on this site relies very much on look-ahead to determine what short-range moves are the best, and this can take a very long time.

Another weakness of my current evaluation function is that it cannot spot a completed blockade - and this is why you can't play Copenhagen hnefatafl against the computer here. Introduction of a speedy check for a blockade would not only allow me to add Copenhagen hnefatafl to the applet, but it would also probably be of great use in refining evaluation of positions in other variants too.

There are probably other things I've not thought of here: after all, my hnefatafl applet is quite weak on comparison to others. So in summary, an evaluation function for hnefatafl should check for victory and defeat, material, freedom of movement, control of ranks and files, completeness of blockade - and the things I've not yet thought of!