Jump to content
  • Advertisement
Sign in to follow this  
comfy chair

GOAP vs. MCTS

This topic is 1444 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I am about to start working on the planning layer of my simulation game. Originally I thought I was going to use a GOAP design. I believe I understand this approach fairly well. But now that MCTS is becoming more popular, I am wondering if I should look into it more... 

Here is my original thread that describes my thoughts on using GOAP to design this part of my game:

 

http://www.gamedev.net/topic/652272-goap-and-modeling-world-state/

Do you think MCTS is a valid design choice? The game also has a complex crafting/production layer that I did not mention in the post.

I wonder which would require the least work? Both right now and after the game gets expanded with more and more features...

Share this post


Link to post
Share on other sites
Advertisement

Ok. But perhaps we can get into a bit more detail about how the methods differ.

It seems to me that both methods demand a simplified representation of the game space, with actions and estimated state changes from actions.
In the orginal thread I describe how I would represent the game for GOAP. Perhaps this work would be the same for MCTS also?

Also, GOAP requires an end state to search towards, as well as a heuristic function to guide the search.
MCTS does not require an end state, but it does need an evaluator function... how similar would these functions be?

GOAP will only do a single search to formulate a plan. MCTS will do many simulated playthroughs.
If there are no random factors in the simplified representation (for instance if the result of a battle is represented as deterministic), then MCTS and GOAP would look very similar...
 

Share this post


Link to post
Share on other sites


GOAP will only do a single search to formulate a plan. MCTS will do many simulated playthroughs.
If there are no random factors in the simplified representation (for instance if the result of a battle is represented as deterministic), then MCTS and GOAP would look very similar...

 

No, MCTS and GOAP wouldn't look similar at all. MCTS can simultaneously optimize your decisions and the decisions of other agents, so if some plan is easy to stop by an opponent, it will pick a different course of action. For instance, you can use MCTS to play a board game like tic-tac-toe (or go, it doesn't have to be a trivial game), but I don't think GOAP is a reasonable way to go about it. GOAP assumes the agent does things that change the state of the world, but it's not very good at modelling ways in which the world might react to the actions of the agent.

Share this post


Link to post
Share on other sites

No, MCTS and GOAP wouldn't look similar at all. MCTS can simultaneously optimize your decisions and the decisions of other agents, so if some plan is easy to stop by an opponent, it will pick a different course of action. For instance, you can use MCTS to play a board game like tic-tac-toe (or go, it doesn't have to be a trivial game), but I don't think GOAP is a reasonable way to go about it. GOAP assumes the agent does things that change the state of the world, but it's not very good at modelling ways in which the world might react to the actions of the agent.

 

So GOAP is perhaps more suited for games without an antagonistic opponent. Like a simulated world where many agents are trying to make a living in the environment but not really interfering with each other. Then MCTS would be better for traditional RTS or war games...

Share this post


Link to post
Share on other sites

 

No, MCTS and GOAP wouldn't look similar at all. MCTS can simultaneously optimize your decisions and the decisions of other agents, so if some plan is easy to stop by an opponent, it will pick a different course of action. For instance, you can use MCTS to play a board game like tic-tac-toe (or go, it doesn't have to be a trivial game), but I don't think GOAP is a reasonable way to go about it. GOAP assumes the agent does things that change the state of the world, but it's not very good at modelling ways in which the world might react to the actions of the agent.

 

So GOAP is perhaps more suited for games without an antagonistic opponent. Like a simulated world where many agents are trying to make a living in the environment but not really interfering with each other. Then MCTS would be better for traditional RTS or war games...

 

for opponent based problems In either system you would have to evaluate the potential actions of opponents (the preconditions for sub goals doing situation analysis).

 

In a game with rich/complex mechanics with limited viable solution sets,  I wonder about a Monte Carlo mechanism that semi-randomly jumps into a candidate solution (and then does some SWARM sampling around it to incrementally optimize the choice).   Too much chance of missing a corner logic containing the far-better solution option.    If that aspect is to be handled at a higher level then THAT is the fundamental methodology and the MCTS becomes  just a tool to optimize applicable sub goal evaluations (ie- sampling spots on an influence map where much of the complexity has been generalized out of the data)

Share this post


Link to post
Share on other sites

Besides handling randomness more easily than just about any other method, MCTS can also [not so easily] handle uncertainty in the current state of the world. So if your agent is chasing the player and he disappears behind a corner, you can use something like a particle filter to represent your guess for where the player is, and use the particles as starting configurations for your Monte Carlo simulations. If done right, I think this can create very interesting searching behaviors that would be fun to try to defeat.

Share this post


Link to post
Share on other sites

Comy chair,

I would like to hear more of your game, a thorough description - it sounds pretty interesting and seems to be something similiar to what I am also interested in.  If you are not comfortable in public, feel free to email/message me.

 

Michael

Share this post


Link to post
Share on other sites

One of those 'things usually left out' is how much the games complexity requires the situational information to be processed and boiled down into the symbolic form to have these methods applied - to be cached (and constantly patched in a dynamic situation) or regenerated on-demand(where early pruninig helps).

 

The more complex and interrelated the game state is (possibly with temporal issues where a trend pattern is an indicator) and with uncertainty ontop of that (imperfect info, as well as independantly acting entities)  the more work (processing resource) that evaluation becomes.   

 

Which of  GOAP/MCTS can do the most EARLY exclusion to narrow down the situational space being considered and evaluated would indicate its utility.   Boiling down all the factors to be easily compared (in prioritizing and picking candidate solutions) can be the very hard part.   Spatial  positionality on a map itself might seem an easy shortcutted data set, but consider evaluating the patterns in GO  - the analysis for even such a simple 'terrain' and entity mechanics explodes in the processing required to evaluate the actual situations.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!