Page 1 of 2

Neural networks artificial intelligence

Posted: Sun Feb 26, 2017 9:44 am
by Hagbard
In internet archives is a ten year old research paper of a neural networks artificial intelligence project in Australia:

"Evolving Players for an Ancient Game: Hnefatafl", Philip Hingston, Edith Cowan University, Australia, 2007
https://pdfs.semanticscholar.org/ba25/8 ... 784d7c.pdf

The paper mentions the shieldwall rule, which we use in Copenhagen Hnefatafl.

Re: Neural networks artificial intelligence

Posted: Sun Feb 26, 2017 9:48 am
by Hagbard
25.2.2017 I received this email:
Hello Sir,

I'm a data scientist that was looking to work on a new side project with some collaborators: creating an AI that can play Hnefatafl from either
side. This wouldn't be by conventional heuristic means, but by feeding it the boards and moves of previous games played by humans.

The model implemented is a deep learning
<https://en.wikipedia.org/wiki/Deep_learning> one which will attempt to learn from a corpus of game data. It doesn't even have to be any
"grandmaster"-caliber game data, as even amateurs make moves based mostly in their own self-interest (at least, in the short-term).

Such efforts have been successfully implemented
<https://github.com/imthexie/giraffe> and even published
<https://arxiv.org/pdf/1509.01549.pdf> for symmetrical games like chess, but I don't find any records of this being done for asymmetric strategy
games like Hnefatafl. Besides it being less globally popular, I suspect this is because there exists no massive corpus of game data.

And this is why I contact you tonight. I stumbled across your site, and I have noticed that you have a sizable archive of games and their moves.
Might I ask that you make available this data to me and my collaborators so that we can attempt such an effort? It's not likely to succeed, but I think
it would be rewarding to give it a go. We can work with any format you provide.

In any case, this is just a side-project of ours, and if you wish to keep your hard-earned and well-curated data to yourself, I completely understand.

Many thanks for your time and consideration,

Bryan Dannowitz

Re: Neural networks artificial intelligence

Posted: Sun Feb 26, 2017 9:59 am
by Hagbard
Bryan Dannowitz wrote:
creating an AI that can play Hnefatafl from either
side. ... by feeding it the boards and moves of previous games played by humans.
The model implemented is a deep learning ... one which will attempt to learn from a corpus of game data.
Hello Bryan Dannowitz,
that's an interesting project. Could it result in a neural networks robot accessible for free as an opponent for tafl players on the internet?

I would recommend to try the project on Historical Hnefatafl 9x9 (Saami Tablut) and Historical Hnefatafl 11x11 (Welsh Tawlbwrdd).
The game rules are found here:
http://aagenielsen.dk/historical_hnefatafl_rules.php
Adam Bartley did a pdf-layout of the rules here:
http://aagenielsen.dk/TaflRulesEnglish.pdf

A full extract of games between strong players are put on the net here:
Tablut games
http://aagenielsen.dk/tafl_tabluts.txt
Tawlbwrdd games
http://aagenielsen.dk/tafl_tawlbwrdds.txt


A ten year old research paper of a perhaps similar project in Australia can be found in internet archives:
"Evolving Players for an Ancient Game: Hnefatafl", Philip Hingston, Edith Cowan University, Australia, 2007
https://pdfs.semanticscholar.org/ba25/8 ... 784d7c.pdf
but this old project is probably not based on as many game data.


Good luck with the project!
Aage Nielsen, Denmark

Re: Neural networks artificial intelligence

Posted: Sat Jan 27, 2018 7:42 pm
by Hagbard
"cc dark" sent this mail:
Greetings!

You should totally use neural net to make this game complete.
I suggest to stay close with one version of the game as much as possible.
Keep a single set of rules and call it just simple Tafl.

Put aside all historical threads, who cares how they played it? All great games walked long roads of metamorphoses to become truly playable. Chess, Xiangqi, Shogi are great examples.

But Tafl is so unique, wonderful, asymmetric game with one king! It deserve to be one of the top boards games. We don't have centuries, but we have technology at our side to shape this game to its potential.

Also, "escape to the edge win" aesthetically is more beautiful for gameplay in my opinion.

Re: Neural networks artificial intelligence

Posted: Tue Jan 30, 2018 8:40 pm
by Fishbreath
Oh, data! Excellent. One of these days, I'm hoping to compile a corpus of games in OpenTafl save-game format; I already have a converter for PlayTaflOnline, but still need to write one to handle games from here.

