Hnefatafl

Game Mechanics Artificial Intelligence
#1

The vikings played a game called hnefatafl (king table) often mistranslated as chess. The rules are quite simple as far as they have been pieced together. The game is played on boards of varying sizes, 13x13 is the most common. The king starts on the central square, his throne. He is surrounded by his warriors. On the edges of the board are attackers outnumbering the defenders 2 to 1. All pieces move like chess castles except the king, who moves like a chess king (but not diagonally).

The defender wins if the king escapes to any corner.

The attacker wins if they surround the king.

You kill enemies by moving to opposite sides of an enemy piece. It is legal however to move into the gap between two enemy pieces.

https://historyundusted.wordpress.com/?s=Hnefatafl

How would you go about building an AI for this? MCTS looks easy but there are a go-like number of moves for each turn…

#2

Your description sounds like this:

Interesting. When I hear people say “viking chess” they (for some reason) usually refer to this…:

#3

Exactly like that. Can I copoy the first image to the top post?

#4

It is a random image i found on Google Images, also linked it from it’s original location.
Do whatever you think you want to do with it. :slight_smile:

#5

interesting game, thanks!

I think attacker and defenders have slightly different moves reading rules, for example defenders don’t have king :smiley: So at first sight I think this is an important thing to consider, because resulting AI could be… two AIs types?

#6

We would at first probably need a slightly more specified ruleset…

#7

Interesting thing is the rules need to be flexible. Players might agree to play a “shieldwall” rule, change which side goes first, change the movement of the king…

#8

Well, unless we clearly define how flexible this is allowed to be, we will barely be able to create a proper AI for it, unless counting a simulated human being… :slight_smile:

#9

This set of rules seem fairly well worked out:

http://aagenielsen.dk/copenhagen_rules.php

The number of possible victory conditions boggles the mind. The recommended board is 11x11, which makes it a bit easier on the AI.

Assuming an MCTS approach, the tree of moves can be pruned as follows:

The attackers favor moves to block the corners.
Moves adjacent to enemies are discouraged if enemies can immediately move to the opposite side. Otherwise moves adjacent to enemies are favored?
Moves that increase board coverage are favored, where board overage is the total number of possible moves available from the new position.
Moves that decrease enemy board coverage are favored.

But I think MCTS would have trouble seeing shieldwall and fort situations.

#10

This is much closer to chess as far as branching factor goes, and there are always a lot of “dumb” moves. Therefore pruning trees like used in chess would work well. However chess AI uses databases of opening moves. Since this game is not so popular you would find it hard to find such databases. Hence it would need to have some deep precomputed openings or something.

#11

Playing with this in my lunch breaks.

I started with generating a coverage map:


. x x . . . . . x x . 
x x x b b . b b x x x 
x x . b b b b b . x x 
. b b b b . b b b b . 
. b b b . . . b b b . 
. . b . . . . . b . . 
. b b b . . . b b b . 
. b b b b . b b b b . 
x x . b b b b b . x x 
x x x b b . b b x x x 
. x x . . . . . x x .

Defenders cover little o squares, attackers cover little x squares and both cover b squares.

Code:


    private static final int OFF_BOARD = -1;

    public interface Direction {
        int at(int square, int distance);
        Direction LEFT = KingsTable::left;
        Direction RIGHT = KingsTable::right;
        Direction UP = KingsTable::up;
        Direction DOWN = KingsTable::down;
        Direction[] DIRS = {LEFT, RIGHT, UP, DOWN};
    }


    private static char[] calculateCoverage() {
        char[] coverage = new char[ROWS * ROWS];
        Arrays.fill(coverage, '.');
        for (int i = 0; i < coverage.length; i++) {
            char mover = board[i];
            if (mover == 'X' || mover == 'O' || mover == 'H') {
                for (Direction dir : Direction.DIRS) {
                    for (int j = 1; j < ROWS; j++) {
                        int neighbor = dir.at(i, j);
                        if (neighbor != OFF_BOARD) {
                            if (board[neighbor] == '-') {
                                coverage[neighbor] = cover(mover, coverage[neighbor]);
                            } else if (mover == 'H' && (board[neighbor] == '#' || board[neighbor] == 'T')) {
                                coverage[neighbor] = cover(mover, coverage[neighbor]);
                            } else if (board[neighbor] == 'X' || board[neighbor] == 'O' || board[neighbor] == 'H') {
                                break;
                            }
                        } else { break; }
                    }

                }
            }
        }
        return coverage;
    }

Next up is a heat map suggesting favored squares based on my ignorant noob concept of the game.

#12

A standard alpha-beta AI works very well, counting the “wood” and a few simple
factors such as king safety and proximity to the goal. The asymmetric rules
has no effect at all on the AI - all it needs is a move generator.

You can play on against this simple AI on Boardspace.net, where the game is known as
Tablut (no one can pronounce or spell Hnedatafl!)

#13

That’s good info, thanks.I was aware of tablut, most reconstructions of hnefatafl rules are based on the presumed similarity to tablut. Let’s see how I do at building an hnefatafl AI.

@ddyer, I’m liking boardspace.net! http://boardspace.net/english/about_tablut.html

@Drenius, I looked up the other game you pointed out (Kubb) and it seems to have no genuine Viking connection. It’s not mentioned in the sagas for certain. As far as lawn games go, they seemed to do a lot of wrestling :slight_smile:

If I can get this tafl game working well I can add it into Vangard as a game in a game. The vikings prized playing well, but in particular admired quick play, so I could make the moves timed.

#14

Modified the coverage method given above to use method references. I updated the post.

#15

I hate to plug my own stuff with my first post here, but I’ve been doing hnefatafl AI research for some time now, and I’m thrilled to see other developers interested in it.

I’m the creator and current sole contributor to OpenTafl, a full-featured engine for tafl games written in Java, with support for external AIs and a very mediocre built-in AI, along with some handy ancillary features like annotated replays and a few options for timed games. My eventual goal is to make it as fully-featured as, say, Arena for chess, or the online-go.com Go engine.

In the next few months, I hope to expand to network play and improve the built-in AI. In an effort to encourage further development of AIs, I’m also running a tournament for AIs this December. If anyone here is interested in entering, I’d be delighted to have you.

#16

Kind of like Thud! although:

[quote]Thud! is similar to Hnefatafl but is not actually a member of the tafl family (See http://boardgamegeek.com/boardgamefamily/4049/tafl) because the manner of capture has been modernized and the game involves no king piece.
[/quote]
http://i.imgur.com/NiCpyif.jpg

#17

I completed work on the first version of the AI :slight_smile:


    public interface AI {
        default String recommendMove(char[] board, char[] canMove) {
            return "resign";
        }
    }
#18

ags1, that’s about as good as mine—mine just takes a lot longer to get to the point where it inevitably loses. :stuck_out_tongue:

#19

I’m a bit further on now, I have a basic AI that makes random legal moves.


  | a b c d e f g h i j k
--+----------------------
 1| # - - X X X - - - X # 
 2| - - - - - X X - - - - 
 3| - - - - - - - X - - - 
 4| - - O - X - O - - - - 
 5| X - - - O - - - O - X 
 6| X X - - O T O - - X X 
 7| - - - O O O O O - X - 
 8| X - - - - - - - - O X 
 9| X - - X X - - - - - H 
10| - - - - X - - - - - - 
11| # - X - - - X X - - # 

King home? false
King can reach corner? true
King can reach edge? true
Enter move (eg: e1-c1):
#20

Re Thud!

This statement has been bugging me for a week. Hnefatafl, tablut etc are abstract games. There is no possible meaning to the statement that Thud has “modernized” the manner of capture.