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.

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.

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#.

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

Can anyone please explain Monte Carlo for me? The ones on the internet aren't doing it for me.

Thanks.

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.

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]

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

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.