Java-Gaming.org Hi !
Featured games (91)
games approved by the League of Dukes
Games in Showcase (804)
Games in Android Showcase (239)
games submitted by our members
Games in WIP (868)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Hnefatafl  (Read 39555 times)
0 Members and 1 Guest are viewing this topic.
Offline ags1

JGO Kernel


Medals: 367
Projects: 7


Make code not war!


« Posted 2016-04-12 19:10:15 »

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...

Offline Drenius
« Reply #1 - Posted 2016-04-12 19:38:02 »

Your description sounds like this:


Interesting. When I hear people say "viking chess" they (for some reason) usually refer to this...:
Offline ags1

JGO Kernel


Medals: 367
Projects: 7


Make code not war!


« Reply #2 - Posted 2016-04-12 19:40:55 »

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

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Drenius
« Reply #3 - Posted 2016-04-12 19:45:27 »

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.  Smiley
Offline Gornova
« Reply #4 - Posted 2016-04-13 14:03:44 »

interesting game, thanks!

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


Blog | Last game Number+
Offline Drenius
« Reply #5 - Posted 2016-04-13 14:50:23 »

We would at first probably need a slightly more specified ruleset...
Offline ags1

JGO Kernel


Medals: 367
Projects: 7


Make code not war!


« Reply #6 - Posted 2016-04-13 15:59:49 »

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...

Offline Drenius
« Reply #7 - Posted 2016-04-13 16:20:42 »

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...  Smiley
Offline ags1

JGO Kernel


Medals: 367
Projects: 7


Make code not war!


« Reply #8 - Posted 2016-04-13 19:00:48 »

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.

Offline delt0r

JGO Wizard


Medals: 145
Exp: 18 years


Computers can do that?


« Reply #9 - Posted 2016-04-13 23:08:46 »

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.

I have no special talents. I am only passionately curious.--Albert Einstein
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline ags1

JGO Kernel


Medals: 367
Projects: 7


Make code not war!


« Reply #10 - Posted 2016-04-15 10:43:28 »

Playing with this in my lunch breaks.

I started with generating a coverage map:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
. 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:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
    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.

Offline ddyer
« Reply #11 - Posted 2016-04-16 18:06:02 »

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!)
Offline ags1

JGO Kernel


Medals: 367
Projects: 7


Make code not war!


« Reply #12 - Posted 2016-04-16 18:47:01 »

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 Smiley

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.

Offline ags1

JGO Kernel


Medals: 367
Projects: 7


Make code not war!


« Reply #13 - Posted 2016-04-20 11:23:57 »

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

Offline Fishbreath
« Reply #14 - Posted 2016-04-21 02:48:37 »

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.
Offline jonjava
« Reply #15 - Posted 2016-04-21 07:40:13 »

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.


Offline ags1

JGO Kernel


Medals: 367
Projects: 7


Make code not war!


« Reply #16 - Posted 2016-04-21 10:52:26 »

I completed work on the first version of the AI Smiley

1  
2  
3  
4  
5  
    public interface AI {
        default String recommendMove(char[] board, char[] canMove) {
            return "resign";
        }
    }

Offline Fishbreath
« Reply #17 - Posted 2016-04-21 17:03:09 »

ags1, that's about as good as mine—mine just takes a lot longer to get to the point where it inevitably loses. Tongue
Offline ags1

JGO Kernel


Medals: 367
Projects: 7


Make code not war!


« Reply #18 - Posted 2016-04-21 17:31:26 »

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

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
  | 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):

Offline ags1

JGO Kernel


Medals: 367
Projects: 7


Make code not war!


« Reply #19 - Posted 2016-04-23 15:35:02 »

Re Thud!

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.

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.

Offline ddyer
« Reply #20 - Posted 2016-04-26 00:22:34 »

different from traditional =  modernized .  It scans for me.
Offline ags1

JGO Kernel


Medals: 367
Projects: 7


Make code not war!


« Reply #21 - Posted 2016-04-26 06:58:58 »

I disagree, "modernized" carries with it the sense that whatever it replaced was outdated and that's simply not possible in an abstract game.

Offline ags1

JGO Kernel


Medals: 367
Projects: 7


Make code not war!


« Reply #22 - Posted 2016-04-26 10:09:44 »

I'm at the point at which I can start teaching the AI to play well. As I don't know how best to prune the tree, I think I will use genetic algorithms to discover a pruning function.

