Turn Based AI Technics

Started by
9 comments, last by alvaro 9 years, 8 months ago

I'd like to come to know some varying technics for programming an AI for a turn based game. I am aware of Min-Max-Trees and Alpha-Beta-Search, but I'd also like others as there might be games that can only hardly benefit from such trees or that are too complex for them. However, I hardly found any ressources in this matter.

I also looked in the pinned topic about AI books and sites, but most of it are focussed on real time applications. Take for example the FSM, which would have to be extremely complex to yield satisfying result in a lot of turn based games.

So can you recommand any ressources or technics for that matter?

Advertisement
The big alternative to minimax search is MCTS (Monte Carlo Tree Search). If you search the web and can't find good information about it, post again and I'll give you some pointers.

This paper goes into Monte Carlo planning a bit:

http://pst.istc.cnr.it/PlanSIG10/proceedings/paper%2011.pdf

These techniques and similar ones are also used for high-dimensional A* pathfinding, for example in robotics where the robot has many degrees of freedom of movement.

That's a nice info. I'll definitely look into MCTS a bit and have found some pretty nice ressources for that.

On another side, I stumbled across Neural Networks during my previous inverstigation, but the general recommandation was not to use them for various reasons such as inefficiency regarding time or difficult understanding of the AI. Then again, this was concerning real time games and I don't have much problems with a black box AI, so do you think it would be worth it to look into that?

I wouldn't waste time with artificial neural networks. The are some recent success stories, but it is unlikely that you have a problem for which ANNs are well suited and, even if you do, it will probably be difficult to implement a decent ANN for your problem without becoming an expert in ANNs first.

I have been looking into the Monte Carlo Tree Search. However, there seems to be a lack of tutorials or more detail than a wiki walkthru. If anyone has more information I would enjoy reading it.

Thank you.

Developer with a bit of Kickstarter and business experience.

YouTube Channel: Hostile Viking Studio
Twitter: @Precursors_Dawn

I recently wrote an AI system for a turn based game called Battle Worlds : Kronos and neither Neural Networks nor building and searching of a game tree in the classical sense had a part in the solution. Neural networks are interesting but hard to control and debug. If the AI behaves in an un-intended way you can't just step into the code and change it because the workings of a NN is opaque even to the developer. Game trees are a nice idea but in their raw form impractical for complex games. Even with chess they hit their limits fast.

My solution builds upon the concept of intelligent agents that use a behavior tree of possible actions. Each unit is controlled by an agent and grouped in squads, squads help units sync their actions. In the scope of one-squad and one-turn it is possible to build a tree of possible actions and search for the optimal path. The strategic behavior of the AI is mostly scripted.

Re neural networks: FFS

Re BTs: most turn-based games are going to have such a complex potential solution space that BTs will break under the weight

You need something that will evaluate your potential actions in a reasonable, yet tunable way... enter utility systems.

Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC
Professional consultant on game AI, mathematical modeling, simulation modeling
Co-founder and 10 year advisor of the GDC AI Summit
Author of the book, Behavioral Mathematics for Game AI
Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play

"Reducing the world to mathematical equations!"


enter utility systems.

Any reading suggestions to get a quick overview how utility based systems differ from behaviour trees with "smart" metric-driven transitions?


enter utility systems.

Any reading suggestions to get a quick overview how utility based systems differ from behaviour trees with "smart" metric-driven transitions?

Someone else tell him, please. It's less awkward that way.

Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC
Professional consultant on game AI, mathematical modeling, simulation modeling
Co-founder and 10 year advisor of the GDC AI Summit
Author of the book, Behavioral Mathematics for Game AI
Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play

"Reducing the world to mathematical equations!"

This topic is closed to new replies.

Advertisement