If you have more data in that format, I might go ahead and write a parser.

As far as neural networks go, I'd love to take a crack at that sometime. Even with the combined set of games from here and PlayTaflOnline, I doubt there's enough data for directed learning, though, and I certainly don't have sufficient computing resources to do undirected learning in the same sense as DeepMind.

Re: Neural networks artificial intelligence

Posted: Mon Nov 19, 2018 1:44 pm
by nath
@Fishbreath: Do you think we can get the code nice and clean? I see that as the major issue. I actually say I'm very much interested in that route, and wouldn't mind contributing. Please don't compare everything to chess - that's a totally different game. Chess has much more complex representation because of this 12 different pieces (instead of 3). I think we have even a reasonable representation available, since our game is more about mobility than material. Please contact me, if you think we can get a clean and workable codebase for that.

Re: Neural networks artificial intelligence

Posted: Wed Sep 18, 2019 11:24 pm
by Ytreza
Hello,

Is there any update on this topic since last year? I have found a code here:

https://medium.com/applied-data-science ... 664945c188

which seems very easy to adapt to any game. I have no expertise on AI but if I understand the procedure correctly, the only thing one should do is to write the representation of the game (for hnefatafl I guess a 11x11 array with e.g. value 0 for empty squares, -1 for attackers, 1 for defenders, 2 for king), the representation of the moves (here any couple of coordinates on the same line or column), the conditions allowing a move (is the path free and doesn't end on a forbidden square and is there a pawn on the first specified square), the rule for playing the move (remove the pawn on the first coordinates, put a new one on the second and remove captures), the win conditions (to simplify, say white should put the king on corners or in a edge fort and black wins if white doesn't after x hundred moves), and that's pretty much it!

The very nice thing is that it is based on alphazero, so no sample of played games are needed: the AI learns from scratch by playing against itself. No evaluation function is neither needed. It's really as simple as encoding the rules and let the algorithm play thousands and thousands of games.

The results could be so interesting! First one could plot the evolution of the win percentage for white as the number of games played by the AI increases (100% is expected at the beginning, but then does it converge to 60%? 30%? 0%? or does it stay at 100%, is there an absolutely unstoppable strategy for white??). Then, given how simple it seems to implement various games, one could test various variants. It would also give clues about strategies... Should white try to escape right in the opening, or should he focus on capturing black so that black cannot prevent the edge fort in middle game? Is it a good idea to put defenders in several corners at the beginning? Should white put all his effort in only one corner? etc.

I'll try to work on this in the forthcoming days. I encourage you to also think about it (a basic knowledge of object oriented programming in python is required). It seems so simple... We have to try that :)

Re: Neural networks artificial intelligence

Posted: Sat Sep 21, 2019 6:52 pm
by nath
Hi Ytreza!

Thank you for your interest! I lacked the motivation to try something completely myself, but the idea was indeed to use tensorflow (or some framework based on tf). It's somewhat simple, yet still very hairy in the details of getting the C/C++ and python parts to interact properly and coordinate the whole thing through distributed infrastructure. It's not hard-hard to do that, but's harder than this article is suggesting. Connect for on 9x9 is fairly trivial game. It's well understood by humans, and there is not reason to loose a games unless you are dead tired. Furthermore the maximal amount of moves per game is just much, much lower...not regarding the overall tree and game complexity.

I have some remarks, from an ai standpoint (I worked some time as data engineer and even did some data science) and from my view as Hnefatafl player.

