Jump to content
  • Advertisement
mudslinger

Game of The Generals AI

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

Hello.

We have a board game called Game of The Generals. It's played on a 9 x 8 bored and players are free arrange their pieces on the lower three rows according to their strategy. Players are not allowed to see each other's pieces.

http://en.wikipedia....of_the_Generals

Writing an AI for this is difficult since players can't see what the pieces are unlike chess. One of the ideas I thought of was setting probabilities to each enemy piece and adjusting as pieces reveal themselves through the game (e.g. a piece eliminating a lower ranking piece). The good thing about this game is that pieces can only move one square per turn, and should simplify the search tree.

Any tips?

Thanks in advance. Edited by mudslinger

Share this post


Link to post
Share on other sites
Advertisement
Is it a bit like Stratego?

You can create random scenarios that are consistent with the information you have so far. Then consider what would happen after each one of your moves, probably using Monte Carlo playouts (look at how recent computer go programs are implemented).

That's the first approach I would try.

Share this post


Link to post
Share on other sites
Thank you for your reply.

Yes, it is a lot like Stratego but much simpler. All pieces move only once per turn, and all they do is outrank each other.

I'll attempt the method you suggested. But is Minimax advisable?

BTW, I'm implementing the game on C#.

Share this post


Link to post
Share on other sites
Quote: Original post by mudslinger
I'll attempt the method you suggested. But is Minimax advisable?



I wouldn't know how to use minimax in a game with partial information. Edited by IADaveMark

Share this post


Link to post
Share on other sites
Quote: Original post by mudslinger
Can anyone please explain Monte Carlo for me? The ones on the internet aren't doing it for me.



The first thing you need is a "policy". This is a very simple rule that allows you to pick a move on a given situation, with some randomness. It doesn't have to be particularly smart: For many games, picking a purely random move is a good start. You want to make sure that games end in a reasonable number of moves, so perhaps you should make it more likely for pieces to go towards opponent pieces, so they eventually annihilate each other.

Now, given a position on the board (with full knowledge of what's on both sides), you can play the rest of the game using the policy (this is called a "playout" or a "Monte Carlo simulation"). This is a random process, and each player will have a certain probability of winning. The hope is that the probability of winning this random process is a decent evaluation function for the board.

So the first algorithm you can try is this:
For each move M {

Do 10,000 times {

Generate a plausible configuration for the pieces of the opponent.

Play M

Run the rest of the game using the simple policy for both sides

}

Count how often you won

}

Pick the move that won the most.



There are several possible refinements. Of the top of my head:
(1) Use UCB1 to sample more promising moves more often.
(2) Make the policy smarter (always room for improvement here).
(3) Bias the plausible configurations using Bayes's formula on the history of the game (this seems hard).

I would probably implement only (1) and see if the program plays well enough to be fun.

The quality of play will depend on how many simulations you run, which means that speed will likely be important. Perhaps C# is not the best choice for this type of approach, but I wouldn't worry about it for now: Implement it initially in whatever language you are most comfortable with, and you can always rewrite it in C or C++ later if you need the speed. Edited by IADaveMark

Share this post


Link to post
Share on other sites
Quote: Original post by alvaro
(1) Use UCB1 to sample more promising moves more often.



What is UCB1?

EDIT: I just finished writing the game with an AI with fully random moves.

[Edited by - mudslinger on October 23, 2010 5:33:16 AM] Edited by IADaveMark

Share this post


Link to post
Share on other sites
Quote: Original post by mudslinger
Quote: Original post by alvaro
(1) Use UCB1 to sample more promising moves more often.


What is UCB1?



How hard have you tried to find out on your own what it is? Edited by IADaveMark

Share this post


Link to post
Share on other sites
I did find this:
http://eprints.pascal-network.org/archive/00002713/01/nips_exploration_exploitation.pdf

While I was trying to understand it, I hoped someone could give me a simpler explanation.

Will still try to understand it, though.

Share this post


Link to post
Share on other sites

  • 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!