6
\$\begingroup\$

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!

\$\endgroup\$
2
  • \$\begingroup\$ This comes from another angle, but is essentially your question. \$\endgroup\$
    – Anko
    Feb 28, 2013 at 10:52
  • \$\begingroup\$ You might want to email the developers of Lux Delux, or see if you can reverse engineer it. They have already done what you wish to accomplish, and may be able to assist you better. sillysoft.net/lux \$\endgroup\$
    – user32059
    Jun 18, 2013 at 10:35

2 Answers 2

6
\$\begingroup\$

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.

\$\endgroup\$
9
  • 2
    \$\begingroup\$ Honestly, I don't think Minimax is suited to Risk because there are too many possible options. Imagine a territory with 50 armies in it. There are a TON of possibilities there. \$\endgroup\$
    – Almo
    Feb 28, 2013 at 2:00
  • 2
    \$\begingroup\$ @Almo Alpha-beta pruning \$\endgroup\$
    – Supericy
    Feb 28, 2013 at 6:21
  • \$\begingroup\$ @Almo There are many states, but most of them are functionally very similar and so easily clumped together, so I think there's a lot of room for optimizing Minimax for the purpose. \$\endgroup\$
    – tex
    Feb 28, 2013 at 8:09
  • 1
    \$\begingroup\$ Does Alpha-beta pruning work so well in a game with a random element? (honest question) There is also the unknown element of which cards the opponent has; I seem to remember that in Risk that if you own the country of a card when turning it in, you get bonus armies there. \$\endgroup\$
    – Almo
    Feb 28, 2013 at 9:36
  • 1
    \$\begingroup\$ Another honest question... will minimax deal well with more than two players? My experience with it is in two player no-luck games. \$\endgroup\$
    – Almo
    Feb 28, 2013 at 10:04
2
\$\begingroup\$

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.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .