Jump to content
  • Advertisement
Sign in to follow this  
Strid

Turn-based boardgame AI (need help on improvements)

This topic is 2950 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

hey guys, i've recently developed an advergame based in a boardgame, its a 4-player (1 player + 3 bots) race game in which players collect flags from each others bases (their start points), then run to the final base.


heres the game's site:

http://www.nestle.com.br/portalnestle/passatempo/Busca/Default.aspx

all games are created by users, you can join any of them clicking the blue button "Jogar" (its brazilian portuguese btw :)




Its all fine pathfinding-wise, but the game has a mechanic in which paths can destructed and reconstructed through the rotation of the discs in which they belong to.

I'm trying to make these bots look wiser when rotating these discs and choosing their cards (there are 2 game modes, a dice mode(random) and a cards mode(strategic))

Its the first time i make a game this big, and i have not much experience with AI, I have had some problems with to processing time and redesigned my code so it could run asynchronously, its working, but i feel it could just be much better...

i think the biggest problem is that a decision in a game like this should take in account multiple turns ahead (i'm only checking the current turn), and the info i'm currently taking into account when making a decision for rotating a disc is:

-player's "own paths" scrambled through that rotation
-player's "own paths" built through that rotation
-opponents' paths built/scrambled through the rotation


I tried creating a utility system (inspired by "Behavioral Mathematics for Game AI")

the utility of building/scrambling a path can be different, paths with distance shorter or equal to X are worth more points than paths with length bigger than X

at the start of every turn, every bot does also have an "objective", that is the closest flag, building/scrambling a path to his own objective has an even bigger utility modifier

i think the AI currently can do very good in many maps, but in some of them (which getting to the flags requires many rotations) they can spend some time wandering around trying to find out how to get to their objectives...


I'm totally open for suggestions on improving the AI, i have researched a lot but haven't found many materials for situations like this...


Thanks

Share this post


Link to post
Share on other sites
Advertisement
I tried playing the game. I am impressed at how polished the interface looks. However, I spent most of my time waiting around for dice to be rolled, and that wasn't much fun. I saw all the help could be eliminated once I understood what was going on, but I think it would be good to have a method to play with even less wait.

I think for a game like this a good evaluation function is all you need. You basically need to estimate the probability of winning the game given a position. You can define several factors that indicate who is ahead and use logistic regression on games to create a probability model. You can learn a lot by looking at how strong backgammon programs work.

Alternatively, you could try to do some sort of tree search, but this is extremely hard to do for games involving more than two players.

Perhaps it's worth looking into MCTS, which is the technique that all the top go programs use. It allows for randomness and it shouldn't be too hard to adapt to multiple players.

Share this post


Link to post
Share on other sites
Quote:
Original post by alvaro
I tried playing the game. I am impressed at how polished the interface looks. However, I spent most of my time waiting around for dice to be rolled, and that wasn't much fun. I saw all the help could be eliminated once I understood what was going on, but I think it would be good to have a method to play with even less wait.


i do agree you, but the is designer for kids 7-12 years, so people get overpreocupied in making the game understandable and non-punitive for input errors, thats why so many alerts confirming your moves, the "sem alerta" (no alerts) button helps a bit


Quote:
Original post by alvaro

I think for a game like this a good evaluation function is all you need. You basically need to estimate the probability of winning the game given a position. You can define several factors that indicate who is ahead and use logistic regression on games to create a probability model. You can learn a lot by looking at how strong backgammon programs work.

Alternatively, you could try to do some sort of tree search, but this is extremely hard to do for games involving more than two players.

Perhaps it's worth looking into MCTS, which is the technique that all the top go programs use. It allows for randomness and it shouldn't be too hard to adapt to multiple players.



there are 2 things which i have problem with



1- getting the information requires too many pathfinding calls, need to update when checking for every rotation option. When it comes to a flash game, it gets very processor expensive. Since actionscript is a single-threaded language, i have to write code which can run async (still getting used to that)

2- too many things to look at when choosing your card (when playing strategic mode) or searching/deciding for possible move sequences (move->rotate or rotate->move), it's hard to evaluate all this information


I have no experience in AI programming, it's the first time i build a game this big and had only a few days for putting some AI together, i will check how AI works in backgammon and other games, maybe i can apply a thing or other.

Will also take a look at Monte Carlo Tree Search, found a few pdfs on google, can you recommend me any specific resource?


Thanks!

[Edited by - Strid on August 22, 2010 4:36:02 PM]

Share this post


Link to post
Share on other sites
I first learned about MCTS by reading this paper on MoGo's search. The specific algorithm they use is called UCT, and something similar to that is at the core of many go programs. But the basic algorithm has gone through so many refinements that the name wasn't very correct anymore, so the computer-go community coined the new term MCTS.

Unfortunately I don't have any good references for backgammon programming. If you end up finding something that you particularly like, please post a link here.

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!