I'll start by the obvious: 1. You need to hone-hot the input fields. That means IF you would (I'll explain the "if" later on), you'd want to feed the board to ai, you should three three input vector for all fields besides throne and corners. If all are zero the field is empty and they exclude each other semantically. Every thing else is just crippling the ability of the network to learn something, because it first has to learn that differentiation. That would still give very most input size of 354 and depending on the choice of output layer a few k output nodes. I'll dedicate a different point (see 3) below) to the topic, yet naively that would be 2320 nodes, a more involved method including the piece little less than 7 k output nodes (irc that should be about 6.8 k). Either way you'd still need an external component checking whether the move is legal (don't implement that in python - that is asking for trouble; ffi sounds like a sane option see 2)). I wouldn't feed that information back to network (like is done quite often today), but just write a cheap wrapper that chooses the best ranked legal move.
Btw: In that case might omit the 72 moves onto corners that are always winning anyways.
2. The basic learning will quite some time and computing power. While I'm happy to help with that, we should limit the scope. I'd suggest 50 moves without capture as a limit to mark the game as won for black. Hundreds of moves just means having less training games.
The checking for edge forts is quite complex. I think we shouldn't include that component in the training until the ai reached a notable level of skill. casshern could surely defeat OdinHimself, Adam, crust or me without using edge forts.
It's furthermore important to include some random moves. We should start with more than 70 % and go down to maybe 2 % or so. That should allow us to go notably above random play in just a few hours.
3. I mentioned that above, but the moves have three important properties The most important properties are the target square and the moving piece. Yet the source field is important as well. It's helpful for the network not have to learn the difference between white and black moves, so it makes sense to include both in the output layer. Convolutional layers aren't likely to help, because the broad area of the board is less important than sparse rows.
4. The possible moves are a way better way of understanding the game than to understand the current position (even though there is no function onto positions). If we don't hand that information to the ai, it first have the learn the rules of the game, which is quite hard. I'm convinced that exposing the possible moves to the network is the right move raising the size of the input layer the size of the output layer.
5. The movegen shouldn't be written in python, if you want any meaningful results for Hnefatafl at all. That's just to painfully slow. Are you used to ffi? I can provide some basic code for movegen if you like.

I'm convinced that I can answer the questions you asked about the game. White has to play very aggressively and a piece isn't important. White has to attack several corners at once - a single thread can be matched by black. I still believe that an ai could reveal a lot about the game. We are practically blind when it comes to the best play.

If you are interested in building a platform so others can contribute though playing games with the current network that will be collected and used for training on a single machine, I'd gladly contribute (both with code and hardware). Just drop me a note.

Regards
Nath

Re: Neural networks artificial intelligence

Posted: Sun Sep 22, 2019 1:34 am
by Ytreza
Hello Nath and thank you for your answer,

Yes after playing a bit with the code I realized by myself that this method couldn't be blindly applied to hnefatafl. Actually it already takes a very long time to get an acceptable AI playing connect4.

As I wrote in my previous post, I have no experience at all in AI programming, neither from the point of view of computer science nor in maths. I am a theoretical physicist and I just program fairly simple codes to encode physical models and so on (I know C,C++ and python), but there is nothing as crazy as DNN. I'm afraid I would not have time to dedicate myself to another big project as you seem to suggest it is. But maybe working together we could get somewhere? It is surely tempting. Also, if we obtain a fairly good AI we could think about writing a scientific paper.

To answer your remarks:
1. I didn't understand what you mean by "you should three three input vector for all fields". By "fields", do you mean "squares"?

2. I plotted the number of wins as white and black in 2012, 2017, 2018 WTF tournaments as function of the number of moves. The peak for white's wins is around move 25. Around move 60, the number of wins as white becomes smaller than the number of wins as black. Then it drops more or less exponentially with a "characteristic number of move" of 100, above which white's wins are negligible.
Therefore I think that one could set a threshold of 100 moves above which black wins (100 moves total, with or without captures).
I agree that edge forts don't seem to be so important. However their importance could be revealed by the AI (see below).

3. I don't get the point (I don't understand " It's helpful for the network not have to learn the difference between white and black moves, so it makes sense to include both in the output layer.")

4. I think that's how the AI I refered to is coded. Two variables are given as input to the network: the position of the pieces and the allowed moves.

5. Yes, python is slow. I'm not used to ffi but I don't think it'd take much time to learn, and it would be useful in any case for other projects.

