search

apotapov / tafl

Android implementation of a Tafl game
Apache License 2.0
2 stars 0 forks source link

Implement AI - Moderate Level #1

Closed apotapov closed 10 years ago

apotapov commented 10 years ago

Take a look at some of the approaches for AI board games:

http://gamedev.stackexchange.com/questions/30026/checkers-ai-algorithm http://gamedev.stackexchange.com/questions/16135/how-to-implement-a-i-for-checkers-draughts http://en.wikipedia.org/wiki/Computer_Othello

ghost commented 10 years ago

I did a lot of research today, looking for any stuff we can use off the shelf. I primarily searched for:

1) available source code we can directly use 2) papers or guides talking about how to implement an AI component for Tafl (or something very similar) 3) strategy/tactics guide for Tafl

I had a tough time finding (2), but I got us some stuff for the other two items:

(+) Here's a javascript implementation of Tafl with decent AI component. The code is available! (http://www.lutanho.net/play/hnefatafl.html) (+) No book on Tafl, except its history and rules. Good free content on strategy and tactics though: (-) Good high level: http://tafl.cyningstan.org.uk/page/29/forming-a-strategic-plan (-) Good breakdown by one of the world's top players: http://www.tim-millar.co.uk/section509308.html (-) A little annoying but decent videos: https://www.youtube.com/watch?v=gND2P1sHM3U (+) I've dug up a good number of contacts via the web we may be able to help us with building a computer opponent.

Complete Notes

1) Hnefatafl using rulesets downloadable code

2) Genetic algorithm approach to Tafl AI http://ro.ecu.edu.au/cgi/viewcontent.cgi?article=5968&context=ecuworks

3) A bunch of resources on Tafl http://aagenielsen.dk/hnefatafl_links_en.html

4) Note to Self: Different names for the same game:

5) Amazon book about old games with new twist:
http://www.amazon.com/Rules-Classic-Games-Wayne-Schmittberger/dp/0471536210/ref=sr_1_6?ie=UTF8&qid=1390602704&sr=8-6&keywords=tablut

6) Concise but good strategy advice http://tafl.cyningstan.org.uk/page/29/forming-a-strategic-plan

7) Searched for open source

8) Several places say Defender has the advantage

9) Best strategy explanation online so far http://www.tim-millar.co.uk/section509308.html

10) Free source code for Tafl last updated Jan 12, 2014 http://hnefatafl.se/

11) Youtube videos on strategy (in several parts) https://www.youtube.com/watch?v=gND2P1sHM3U

12) Hosts a website that allows human-human Tafl tournaments

13) Caltech alumnus implements variations of Tafl online: http://alumnus.caltech.edu/~leif/games/Hnefetafl/ It seems like he has implemented the AI for computer opponent.

14) Javascript implementation of Tafl game with AI opponent!

15) Java applet implementation with computer opponent

ghost commented 10 years ago

I suggest we use this for first version of AI: http://www.lutanho.net/play/hnefatafl.html. In his javascript code, look for function GetBestMove(cc). The only drawback is that the king capture on requires two pieces (instead of four).

apotapov commented 10 years ago

This is awesome. I'm gonna start digging through it. Will start with http://www.lutanho.net/play/hnefatafl.html. Don't think it's going to be too difficult to change to 4 piece capture heuristic.

apotapov commented 10 years ago

There's a lot of really good info here. I'm moving it to the wiki: https://github.com/apotapov/tafl/wiki/Research

I started breaking down some of the information into separate pages.

Who knows, maybe we can publish a book on this stuff once we compile it. Haha

There's a secondary product for ya: Tafl Strategy Guide ebook

ghost commented 10 years ago

Oh, thanks for organizing the info. I wouldn't use genetic algorithms for the AI. It was just an interesting paper. I suppose if we were trying to solve for the general case, an evolutionary algorithm to tweak the utility function for minimax would be a decent approach. But sounds more like CS research than game building.

apotapov commented 10 years ago

I do like the idea of testing AI against itself. This way we can figure out how to make the game more balanced and tweak the AI in different ways.

We should start thinking about the heuristic function. After reading some of the strategy, I can already think of a few things we can use to evaluate the board.

Black:

White:

Both:

apotapov commented 10 years ago

Series of articles about designing a Chess game: http://www.gamedev.net/page/resources/_/technical/artificial-intelligence/chess-programming-part-i-getting-started-r1014

There's a ton of useful info here. Data structures, AI algorithms, etc. I'm wondering if we can find more information about things like Opening Move. Perhaps there are some forum resources.

So far these guides have proved to be pretty useful: http://www.tim-millar.co.uk/section509308.html http://www.tim-millar.co.uk/section502917.html http://tafl.cyningstan.org.uk/page/30/general-strategy-for-the-attackers

Also according to this: http://www.tim-millar.co.uk/section502917_181959.html The world championship rules state that a king cannot be captured against the side of the board. Should we change that as well?

Should use this for the evaluation function: http://www.tim-millar.co.uk/section502917_182106.html

The TAFL facebook page also looks pretty active: https://www.facebook.com/HnefataflBoardGame