BoardSpace.net

[AdamS]

I have an AI (for Hex) that has an evaluate function that has a side-effect of giving a good indication of which moves are best.

The simplistic implementation ignores this information as the engine does:

- List_Of_Legal_Moves
- For every possible move

- Make_Move
- Static_Evaluate_Position: call EVALUATE
- UnMake_Move

Instead I'd like to do this

- List_Of_Legal_Moves: call EVALUATE
- For subset of good moves

- Make_Move
- Static_Evaluate_Position - call EVALUATE
- UnMake_Move

Net a lot less calls to EVALUATE as the branching factor of the search tree is reduced from say 100 to 10. But it's a shame because we will EVALUATE many positions twice. Any tips on how to get round this?

I could potentially implement my own mechanism based on a hash of "digest => score" but there is a small risk of collisions plus of course I don't want to reinvent the wheel.

[admin]

What you are proposing to do is narrowing the width of the search,
which is dangerous unless your list of "good" moves is really really
good. Consider yourself warned.

To fit this strategy into the current framework, cache the result
of the static evaluation in the move object. Subclass "Search_Driver
and wrap
public double Static_Evaluate_Move(commonMove mm)
with a check for your precomputed result. Your shortcut
version will need to include the equivalent of this:

double val = r.Static_Evaluate_Position(mm);
mm.local_evaluation = val;
mm.evaluation = val;
mm.gameover = r.Game_Over_P();
mm.depth_limited = r.Depth_Limit(current_depth+1,max_depth);


One final note about this optimization: I predict you will not be able to detect the benefit. You'll be skipping the second evaluation only for the moves that were actually used, and only for the non-terminal nodes. This is a very small percentage of the total nodes. This kind of thinking about the expected benefits of a proposed "optimization" can save you a lot of work and prevent accumulation of unnecessary complexity in your robots.