Jump to content

  • Log In with Google      Sign In   
  • Create Account

We're offering banner ads on our site from just $5!

1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


Turn Based AI Technics


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
10 replies to this topic

#1 Robot334   Members   -  Reputation: 104

Like
0Likes
Like

Posted 05 July 2014 - 11:35 AM

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?


Edited by Robot334, 05 July 2014 - 11:35 AM.


Sponsor:

#2 Álvaro   Crossbones+   -  Reputation: 13692

Like
2Likes
Like

Posted 05 July 2014 - 05:47 PM

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.

#3 jefferytitan   Crossbones+   -  Reputation: 2225

Like
3Likes
Like

Posted 05 July 2014 - 08:08 PM

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.



#4 Robot334   Members   -  Reputation: 104

Like
0Likes
Like

Posted 06 July 2014 - 02:57 PM

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?



#5 Álvaro   Crossbones+   -  Reputation: 13692

Like
4Likes
Like

Posted 06 July 2014 - 04:27 PM

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.

#6 Navyman   Crossbones+   -  Reputation: 4049

Like
0Likes
Like

Posted 30 July 2014 - 04:14 AM

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.

34410.png

#7 Lithander   Members   -  Reputation: 245

Like
0Likes
Like

Posted 30 July 2014 - 04:39 AM

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.



#8 IADaveMark   Moderators   -  Reputation: 2513

Like
2Likes
Like

Posted 30 July 2014 - 11:31 PM

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-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
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!"

#9 Lithander   Members   -  Reputation: 245

Like
0Likes
Like

Posted 05 August 2014 - 08:51 AM


enter utility systems.

 

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


Edited by Lithander, 05 August 2014 - 08:57 AM.


#10 IADaveMark   Moderators   -  Reputation: 2513

Like
1Likes
Like

Posted 06 August 2014 - 03:15 PM

 


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-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
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!"

#11 Álvaro   Crossbones+   -  Reputation: 13692

Like
3Likes
Like

Posted 06 August 2014 - 03:25 PM

Dave wrote a book that covers precisely that type of thing.

Or you can just take the basic idea (write a function that returns how happy you are with an action (the "expected utility" of the action) and then pick the action with the highest value) and experiment with it. Chances are you'll discover everything that's in the book by yourself. But still, Dave is a nice guy and you should buy his book. smile.png




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS