Awaken, foul beast! (Game AI)

[Skummy]

Right, I'm not a programmer so I have no idea how this works. I think we were just making the point that it isn't going to be easy.

[Jerhod]

Do you know about Tesauros TD-Gammon program? Anyway, it's a program that plays backgammon (surprise, surprise!) and can challenge the very best human players. How did it become so good? By playing 1'500'000 games against itself! Fascinating, isn't it? The program could learn from its mistakes, or rather, from its good moves.

As a follow up to this, computer-AI backgammon players beat human players consistently for a long time because there were some statistically beneficial moves that the AI's were able to calculate that the human players were not able to recognize. (Humans use "pattern matching" to become good game players for just about every game, and the computers had essentially recognized a pattern that the human players hadn't been able to "see" yet.) However, after the human players caught on to these patterns, the humans were able to consistently beat the computers. Doesn't mean it's always easy, but we can beat our machines consistently.

One problem with a Blood Bowl AI is the idea of "over training" the computer. With a relatively simple game like Backgammon this isn't so much of a worry, but Blood Bowl is significantly more complex. The idea behind over training is that the computer will become so used to playing against itself that it will learn plays that are only good against its own style of play. When it starts playing against humans it won't be able to compete because it isn't at all used to playing against humans. Again, this isn't as much of a worry with a simple game like backgammon because there aren't very many moves to make, but with Blood Bowl I see it being a significant risk.

[Skummy]

As a follow up to this, computer-AI backgammon players beat human players consistently for a long time because there were some statistically beneficial moves that the AI's were able to calculate that the human players were not able to recognize. (Humans use "pattern matching" to become good game players for just about every game, and the computers had essentially recognized a pattern that the human players hadn't been able to "see" yet.) However, after the human players caught on to these patterns, the humans were able to consistently beat the computers. Doesn't mean it's always easy, but we can beat our machines consistently.

Why do I get the feeling you just ruined Matrix III for me?

Morpheus: That's right, Neo. The Blood Bowl AI is stronger and faster, but they will always have to play by the rules. Patterns will emerge. Patterns you can control and turn to your own advantage.

Neo: You're saying I can dodge Rat Ogres?

Morpehus: I'm saying that when you're ready, you won't have to.

[grep-v]

Again, this isn't as much of a worry with a simple game like backgammon because there aren't very many moves to make, but with Blood Bowl I see it being a significant risk.

I would worry more about the difficulty of applying Tesauro's technique on BB.
Whereas in Backgammon the Goal is directly related to the advancement of your pieces in a linear space with only few interactions (max. pieces per slot and so on) we have a more complex system in Bloodbowl with 2D space, more types of interaction and of course the passing system which can be considered a non-local interaction thus perhaps counteracting the convergence of the optimization.
If all these contras could be overcome, playing strength against humans would be just a matter of the number of games played.
(Of course I'm not striving towards a functioning application of Tesauro's method on BB, even if it would be REALLY interesting).

ciao

[Indigo]

Morpheus: That's right, Neo. The Blood Bowl AI is stronger and faster, but they will always have to play by the rules. Patterns will emerge. Patterns you can control and turn to your own advantage.

Neo: You're saying I can dodge Rat Ogres?

Morpehus: I'm saying that when you're ready, you won't have to.

lol thanks mate I've just spat coffee all over my monitor at work...

Child: Remember the truth. There are no double skulls.

[bitMonkey]

Darkson: LOL, yeah, a bad looser AI! That would be great. Beat him up too badly and the program terminates and won't start for several days.

Jerhod: Asymptotically, in theory, overtraining should not be a problem. Theory is all good and well though... maybe there is a problem here, I am not sure. The state space is huge, after all. However, it would not have to stop learning after having trained by playing against itself. It could store away a game played against a human, or several humans, and study them later. So the next version could be better than the previous.

Right, I wanted to ask you guys (are there any women here at all?) if there is a standard notation for recording a Blood Bowl game? You know, sort of like in chess? Maybe I should emphasize ''sort of''. I know it would not work ''off the shelf''. No need to cut my head off for that.

Skummy: Nice one! Totally off topic: I'm gonna see Matrix II today.

grep-v: I am a bit concerned with the fact that in backgammon you will with 100% certainty eventually do something good. You can only move forward, as you said, and no matter how poorly you play you will eventually start to move your pieces off the board. Needless to say, but I'll say it anyway, not so in Blood Bowl. By simple moving around at random, what are the chances of the program scoring a touchdown? Not too great I'd say. Maybe one would have to reward the program for possessing the ball, and even for moving it forward? But that's so dangerous... I'm afraid it would upset the main goal of the game. It's much cleaner if a reward was only given when a TD is scored.

[Indigo]

Right, I wanted to ask you guys (are there any women here at all?) if there is a standard notation for recording a Blood Bowl game? You know, sort of like in chess? Maybe I should emphasize ''sort of''. I know it would not work ''off the shelf''. No need to cut my head off for that.

Probably not - with chess you move one piece a turn, but in BB you move many pieces and do many different things. Not saying it's impossible mind you, just tricky. I think I might have a go next time I'm bored at work!

One thing I think we should work on as a community is a better way of creating "match reports" like WD does for battle reports. I don't think the way presented in BBmag #6 was very good, so I am working on an alternative...

[DoubleSkulls]

There are no double skulls.

I do exist, honest.

[Marcus]

I think you're in for an uphill struggle. Go is a game with a lot of set strategy and no random element, yet no-one has coded a good AI for Go. Poker is a game with a high random element and a vast amount of scope for interpersonal tactics, no-one has coded a good AI for poker.

