Hi all,

Currently what I'm doing if I want the AI to make a second move while on the same turn is:

            if (board.sameTurn)
                val = negamax(board, depth, alpha, beta);
            else
                val = -negamax(board, depth - 1, -beta, -alpha);

However, if I plan to move to Negascout, PVS, etc it gets more tricky and I'll end up having lots of 'if' conditions in the search. So is there a better way for the AI to handle a second move on the same turn outside of the search?

Thanks

If a turn consists of several moves, I would redefine "move" to mean the whole set of actions you take in one turn. Can you describe a bit the game you are working on?

It's a nine men morris game.

What I'm doing is that I have a game state (place, move, remove). When a remove is to be done on the same turn as place or move, I set the game state accordingly but I do not switch players.

However I can suspect that this is a problem because the search will then try to get the best moves for min when it should get them for max again.

I am not very familiar with nine men morris, but I think this can be treated like multiple jumps in checkers. As I said before, you can treat everything that happens in a turn as a move. Your move-generation function can be implemented using recursion.

EDIT: You don't need to make the move generation recursive (I thought you were saying that you could go again after removing an opponent's piece). So instead of setting the game state, make the move representation indicate the piece to be removed and do the whole operation in one bout.

Hmmm I should consider that solution. I will need to add a property to the move so that it can hold the piece that can be removed. Also, when generating the first set of moves, I will need to determine if a move results in a remove, and if yes, get the pieces that can be removed.

For the purposes of Nine men morris I would make the 'move' include all actions as a single unit, for simplicity so that you can continue using negamax. If you intend to use your search engine for other types of games where it becomes necessary to break moves into different steps (e.g. Arimaa) then I suggest abandoning negamax and implementing a more generic search. Negamax is a coding optimisation which works for 2-player single step move type games. Once you breach that realm you can't really use negamax as you have broken its assumptions about the type of search that is being performed.

If I implement move & remove as a single move unit, I could have for example 9x9 moves that I need to generate. Has this performance issues instead of first generating 9 moves, make the move, and then generate another 9 moves for the remove?

If I implement move & remove as a single move unit, I could have for example 9x9 moves that I need to generate. Has this performance issues instead of first generating 9 moves, make the move, and then generate another 9 moves for the remove?

9x9 moves? Can you have that many mill-completing moves available? Since you are worrying about performance, you should primarily be concerned with the average performance of the program in positions where the game hasn't been decided yet. So I expect you typically will have very few mill-completing moves and the actual list of moves will be short.

If generating a lot of useless moves (because a beta cut-off will prove them useless) becomes an issue, you could use an object that generates the moves in stages, using a pattern that old geese like me call a "co-routine". That way your code just asks for a next move from the object, and the object can internally only generate the removals as they are needed. But it's almost certainly not worth the effort in this case.

If you are worried about performance, the alpha-beta algorithm performs much much better if you are clever about how you sort the moves. Having all the moves available in a list will allow you more flexibility as to the types of heuristics you can use for move ordering, so that's another argument for generating the complete list.

9x9 is a little exagerated because even if both players have all their pieces on the board, most would have already formed mills and they can't be removed. So I'm sure the list will be much shorted.

Would using bitboards speed up the search and/or move generation? How would I set up a bitboard for such a board? Currently I keep an array of 24 items that represent a node on the board.