On our browser game we have a battle system on top of a board game similar to chess. We soon started to think on implementing AI on the game, because that would add so much value to the game. We could create single player campaigns, we could add mobs and bosses to the universe. But implementing AI on this game proved to be a bit dificult, because it has many more combinations than chess, for example.
We don't have any experience on AI, so that made things harder. We studied AI on chess and that methods can be used for Orion's Belt as well, here's what we've learned:
- The chess computer programs use brute force to play. They try every single move and choose the best one. Choosing witch one’s the best its also a problem on its own. On Orion's Belt on each turn a player can make up to 6 moves... so this makes things a little harder...
- Each player’s move is called a ply. For each ply the program has to calculate the next dependent plys, creating a game search tree. This tree can become quite big and heavy, and there are some techniques that optimize it, like alpha-beta pruning or transposition tables.
- I always had this doubt: ok, I can see how the computer gets the best attack, it just has to check all moves and associate some kind of weight. But, how can the computer know how to defend? This is answered by the minimax algorithm: for each move you get, apply your own algorithm to the opponent’s side. This way you’ll know if your opponent can checkmate you in the next move.
- For every unit group, see if it can attack something, store that movement and it’s value. The value will be calculated by seeing how much damage this attack will produce
- For every unit group, rotate to all directions and the follow to 1.
- For every unit group, move to all directions and then follow to 2.
This algorithm is very basic and it won't harm an average player. Even so it's a great playground for newcomers to the game. And lets not forget that dificulty is always relative... we can have the best player, bug if he has a worst fleet than the bot, he may not win. It's a question of proper fleet balance, and try to make the match very hard to win, but doable.