I downloaded some Tablut games for Android, and I think I can do better. Anyways, I will definitely enter Fishbreath's competition.

Offline Fishbreath
« Reply #23 - Posted 2016-04-26 14:09:21 »

Delighted to have you! I look forward to seeing your entry.
Offline ags1

JGO Kernel


Medals: 367
Projects: 7


Make code not war!


« Reply #24 - Posted 2016-04-26 16:27:05 »

Fishbreath, how do I integrate with OpenTafl? I don't see instructions on your site. I'd like to see a minimal AI Java implementation to bootstrap my effort.

Also, what resources is OpenTafl providing me - can it give me board state and available moves info, or do I have figure out this in my own AI (so every AI might have different ideas about what a legal move is).

Also, it might be worthwhile to post your competition in the competitions board on JGO, rather than burying mention of it in my thread

Offline Fishbreath
« Reply #25 - Posted 2016-04-26 17:44:51 »

Here's a link to the engine protocol. You can get board state (and OpenTafl sends external engines a position record when the board state changes), but you'll need your own move generator.

OpenTafl communicates in a specific human-readable notation. OpenTafl's code for generating and parsing OpenTafl notation lives in this package, and is Apache-licensed, so you can crib from it directly.

This is the source file where the engine client implementation lives, and should get you started.

Thanks for the tip about the contests page—I didn't realize it was for community-run contests, too. I'll post over there.
Offline ags1

JGO Kernel


Medals: 367
Projects: 7


Make code not war!


« Reply #26 - Posted 2016-05-04 21:44:05 »

Well, my dwarves and elves are tinkering away on my hnefatafl automaton, and we have a (1) fast AI that prunes but does not do playouts and (2) an MCTS AI. The MCTS AI uses the fast AI for the playouts. I have been seeing how increasing the number of playouts improves the results for the MCTS AI, and I see a clear progression. Here the MCTS is playing defenders and the fast AI is attacking. In each iteration I double the number of playouts per position.

dwins = number of games won by defender : average turns to win
awins = number of games won by attacker : average turns to win
draws = games that went over 250 turns without a winner


2 playouts for defender: dwins=10:100, awins=6:107, draws=4
4 playouts for defender: dwins=15:66, awins=3:103, draws=2
8 playouts for defender: dwins=19:60, awins=1:87, draws=0
16 playouts for defender: dwins=19:40, awins=1:39, draws=0
32 playouts for defender: dwins=18:31, awins=0:0, draws=2


EDIT: I did the reverse case of playing attackers, which is a harder problem to compute:


2 playouts for attacker: dwins=5:524, awins=12:150, draws=23, time=1192668
4 playouts for attacker: dwins=9:1100, awins=18:125, draws=13, time=1877313
8 playouts for attacker: dwins=0:0, awins=37:111, draws=3, time=2911840
16 playouts for attacker: dwins=0:0, awins=40:80, draws=0, time=4858704
32 playouts for attacker: dwins=0:0, awins=40:67, draws=0, time=8562867
64 playouts for attacker: dwins=0:0, awins=40:62, draws=0, time=17018320


It seems like attackers hit a wall....


Pages: [1]
  ignore  |  Print  
 
 

 
Riven (581 views)
2019-09-04 15:33:17

hadezbladez (5510 views)
2018-11-16 13:46:03

hadezbladez (2402 views)
2018-11-16 13:41:33

hadezbladez (5772 views)
2018-11-16 13:35:35

hadezbladez (1223 views)
2018-11-16 13:32:03

EgonOlsen (4661 views)
2018-06-10 19:43:48

EgonOlsen (5683 views)
2018-06-10 19:43:44

EgonOlsen (3198 views)
2018-06-10 19:43:20

DesertCoockie (4095 views)
2018-05-13 18:23:11

nelsongames (5115 views)
2018-04-24 18:15:36
A NON-ideal modular configuration for Eclipse with JavaFX
by philfrei
2019-12-19 19:35:12

Java Gaming Resources
by philfrei
2019-05-14 16:15:13

Deployment and Packaging
by philfrei
2019-05-08 15:15:36

Deployment and Packaging
by philfrei
2019-05-08 15:13:34

Deployment and Packaging
by philfrei
2019-02-17 20:25:53

Deployment and Packaging
by mudlee
2018-08-22 18:09:50

Java Gaming Resources
by gouessej
2018-08-22 08:19:41

Deployment and Packaging
by gouessej
2018-08-22 08:04:08
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!