How do I go about implementing nine man morris game

Question

How do i go about implementing nine man morris game without doing exhaustive search of all the solution space.

Answer 1

I assume that you meanto code the AI end of the game.

If by searching of the solution space then you mean the number of possible positional variations then I wouldn't bother as I gather that there are about 10^10 variations and 10^50 variations of games.

I would start with coding the basic rules of movement and placement. Keeping track of the lines of 3 pieces.

At first just randomly place pieces and once that is working look at weighting moves/positions according to preference.

Each piece will then have a weighting, the number of blank spaces next to it, whether an ajacent piece is the same colour, whether a line of 3 can be formed with the adjacent piece or not.

Then you'll need to decide whether the AI will second guess what the human players moves may be (by running the same algorithm but for the opposing colour) and if so how many moves ahead it may wish to calculate (I'd say no more than 3).

It's a case of simple rules giving rise to complex behaviour.

Answer 2

Looks like it's a solved game as of 1993.

Answer 3

Because of the huge amount of possible combination I'd suggest to have a look at common strategies that are used to create chess AIs. Key features I'd try:

• opening database
• branch 'n bound search with certain depth limit
• rule database to determine how good or bad a certain board configuration is

With that you'll get a pretty good AI, if your algorithms to measure the current configuration is good.