4

I'll try to do a Hnefatafl game with Pico-8.
This is not going to be easy ( because I'm not really good with code), but it's a nice challenge.

The game is one of pure strategy, played on a square board. A king and a small force of defenders occupy the centre of the board. A larger force of attackers, twice as numerous as the defenders, occupy positions around the edge of the board.

What I find interesting it's the asymmetry of this game, and the challenge to do the A.I. for it.

Any help, tips, are welcome , especially for the implementation of the A.I.

board

Why to play this game ?

P#14013 2015-09-11 11:46 ( Edited 2015-09-29 14:17)

I like the background you've made, no idea about the game, but it looks interesting =)

P#14015 2015-09-11 12:10 ( Edited 2015-09-11 16:10)

@Impox Take a look to "why to this game", It's the ancestor of Netrunner . My favorite board game!.
I need to figure out how to create the A.I., no idea how to do that with pico-8 and lua. An alpha beta should do the job, but not sure if it's possible :)

P#14017 2015-09-11 12:18 ( Edited 2015-09-11 16:18)
1. If next to defender piece, attack
2. If not, move to the closest one by one square
3. In case you can only move one piece per turn (haven't played it), for 2. use the closest one to any of defenders if attack is not possible.

And you got AI.

Anyway, looking forward it, especially if you include two player mode (one player is defender, other is attacker).

P#14018 2015-09-11 12:31 ( Edited 2015-09-11 16:31)

Simple AIs to win board games are all about creating board states for possible moves and quietly playing future moves up to a certain length of time, then evaluating those states for their benefit as a possible next move.

The AI will grind through all possible board states after one move, then run some check to see which of those states are more beneficial.

You could have control over how many future states are checked. The more, the longer the computer will make you wait, and the tougher an opponent it'll be.

You could do things like randomly drop a state from the table to simulate the opponent having a poor attention span or something.

I've done it for a connect 4 AI years and years ago. I won my grade 8 science fair with my QBasic AI!

P#14023 2015-09-11 15:34 ( Edited 2015-09-11 19:34)

Since arnaud_debock mentioned alpha-beta pruning, they probably understand the basic idea of a tree search AI for a game like this. The problem would be coming up with an appropriate evaluation function. For the defender, you might use something like the shortest path from the king to a goal space. I saw an interesting approach to the game of Hex that used resistor networks to estimate how close a player was to winning. Perhaps something like that would work here.

You might also want a heuristic to order the moves considered. I'm not good enough at the game to have a good guess what that would look like.

P#14024 2015-09-11 15:49 ( Edited 2015-09-11 19:49)

@Retsyn @eruonna If you can help me with some code example it can really help.
I understand the concept of alpha pruning, but don't know about resistor networks.
( I'll do some research).
I was actually surprise to don't find any A.I. Implememtation done with pico-8.
Does It's a memory problem?
I'm curious.

This game is close to chess, go and checkers.
But the fact It's assymetric, mean it probably need 2 different smart a.i.

@ darkhog thanks for your feedbacks

P#14025 2015-09-11 16:23 ( Edited 2015-09-11 20:23)

Graphics-wise, maybe you could make defenders being shields? It would look better IMO and would underscore their purpose better than just a palette swap.

P#14028 2015-09-11 18:18 ( Edited 2015-09-11 22:18)

@arnaud_debock: I've got a simple AI for picoracer, but that'd be quite a different thing to a strategy AI.

Making a strategy AI seems like a fun challenge, but likely to eat a lot of tokens.

P#14032 2015-09-11 22:34 ( Edited 2015-09-12 02:34)

I have to do some AI for my Hanafuda Koi-Koi game. The beginning for me is to map out the rules and goals (combinations of cards is wrote easy) and then figure out the areas where you can introduce automation and randomness (the AI should not be perfect! )

P#14039 2015-09-12 03:23 ( Edited 2015-09-12 07:23)

@impbox @matt I'll try to do the A.I. as simple as I can for the alpha version.
But First I need to finish this weekend the Pico-zine #2!

P#14041 2015-09-12 04:24 ( Edited 2015-09-12 08:24)

detail rulesI just find nice rules for this game :

P#14057 2015-09-12 13:15 ( Edited 2015-09-12 17:15)

This wiki page may also be helpful, describes a bunch of variants of the game.

Apparently the game is imbalanced, so some fudging of the rules will probably be necessary to make it fun. There's a reason this game died out and chess didn't.

P#14061 2015-09-12 14:32 ( Edited 2015-09-12 18:40)

@innomin you should try it, it's really fun! It's asymmetric, but not unbalanced for a beginner level. The 7x7 board is especially good.

P#14063 2015-09-12 14:59 ( Edited 2015-09-12 18:59)

Chess is imbalanced; I don't think game success is necessarily by merit.

More to the point, the Wikipedia article is talking about different rules than the "Brandub" reconstruction in arnaud_debock's link. Some of the variations the Wikipedia article suggests to make the game more balanced are in the Brandub rules, like 2-man capture of the king and the king having to escape on the corners.

P#14068 2015-09-12 17:38 ( Edited 2015-09-12 21:38)

@cheepicus, really? It's been a while since I played or looked into chess, but I thought it was sufficiently complex that it still wasn't a solved problem.

And I notice now that I came across very bluntly, so sorry about that. I just meant that the rules aren't fully known and it's probably best to make a balanced variant than the rules described in that wiki article.

P#14094 2015-09-13 00:07 ( Edited 2015-09-13 04:07)

The Brandub thing arnaud linked to is already a variant with some of those rules changes, tho.

I didn't read any ill will in your bluntness. I do disagree, though :) The evolutionary fitness of games is kind of a derail from Hnefatafl, so I'm just trying to be terse. Maybe modern chess is MORE balanced than one version of Hnefatafl that Linnaeus reverse engineered on his visit to Lapland, being unable to speak the local language, but if Wikipedia is talking about that game, it doesn't necessarily relate to the Brandub variant.

P#14111 2015-09-13 14:24 ( Edited 2015-09-13 18:24)

@cheepicus @innomin I'm finishing the Fanzine #2, but after that I'll focus on a playable version of the game. And you will be able to judge , how fun it is :)

This is sure than chess got more depth and emergence than Brandub. But what I like in Brandub, is the fact than behind it's apparent simplicity, it's a very tricky game .

P#14112 2015-09-13 14:30 ( Edited 2015-09-13 18:30)

I just released an iOS version of hnefatafl called Viking Chess! I didn't have a CLUE how to tackle AI, so I went multiplayer only.

AI for this game is super tricky. Where as in chess, there are clearly best moves for any situation (I can capture the enemy Queen without risking any of my pieces), things are much muddier with hnefatafl. While your general strategy as a defender is to get your king to a corner, you have to deceive the attacker as to how you plan to get there. Having the AI deceive is tough to differentiate from having it make bad moves (moving a piece towards a corner that is already blockaded).

AI aside, the other thing I had a lot of trouble with was group captures. If you surround a whole group of enemy pieces, they ALL get captured. None of the other iOS versions of tafl had this feature included, so I really wanted to nail it down. I ended up getting it and was extremely satisfied with myself when I did. If you need any pointers with that part, let me know!

Anyway, good luck with this, and I'll be keeping an eye on your progress!

P#14719 2015-09-28 21:59 ( Edited 2015-09-29 01:59)

@Schneider21 Yeah, it's an interesting problem, haven't fine any good solution yet.
If somebody want to team up, I'll be super happy.

P#14732 2015-09-29 10:17 ( Edited 2015-09-29 14:17)