Hello. I would like to know if there is an iterative method of implementing the minimax algorithm. I''ve implemented a recursive minimax algorithm for a game. I''ve been told the game is something similar to go-moku (sp), but far simpler (8x8 board, only 4 in a row, diagonals don''t count). I''ve implemented alpha-beta pruning, history tables, and iterative deepening. I''ve also spent a lot of time fine-tuning my evaluation function, and I''m very happy with it. Now, I''m looking at trying to change it from a recursive algorithm, to an iterative algorithm. I suspect (but don''t really know) that this will provide a good performance boost, maybe allowing me to get another ply. I''ve tried searching for it, but whenever I search for "iterative" and "minimax" i get a lot of links to iterative deepening, which isn''t what I''m looking for. Has anybody here done this before? Is it a whole lot of effort for not much reward? If it is feasible and worthwhile, anyone have any information on it? I tried working on it a little, and it looked like I was going to need to push 2 or 3 variables onto the stack at a time. (I don''t have tons of experience converting recursive problems to iterative problems.) Thanks in advance for any information.

I don''t see why an iterative approach would give you any speed boost at all. You would basically be creating your own stack, as opposed to letting the computer do that work for you. Unless you''re overflowing the stack, or the iterative version will make it easier for you to do further development, I would stick with the recursive version.

Some problems will give you a significant speed boost for using an iterative version instead of a recursive version, but I don''t think this is one of them.

I know of only one chess program that uses an iterative search instead of a recursive one. I certainly don''t know every program, but I know a few dozen that use recursive search, and only one that uses iterative.

The guy that uses an iterative approach said that he did it because he was doing research on making alphabeta work with multiple processors, and the iterative search made it easier for him to do that (I know of plenty people who make alphabeta work on multiple processors using a recursive search though). This guy was trying to make his program work on some super computer though, with like 1024 processors, not just 2 or 4 processors like most people I know.

This might be a question better asked in the General Programming forum though. You might try searching for something more general, like something on converting a recursive function to an iterative one.

Ok, thanks. I have spent some time before on problems like this. I converted a routine that calculated all of the combinations of a given set from recursive to iterative, and it was quite a bit more difficult to do it that way. I''m not using this on any fancy supercomputers (except for maybe a chance at using it on an itanium system), so I guess I''ll stick with a recursive solution, and focus my efforts elsewhere. I thought that since the program jumps between depths frequently, getting rid of the recursion might help. I''m not trying to change the world or anything though, so if popular opinions says recursive, then recursive it is. I''m confident that if it was much more beneficial iteratively, it would be done iteratively. Thanks for the reply.