Hi all,

I use minimax for my Ai in board games and, although not 100% perfect, works fine. Two areas that need improvement are the building of moves and the scoring function.

Both areas are specific to the game itself and its rules. However, I have a question regarding the building of moves.

When it's the AI's turn, I build a list of possible moves that I need feed to minimax. In building this list, I use a sorting/prioritization system, ie. first I list I think are the really best moves, then proceed will less important moves. I don't eleminates. That's the minimax's task.

My question is... When building this list and I already found a move in the 'high priority' part, should I add it again to the list if I find that move in 'medium' priority' part? In other words, should a move only be listed once in the list?

Regards,
Ivan

Ideally yes, a move should only be listed once. If you have duplicated moves, they will just make you waste time revisiting them. If you have transposition tables, the damage will probably be very limited.

It sounds like you having different sorting criteria for your moves. Am I right?

There are a few different ways of dealing with this. Is there a reason you're binning the moves in to 'high' and 'medium' priority?

1. Sort the list once for each criteria. The order of your sorts should be ascending in importance.
i.e. if captures are the most important thing to look at, and 'king safety' is the least, sort by king safety first, then sort by captures last.

2. Move the start index of your sort ahead.
i.e. If a move is a killer move, make it index 0 in the move list. Then sort everything starting from index 1 on (so killer always stays at the top).

3. Keep a sort score for each move then sort based on the sort score.
i.e. if IsCapture()==true moveList.sortScore += 10; if IsKingSafty()==true moveList.sortScore += 4; if IsKillerMove()==true moveList.sortScore += 9999;

I prefer #3 mixed with a bit of #2. :)

Yes I have different sorting criteria but I'm not doing any particular sorting. What I do is, for example, I want to move a piece:

1. Loop through all board positions. If this piece can move and it can make a capture, add the move.

2. Loop through all board positions. If this piece can move and move doesn't exist, add the move.

I then pass this list to my minimax function and it does all the work using my scoring function which applies a very rudimentary (for now) material balance. The minimax doesn't do any sorting either.

Well, captures and non-captures are separate classes of moves, so that particular example shouldn't result in any duplicate moves.

I see. The minimax function itself doesn't make a distinction between different kinds of moves. It's all in the hands of the evaluation function.

btw... I'm writing a simple abstract strategy game using C# and XNA. If anyone is interested in testing what I have achieved so far (very basic stuff for now), let me know and I'll make a copy available for you to download!