I am making an engine for a board game similar (in principle) to chess. However there are a few important differences. The board size is 21 x 11. The pieces can take multiple steps horizontally, vertically or diagonally. A player can move upto 3 pieces simultaneously in one turn. Both players have 7 pieces each and no piece can ever be captured. So on an average there are a lot of possible moves a player can make in his turn - well over 100000. Even with the best pruning techniques that i can think of, game trees wont work here. How should i solve this problem?

What is your question?
...
How to move your pieces?

My question is how should the computer decide which move to play? More specifically, what alternatives are available to game trees?

Although with a game really different, I think I have the same kind of issue.

I would try an analysis on the current board, to found the weak and strong places on the board, and decide where to put the AI efforts.
Something like 'this region needs strong attack, need more pieces'.
This give an all over strategic direction...

Also try to find the relevant cases from this analysis. On such a big board, most of the cases are of no interest. Only consider the interesting ones.

With all this, you can try to make your decision, or even construct a really smaller tree.


Note that I'm aware that this is only theory, and in practice, it is no that easy to do...


Hope it helps,

Emmanuel

The first thing I would try is depth 1 search. Concentrate on getting a strong evaluation function that will play reasonably well even with such minimal search. For games like backgammon, this is enough to get very strong play.

Once you have done that, you might be able to pick which moves to extend further. There is an elegant way to do this that involves making a probability model based on scores. Something like: The probability of move m being chosen is proportional to exp(K*score[m]), where K is a constant (divide by the sum of all such expressions to get the probability). Then you explore branches of the tree that have probability larger than some threshold. The success of this method depends on the nature of your game (are there only a few good moves in each position?).

With that much freedom, maybe it's just a matter of keeping a number of preset formations. Choose one and create pathways towards it while pattern-matching for partial formations of the player in order to block them?

Thanks everyone for replying.

Two more questions:
1>.alvaro, why is K required? For 'n' nodes, why not just expand nodes with a probability of more than, say, 0.9, where
Probability of node 'm' being expanded = score[m]/(score[0]+score[1]...+score[n])

2>.novaflex, can u tell me how ur idea might be implemented?

Quote:

Original post by pacman2003 1>.alvaro, why is K required? For 'n' nodes, why not just expand nodes with a probability of more than, say, 0.9, where Probability of node 'm' being expanded = score[m]/(score[0]+score[1]...+score[n])

Let's think chess. score[m] is typically a number like +2.0 if I am up two pawns, or -3.2 if I am down a knight. The straight-forward formula that you posted won't do the right thing if negative scores are possible. Hence the exp(), which will make all the scores positive. The move with the highest score is the most likely, but how much more likely than the other moves should it be? The parameter K can be adjusted, so if K is a huge number, the highest score will have probability very close to 1, and if K is 0, all moves will have the same probability. The best value of K is probably somewhere in between. Also note that if you didn't have K (or you fix it to 1.0), your probability estimation will be different if you represent scores in pawns or in centi-panws. K can be used to absorb such a change of units.

A more theoretically-sound argument that makes that exp(K*score) a natural choice is that it is an extension of the logistic regression to a situation where more than two outcomes are possible.

If you only expand nodes with probability more than 0.9, you will only expand one node (the root) most of the time. The probability of a node is the product of the probabilities of all the moves that lead to it from the root. If you want to recover the more familiar notion of "depth" as a quantity that is additive, and not multiplicative, you can take base-2 logs of the probabilities, which gives the result in bits(see wikipedia for an explanation). Bit seems to me like a more natural unit of depth than ply.

Quote:

Original post by pacman2003 2>.novaflex, can u tell me how ur idea might be implemented?

You can start by thinking of powerful formations, then manually edit them into arrays. Another approach is to implement a brute-force algorithm that finds powerful formations (the details of this are impossible without more information on the rules/objective of the game). The result of this run would be a file of best patterns to form or block during the game.

The formations could be simple 2d arrays placed in whatever sorted data structure works best for you, perhaps hash table.

Once you have that, you can compare enemy to formations by taking the pieces with min x and min y values and offset them to map to an array in the same format as the formation data. For fuzzier matching you could see which formations rows/columns/diagonals match some of the enemies rows/columns/diagonals, like a substring match or something.

Does that help any?

Could you explain the goal of the game. Are there multiple values of terminal results? Have you worked out any strategies yourself? If not, you should prob. try different ones yourself first.
Against amateurs which aren't deeply rooted in the game, the heuristics is generally enough so Alvaro's suggestion sounds very good. If you could construct an evaulation function with few stationary points or (few local maxima where these are roughly equivalent), any hill-climbing method would work great.
If the heuristics are tricky, you could also generate these automatically. There are very simple methods for this that could very well suffice.