Thread: Looking for appropriate container

Originally Posted by brewbuck

Why are you calling it minimax then?

Because the algorithm is called minmax, no? Alpha-beta pruning is an optimization.

I have collected some statistics. I do get cutoffs. The number of cutoffs is roughly 4% off the total examined nodes. What does that actually mean, though? I really have no idea. Since I don't count the total nodes when getting a cache hit and I don't know how many nodes are cut off from the alpha-beta, I cannot count how many nodes are actually pruned.

But this ordering... I'm afraid I don't know why it would help or how it works.
It is just my first AI algorithm.

Originally Posted by Elysia

I have collected some statistics. I do get cutoffs. The number of cutoffs is roughly 4% off the total examined nodes. What does that actually mean, though? I really have no idea. Since I don't count the total nodes when getting a cache hit and I don't know how many nodes are cut off from the alpha-beta, I cannot count how many nodes are actually pruned.

Counting the exact number of nodes pruned is really looking at it in too fine detail. Just estimate it. If you know the approximate branching factor B for a given move sequence number you can just take it B^(D-1) to predict how many moves would be evaluated at depth D. So if you make a cutoff at depth D then you saved approximate B^(D-1) evaluations.

But this ordering... I'm afraid I don't know why it would help or how it works.
It is just my first AI algorithm.

The ordering tries to put high-value moves first, so that they will cause earlier cutoffs. As these early cutoffs stack on top of each other at various depths, the effect is to reduce the branching factor from B to approximately sqrt(B) which lets you search twice as deep in the same amount of time. The estimates have to be legitimate, not just random values. That's where the table comes in -- as you are filling in the table you are storing the last-known values of those positions and you can use those to order the moves in a following iteration.