Giving it a brain: A BloodBowl AI
(...) they built themselves a stupendous super computer which was so amazingly intelligent that even before the data banks had been connected up it had started from I think therefore I am and got as far as the existence of rice pudding and income tax before anyone managed to turn it off (...)
Douglas Adams, "The Hitchhiker's Guide to the Galaxy"
Some days ago I decided to write a TCP Client/Server Application for learning purposes. In order to make the project more fun, i started writing a BloodBowl game (a game which I used to play some years ago...). Few weeks later I found out that there already exists some BloodBowl games. Reinventing the wheel again and again makes no sense for me, so I stopped that project. But after playing some games on FUMBBL, I found out that one little detail is missing in every BloodBowl game I know about - a computer player.
Being intuitively fascinated by Artificial Intelligence I decided to fill the last white spot on the BloodBowl map and started to work on an AI. Things began to grow. I created a basic framework that knows most parts of the BloodBowl game and some simple analyse functions and a basic GUI to display game data and analyse results. Meanwhile it became obvious that an BloodBowl AI would be a very huge pile of work and that this task cannot be done by one single human, at least not in the next 10 years...
Finally I released my work, now known as "BloodBowl a la carte" (BBalc) under an open source license and put it on SourceForge.net. Simultaneous I started the BBalc Wiki, in order to provide documentation about my work, and to offer the occasion to discuss all parts related to a BloodBowl AI.
And this is what this article is about: I need YOUR help! (In fact I would love to say: WE need your help, but after more than 1000 project page visits on SourceForge and 40+ downloads later, I got exactly 2 sentences of feedback, which can by found on the projects SourceForge project page.) Well, I need support in coding, web design etc. but this article addresses the "ordinary" BloodBowl player. BloodBowl is a very varied game. There exist lots of teams, lots of skills and players on the board can act in several ways. Because of that there is no definite way to BloodBowl. Each team has his way of playing and game play depends highly on the skills owned by your player.
There are several approaches to artificial intelligence and in fact it is fundamental to define which kind of intelligence behaviour you want to simulate. Another important thing to look at is the AI s ability to learn from its environment and decisions. Some prominent approaches to AI are expert systems (using predefined rules to solve a very special tight bounded task), neural networks (these try to simulate the functionality/learning behaviour of the human brain) and genetic algorithms (they learn how to behave in their environment by using evolutionary methods).
In BloodBowl we have the definitions of the board, the players, the teams and the rules to work with. Based on the rules we can calculate probabilities for every possible player action. This results in abstract patterns to work with, e.g. a ST3 versus ST3 block is effectively equal to a ST2(+2 Support) versus ST3(+1 Support) block.
Which kind of AI gets implemented in BBalc is not yet defined and it will possibly be a mixture of the above called approaches and others.
Variety of decisions
One single standard Block action results in "Opponent pushed back" or "Opponent knocked over and pushed back" or "Opponent knocked over" (the occasions where the attacker or both players are knocked over is irrelevant for the Al's planning because it ends the turn). In the first two cases above, the attacking player can choose to "Follow Up" or he can stand where he is. Then there are 3 different fields for pushing/knocking the opponent player into and a player being knocked over can be "Knocked Over", "Stunned" or he might be "removed from the board" - this gives us 28 possible outcomes for a simple Block action.
Another example is a standard player who can move approx. 6+2 squares. That results in 288 possible squares to move into but that can easily be topped by a "OneTurner" who can (in worst case) move all over the board (approx. 400 squares). At least slow players like a mummy have 120 possible fields to move into.
These are only the possible board mutations for a single action from one player. In fact you have up to 11 players on the board and for instance some of them might choose from 1 of 8 possible block actions.
You might say "OK - that are only 28 different mutations" but imagine you have 11 player who can execute exactly one block action each ... - "Well, that results in 308 different mutations - peanuts for your 3+GHz machine with lots of RAM... what is this guy talking about?"
Exploding decision trees
But that is not true - imagine the AI turn starts. The AI tries to find the very best move to do. To accomplish that it has to calculates every possible combination of actions (and their results). For example it starts with player 1, then moves player 2 and then blocks with player 3 and so on. That is a single branch of the decision tree. In fact it is possible to start with player 3 moving somewhere, throwing some blocks with player 5,6, and 7 and so on.
As a result you get a decision tree which is as huge that it can be effortlessly be called incomputeable (in reasonable time) and in fact we would like to analyse each single outcome of that tree which take lots more of time than creating the tree...
Well, this might be the reason that there is no BloodBowl AI out there...
Chopping the tree down
In their daily BloodBowl matches, everyone experienced playing against skilled players who come to a decision very quickly and Rookies who think 5 minutes and more about an average move. This gets obvious if you know that human task solving is often based on heuristics (Heuristics are rules of thumb in colloquial speech). The experienced player uses a set of well fitting heuristics to come to a decision, where the rookie player calculates the outcome of some (still a very reduced part of the decision tree) promising actions and their possible effects on the game. The experienced players heuristics are just a bit better.
As a result the main goal of BBalc (at this time) is to find effective heuristics (rules of thumb) for the different parts of the game.
Stand up for your right!
As stated above I need your help. First of all I want to state clearly that I don't gather information in order to sell it to your worst opponents. I need to find out which general and special heuristics exist and when to use them. There are rules that might work for some teams, some rules do only work for a single team etc... Therefore I need lots of data to work with - the more the better. All contributions are kept anonymously except the one from Wuhan, but his style is already some kind of open book for most player, isn't it?
In the BBalc Wiki there are currently two pages dedicated to surveys. One of them is the Eureka! page which tries to collect simple heuristics for different situations. The other is the ScenarioPage where you find simple scenarios that have to be solved. Please visit the Wiki page and try to answer the questions there and/or process the first scenario.
In fact the BBalc Wiki is a place for discussion on everything concerning BloodBowl AI. Each page has an dedicated discussion page and you can simply add new pages to the Wiki if you like.
Thank you very much for reading this!
I hope that you feel motivated to share your knowledge with me (and as a result with the BloodBowl community).
So far - don't panic!
P.S.: some interesting links...
BloodBowl a la carte homepage: http://www.internnetz.de/bbalc
BBalc Wiki: http://www.internnetz.de/bbalc/wiki