Hey I'm curios as to what a good number of nodes to seach in an implementation of minimax with alpha-beta pruning and killer huristics is. For instance i search 3 ply's deap (all peieces have been moved around but are still on the board). whats should be the number of nodes seached? I want to see if my implemntation is correctly pruning the leaves. the board can be defined using the epd string: rnb1kbnr/pp3ppp/2ppp3/6qQ/2B1P3/2N5/PPPP1PPP/R1B1K1NR w right now my implemntation is searching through 21000 nodes before it returns. is this number correct? Thanks

Thats a difficult question to answer, since AlphaBeta is heavily dependent on move ordering.

Try searching captures first with the same 3 ply search and you should see a difference. Instead of search the board from left to right (if thats what you're doing) search from right to left and you'll see a difference.

I think a straight minmax search to ply 7 goes through 1.8 billion positions-- I have the exact number at home somewhere.

Will

Yes, the efficiency of the alpha-beta algorithm is very dependent upon the quality of the move ordering. If you have perfect move ordering, then you can search twice as deep as you could with minimax in the same amount of time. Another way of stating this is to say that the alpha-beta search will take the square root of the time that minimax takes. That should be true for counting nodes also (sqrt(minimax) = alphabeta).

So this means that if a minimax search requires N nodes from the position you used, then alpha-beta with perfect move ordering (which you don't have) will only need to search sqrt(N) nodes.

Using your test position, minimax(3) should visit 70584 nodes. Therefore if your move ordering was perfect your alpha-beta search would visit about 266 nodes.

Actually I'm kind of stumped here. IIRC, alpha-beta with random move ordering should search about N^(2/3) nodes as minimax to the same depth, which means that even with random move ordering you should complete this search in about 2000 nodes. However, even strong amateur programs using transposition tables to get extra cutoffs and null move to get cutoffs search over 2000 nodes using your position. That doesn't quite add up, but we've only tested a single position and that's not quite statistically significant [wink]

So at the very least try your experiment on multiple positions (the more the better). It's possible that this specific position isn't ordered well by your move generator. It's also possible that N^(2/3) isn't correct, but I think I am remembering correctly. Try it on a number of positions, and see how well your program does on average.

My guess is that if you try this on a few dozen or a few hundred positions, you will get something closer to N^(2/3) nodes or slightly better since you are using killer heuristic. If not, you may either have very bad default move ordering (maybe you generate king moves first or something like that), or maybe you have a bug.

A transposition table will be the biggest help to your move ordering. Try that first. Then you can try things like killer and history heuristic, sorting "winning captures" using a static exchange evaluator (SEE), internal iterative deepening, and so on.