How to design the AI for a board game like Risk?

Question

I am about to develop a web game that is similar to board games like Risk, and iOS games like Lux and Strategery. I am curious to know what the concept behind the AI for such games should be like.

I know it's going to involve a lot of move calculations and and calculating all possible options. But can someone elaborate on this please? I am actually a web programmer who usually develop websites and program logic to them, so game development is something new to me.

Also, my boss would like to implement different difficulty levels for the AI. What are the principles behind something like this? Would the difficulty level correspond with how many steps/turns ahead the AI would calculate for each movement? (Like easiest difficulty would be the AI only calculating all possible moves for this turn, whereas in the next level of difficulty, the AI would calculate all possible moves for this turn and the next turn?)

Thanks!

Answer 1

i don't know about Risk but i had developed a Chinese Chess game few years ago. I think you can try Minimax which the game calculate every possible decisions and each decision will branch out a node for all the players until a certain depths within reasonable time. I think it is suitable for most turn based games. For 'difficulty' your game will randomized the node paths based on success rate of the paths, higher difficulty will give more 'weight' to the higher success rate paths. Also, you might want to limit the depths of the calculation, easier = less depth, harder = deeper depths.

Answer 2

Risk has too many potential moves and too many potential outcomes per move to have a Chess-like AI be effective. You don't need to consider every possible move, and you don't need to do look-ahead.

I would suggest you get some playtesters, or at least one or two smart gamers to help. If you're really just taking the Risk rules, or some sub-set of them, then you can borrow the known strategies for such games. Make an "expert machine" heuristic computerized opponent, by figuring out how a player would play, and program routines for that. You can have a variety of considerations and apply them based on the situation and various rules, and some random numbers to keep things unpredictable. Things like moving armies to the "front line" provinces, and towards prime target provinces. Favor moves that don't expose your territory as much, complete objectives, and have some threshold for leaving some troops on the front rather than burning down to single armies on the fronts. You can have difficulty levels by reducing the number and/or likelihood of the opponent applying some of the strategies. i.e. the Easy opponent may tend to only leave one or two armies on his fronts.

Program a simple opponent and then let your playtesters try it and suggest strategies for you to add to the AI.

Note that just because you don't do look-ahead, doesn't mean your AI can't have long-terms goals. They probably should, such as what continents and opponents to concentrate effort towards, especially if the game has a lot of multi-turn movement to gets troops to fronts.