Hi everybody, I am working on a AI for a Board game called ZERTZ. On every turn the player places a marble with one of 3 colors on one of about 36 fields. He than removes one of ~16 rings. Makes a Branching Factor of ~1700. But there are turns when a player has to do a jump, for this turns the branching factor is somehwere between 2 and maybe 7. These are the intersting turns and that is why I look deeper into the search tree if those occure. So far so good ... My AI can beat a beginner. I used the following performanve boost strategies: -AlphaBeta Cutoff -Principal variation search -Iterative deepening -Transposition table (with a overwrite if deeper policy) Of course, I know, I have to look more into the game and detect moves, that do not make sence. My question: Is there some general Idea/performance boost strategy for this kind if games? On what would you guys focus the make the AI smarter? Thanks for any Ideas! Nathan

I would try to get a very very good evaluation function.

Use it up to about half-way down the tree, and use a much faster one after it.
You use the good eval to sort the nodes (according to type, like captures first, and according to how good it is. I'm not sure on how good the first will be for you).

With good sorting alphabeta should let your speed shoot through the roof. But only up to a point.

No offence, but minimax (w/ all the rest) doesn't seem to be the best for this (branching factor of 1700!(
I'll look at the game, and see what extras i can find.

From,
NIce coder

"No offence, but minimax (w/ all the rest) doesn't seem to be the best for this"
I know, the search depth does not get depth enough so that alpha-beta can do much. Are there alternatives???

LonelyStar,
give MTD(f) a try, probably faster than PVS.

Sorting moves is essential, and prunning 'probably ilogical' moves could reduce drastically your branching factor (but 1700! ufff it's a lot :( ).

Store best move on your Transposition Table, this should be tried first and previous moves at the same level skipped.

Hope it helps

Anonymous Poster:
I like to look into those strategies you suggested. But I was unable to find information about them using google (except neural nets of course). Can you point me a little in the right direction where I can find information about those "ideas"?!?
Also: Are there an other Board-Game "algorithems" I should look into?
Thanks a lot!
Nathan

Zerts, rules and all the rest for those who haven't played the game (like me).

Stratagy

With pattern matching, you set up a set of patterns, of size x. (x can be different per pattern).

In each pattern, you set it up, so that each square (in the pattern) could be:
Anything
One of a subset of things
Or only one thing.

Now, for the last two, you define an inportance or a weighting for it being one of those.

Once you have evalueated the pattern, in respect to the board (the pattern could be in many spots on the board, so you'll have to check them all), you go and you get the patterns weighting.

You then divide that by the boards maximum weighting (which can be precomputed and turned into a multiplication, which is a lot faster).

The result is a number from 0 to 1, which dictates how close the pattern is to fully matched.

You also store a subset of moves, each with its own weighting. Those are relitive moves, from the center of the pattern. For eg. +4,-25. (so that the pattern can be used anywhere and the moves will follow).

Once you've got them, you get the legal moves, and you increase their weighting by the Matchcoefficint (which is from 0 to 1) and the moves weighting.

Eventually you end up with a list of possible moves, each of which have a "goodness" value from the pattern matching.

You can pick the one with the heighest goodness value.

There are other ways to do this, and you can use a multitude of tequneques to find the best move.

From,
Nice coder

Theres another way, it involves an influence map.

Look here

What you should do, is find the number of positions, and use that to figure out what to do:
ie. When there are too many positions, use the influence map with pattern matching.
When there is enough, then you do a limited depth search, with the depth going up as the number of posiotions goes down.
once there are few enough positions then go and do a minimax search and play perfectly.

From,
Nice coder

[Edited by - Nice Coder on January 29, 2005 9:31:51 PM]