A question I keep asking myself about hnefatafl strategy is should white really try to escape, or rather capture as much black pawns as possible to get space to build an edge fort? Most games I see (my games but more importantly games between high rank players in the archive) end because white or black chose a wrong variation at some point. The questions I expect an AI to answer are:
i/ Is there a winning corner attack for white? (100% chance of winning). This would be very disappointing of course (the games would end in the opening).
ii/ Is there a winning strategy for white? (again, 100% chance of winning, but not in one single corner attack, e.g. first deplete black's forces, then move the attack to an adjacent corner). This would be more interesting but again disappointing (the games end in middle game, as seen most of the time in this website).
iii/ If not ii/, that means there is always a variation leading to the blocking of all corners by black. This would be very interesting. In that case, the goal for white in middle game would not be to escape, but to threaten to escape so that black has to sacrify pawns. I think (tell me if you don't agree) that when white manages to capture 6 attackers, he has good chances in endgame even if the corners are closed. The reasonning behind this number is as follows: black needs 12 pawns to close the corners, so if white captures 6, black is left with only 6 "movable" pawns. If white made 6 exchanges in middle game, there are 6 white + powerful king VS 6 black in endgame fighting to build/prevent an edge fort.
In this case, the games would be very interesting with a lot of long-term strategy involved (not only computation of tactical variations for corner escape).
That's why I said above that edge forts could be very important at some level of play.

Anyway, I'm afraid I don't have the capabilities and time required to program this nice stuff for now, but I really hope someone will do it someday! From a newbie point of view, it doesn't seem so hard for an expert (ok, harder than just feeding alphazero with the rules, but still...)

Cheers
Ytreza

Re: Neural networks artificial intelligence

Posted: Wed Sep 25, 2019 1:43 am
by nath
Ytreza wrote:
Sun Sep 22, 2019 1:34 am
Yes after playing a bit with the code I realized by myself that this method couldn't be blindly applied to hnefatafl. Actually it already takes a very long time to get an acceptable AI playing connect4.
I think it might. At least if you have a few millions to spend on hardware and power.

Some people like to just throw more computing power at a problem, but I'm none of them.
Ytreza wrote:
Sun Sep 22, 2019 1:34 am
As I wrote in my previous post, I have no experience at all in AI programming, neither from the point of view of computer science nor in maths.
I can help with that. From a mathematical standpoint it's just awful anyways. I mean seriously. :?

We have no idea whether something similar happen if try two times. The practical results just give a notion of "usually".

But if you have questions, I'd be glad to help.
Ytreza wrote:
Sun Sep 22, 2019 1:34 am
(I know C,C++ and python), but there is nothing as crazy as DNN.
That's more than enough for this project. All the heavy lifting stuff should be written in C or C++. I have build NN in low level languages by hand for years, but with tensorflow (tf) there is no really reason to do that anymore. It's better than everything I've ever build and in my eyes the real reason to use python. It's at least the real reason I'm dealing at all with this ... language.

That being said, we should be able to get nearly all of the stuff we need from higher level framework keras (which is just tf with a small wrapper).
It still helps to understand what you are doing, but it essentially safes us the hassle to implent own DNN stuff. It's not the hardest thing I've done in my life, but it's very error prone.
Ytreza wrote:
Sun Sep 22, 2019 1:34 am
I'm afraid I would not have time to dedicate myself to another big project as you seem to suggest it is. But maybe working together we could get somewhere?
It's similar on my end. I can't make this my number one project right now, but that doesn't mean I can't invest some time.
Ytreza wrote:
Sun Sep 22, 2019 1:34 am
It is surely tempting. Also, if we obtain a fairly good AI we could think about writing a scientific paper.
Let's start by building one. The question is whether our approach make it stronger, not whether it gets decent strength. But either way we have to build it first.
Ytreza wrote:
Sun Sep 22, 2019 1:34 am
1. I didn't understand what you mean by "you should three three input vector for all fields". By "fields", do you mean "squares"?
Yes, sorry. I should have stuck to one notation.
Ytreza wrote:
Sun Sep 22, 2019 1:34 am
2. [...]
Therefore I think that one could set a threshold of 100 moves above which black wins (100 moves total, with or without captures).
I think that won't be the most relevant question. At the same time I've seen that games can stay interesting for quite a long time, if both sides do top notch moves. Usually humans make mistakes, because humans suck...
But we can start with 100 moves in total, sure.
Ytreza wrote:
Sun Sep 22, 2019 1:34 am
I agree that edge forts don't seem to be so important. However their importance could be revealed by the AI (see below).
There is a difference between the scenarios.
We will loose a ton of computing power before the ai is able to play strong enough to threaten a total beginner. It's important to make the stuff as simple as possible when we start out. I'd like to instroduze new concepts to this ai as we go. It's much faster to take an ai with basic understanding of the game and teach edge forts, but to learn a new ai. That being said it's hard for the ai to notice edge forts at all. It's not mainly about the 100 moves. It's more about the fact that it takes a long time for the ai to figure that out, because you need A LOT of luck to build an edge fort by accident. And you need to do that many times for the ai to figure it out.
Ytreza wrote:
Sun Sep 22, 2019 1:34 am
3. I don't get the point (I don't understand " It's helpful for the network not have to learn the difference between white and black moves, so it makes sense to include both in the output layer.")
Hnefatafl is so interesting, because it's a very asymmetric game. For that every reason we should differentiate the output nodes and designate individual ones to every kind of piece we have in the game. We have just three types, but it makes it simpler, because it gives a sort of meaning the the individual move.
Ytreza wrote:
Sun Sep 22, 2019 1:34 am
5. Yes, python is slow. I'm not used to ffi but I don't think it'd take much time to learn, and it would be useful in any case for other projects.
If you want to continue to use python, it's helpful. If you want to do reinforcement learning it's great. I find it a chore (like almost everything in python).
Ytreza wrote:
Sun Sep 22, 2019 1:34 am
A question I keep asking myself about hnefatafl strategy is should white really try to escape, or rather capture as much black pawns as possible to get space to build an edge fort?
That question isn't reasonable inherently. Because you can do neither if black doesn't want to allow it. Black allows you to attack a certain corner or to take a pawn. The point is that while it's very easy to defend a single corner or keep all pieces, doing all at once is hard.

In my personal experience having a pawn more or less is not the important part. The total amount of pawn is usually not the issue regarding edge forts. It's much more the systematic weakness of two adjacent corners that bind all the available pawns that are now missing to provide even basic protection the the edge.

As much as I'd like this to be answered by an ai, that is nothing an ai will tell us 2019 or 2020. There are a lot of simpler questions that need to be answered first.
Ytreza wrote:
Sun Sep 22, 2019 1:34 am
Most games I see (my games but more importantly games between high rank players in the archive) end because white or black chose a wrong variation at some point. The questions I expect an AI to answer are:
i/ Is there a winning corner attack for white? (100% chance of winning). This would be very disappointing of course (the games would end in the opening).
I doubt there is a simple solution. But that is indeed something I'd like an ai to have a say on. At the same time it doesn't prove anything, it just suggests...
I think the other questions are interesting, but at least for now totally out of scope.
Ytreza wrote:
Sun Sep 22, 2019 1:34 am
I think (tell me if you don't agree) that when white manages to capture 6 attackers, he has good chances in endgame even if the corners are closed. The reasonning behind this number is as follows: black needs 12 pawns to close the corners, so if white captures 6, black is left with only 6 "movable" pawns. If white made 6 exchanges in middle game, there are 6 white + powerful king VS 6 black in endgame fighting to build/prevent an edge fort.
In this case, the games would be very interesting with a lot of long-term strategy involved (not only computation of tactical variations for corner escape).
That's why I said above that edge forts could be very important at some level of play.
I don't think that's such a mayor problem as you make it out to be. Think about 16 black pawns bound in the corners. That means that white can choose any corner and position 5 pawns at VERY specific squares and the sixth pawn further defending the exposed pawn and the king inside the castle. That means that upon the symmetry of the board there are just two possible positions for the white pieces (king at the corner and king one square away). Even though black has just two pawns to defend that's not really that scary, even if you have just two free pawns to defend. The point is that the white edge forts get much scarier if white manages to get 4 connected squares at a single edge. But if black can prevent that...
Ytreza wrote:
Sun Sep 22, 2019 1:34 am
Anyway, I'm afraid I don't have the capabilities and time required to program this nice stuff for now, but I really hope someone will do it someday! From a newbie point of view, it doesn't seem so hard for an expert (ok, harder than just feeding alphazero with the rules, but still...)
A decent movegen on it's own, isn't easy already. Tf isn't that hard, but setting up the flow graphs is still a chore. Yes, I do notice I use that word a lot when it comes to python. We haven't talked about the graph. After all the estimation of depth one will never be *that* great. That's true for Hnefatafl much more than it's for other games like chess. Once the two components of training and producing training data are well encapsulated components, that can be executed asymmetrically, the network stuff should be fine. After all we don't even need to compress the stuff very well. Even three bytes per move would be fine (even 10 bytes shouldn't be a problem).

Let's formulate the plan on a very high level:
1. build movegen (I sort of have one)
2. use the movegen to feed some tf graph
3. feed that into some classical data structure (so the engine is able to "inspect" positions)
4. use the classical recursive reinforcement learning to update the DNN
(5. do that as a distributed system)

Regards
nath