Bloodbowl combines tactical positioning, risk management and interpersonal tactics. I don't think there's a good chance of making a good AI for bloodbowl.

I think you'd probably have to hook into emegent properties in the AI to make it play well, rather than try to code in all eventualities.

Simple directives like:

- Advance ball/recievers towards endzone to ensure scoring is possible within alotted time.
- Ensure opponent can't blitz ball carrier (factor in risk assessment so the AI doesn't make a 4+ dodge to force the opponent to make a 2+ dodge in their own turn.)
- If a player can't be used to advance scoring chances or make the opponent roll dice in their turn (diminishing returns apply if players have already met these criteria) then hit something. Use players to give assists where feasible.

Let the emergent properties of the AI take over from there. If you find they do ridiculous things and lose, adjust the weightings of the priorities. If you find they do ridiculous things and win, then maybe you've stumbled across tactics that a human wouldn't have thought of.

If you ensure the AI is focussed on winning the game by outscoring, then ensure that the AI's main plan is to make sure that the opponent makes more difficult rolls next turn than the AI is making this turn, I reckon you'd see the computer come up with some decent tactics.

Trying to make a computer memorise a human's list of tactics is a dead end. Give it simple priorities and let it think like a computer then see what happens.

[grep-v]

I think you're in for an uphill struggle. Go is a game with a lot of set strategy and no random element, yet no-one has coded a good AI for Go. Poker is a game with a high random element and a vast amount of scope for interpersonal tactics, no-one has coded a good AI for poker.

Bloodbowl combines tactical positioning, risk management and interpersonal tactics. I don't think there's a good chance of making a good AI for bloodbowl.

I don't know if it's possible, but I thing you missed one point in your statements: Go and Poker have simple rulesets causing complex patterns. Humans have definitely an advantage in these games. But in Bloodbowl I sincerely doubt that most players are playing pretty "good". So, no need to build a great, overwhelming AI, just one that is fun to play with. In game development that's exactly the path to success as nobody wants an AI that mops up the floor with you.

I think you'd probably have to hook into emegent properties in the AI to make it play well, rather than try to code in all eventualities.

Simple directives like: (...)

That are exactly the strategical and tactical patterns I mentioned/proposed before.

Let the emergent properties of the AI take over from there. If you find they do ridiculous things and lose, adjust the weightings of the priorities. If you find they do ridiculous things and win, then maybe you've stumbled across tactics that a human wouldn't have thought of.

And this is the "machine learning" part

Trying to make a computer memorise a human's list of tactics is a dead end. Give it simple priorities and let it think like a computer then see what happens.

The simple priorities alone won't help in this case, just as your first sentence explains. In defining these priorities we apply our human point of view. That's a starting point for designing an AI but later on you have to ensure that there is a mechanism for the AI to implement own priorities etc.
That's why I proposed a threefold model: to split the evaluation and planning in simpler parts that can later be optimized via automated methods.

[DoubleSkulls]

But in Bloodbowl I sincerely doubt that most players are playing pretty "good".

Most chess players aren't Grand Master level either...

[Marcus]

grep-v: you don't need a human point of view if you define the priorities in terms of the rules of the game. The winner is the one who carries the ball into the endzone more times than the opponent. That's a priority.

How you go about doing that is a matter of crunching numbers, which a computer can do. My main suggestion is the application of poker theory to make sure the opponent is making worse dice rolls than you at every step.

[grep-v]

Most chess players aren't Grand Master level either...

That's why it is hard to develop a GM-level chess program and equally hard to develop an entertaining chess program for the average player, which assesses the skill of the player and achieves slightly less than 50 % wins with widely varying playing style.

[grep-v]

grep-v: you don't need a human point of view if you define the priorities in terms of the rules of the game. The winner is the one who carries the ball into the endzone more times than the opponent. That's a priority.

The last thing is a priority indeed. But only for a single game, a whole league season may have different priorities, a tournament also, etc. pp.
But that is a pretty high level goal and thus hard to implement by any means. Even the before mentioned method of Tesauro is based on simpler preconditions.That's why I tried to break it down to simpler patterns. Of course the choice of the simple pattern can be influenced or even motivated by some larger pattern for a whole game, which can be influenced by an even larger pattern for the whole season, which can be .... you get the point. But that's beyond a starting design for a game AI.

How you go about doing that is a matter of crunching numbers, which a computer can do. My main suggestion is the application of poker theory to make sure the opponent is making worse dice rolls than you at every step.

Hey, that's my playing style !
But I see BIG problems with implementing it for Bloodbowl. To decide which dice rolls your opponent has to make, you have to determine the goals of your opponent. In Poker it is simple: have better cards than the opponent. In Bloodbowl it only sounds simple: make more TDs than your opponent. While in Poker the goal and outcome of the game is directly connected to the sample space which has a total order. So it is relatively easy to determine which action bears what risk in a probabilistic way (RELATIVELY, it's still a hard problem).
In BB the sample space is not only substantially larger, it also hasn't any order. By looking at a position you can tell if a TD is possible, but looking at two positions in general you cannot tell which one is better. So how are you going to tell which dice rolls your opponent is going to make? Should he reach this position or that? You may still do this analysis by brute force but that is not a feasible task.

[DoubleSkulls]

By looking at a position you can tell if a TD is possible, but looking at two positions in general you cannot tell which one is better.

Its pretty hard but you ought to be able to score a given board position e.g. how close am I to scoring, how well protected is the ball/ball carrier etc, or not if you are on D.

Then you can work out the risk associated with the position and intervening positions to choose the one to go for.