From the player''s point of view, I don''t like timers at all. If I play on the "hard" level, give me hard. If I play on easy, give me easy. I don''t want "easy" to search 4 more depth levels just because I play on an Athlon 1600+, nor hard to be too easy just because I play on a P233.

That being said, a timer friendly algorithm probably needs to store the search tree in memory and be able to add single nodes to that tree and update the rest of the tree after adding that node. Proof number search is an example of such algorithm. It assumes the game tree is and AND/OR tree (each node can be true or false - true for a win, false for a loss for the AI player). If a node represents a game state where the computer AI plays, it is an OR node, if its oponent plays its an AND node (minmax style). Each inner node in a partially calculated game tree needs a minimal number of leaf nodes proved true to prove it true and a minimal number of leaf nodes disproved to disprove it. Turns out that at all times there is at least one leaf node that is in both of these sets. Expanding that node will have the highest likelihood of solving the tree. For more, search for the paper by Victor Allis.

But I''d much rather prefer an algorithm that performs the same on all computers. Iterative deepening minmax is a good and simple enough choice. You start with a very shallow minmax run (1 ply or so). You then keep calling the minmax with larger depths (increase the depth with 1 at each iteration). You can limit your algorithm when a minmax run has expanded a certain number of nodes (this gives the advantage that you can search deeper at times) or using a timer (bleh). Given the exponential time needed by minmax, you won''t waste too much time with the unused shallow searches (probably around 25% give or take). And if you use transposition tables (storing the values of the positions you have calculated in a hash table), you can use these values calculated by a shallow iteration to improve the alpha beta optimisation by better move ordering at the next iteration.

That or you _can_ use fixed depth. Trouble is often the time needed for a fixed depth algorithm can vary a lot. My former go-moku program could search ten thousand position or five millions for the same depth without blinking. I assume a the number of moves needed for a Connect 4 game is a lot more stable though given the limited moves at each step.