Next: Improving Game Playing Up: Games and AI Previous: Improving Game Playing

The Horizon Effect

Since the lookahead tree is of fixed size - say N, what happens if we increase the depth by one (to N+1)?

The negative horizon effect - MAX may try to avoid a bad situation which is actually inevitable. For example, MAX tries to avoid losing the white queen and appears to be able to do so using a lookahead tree of depth 6 but a little deeper it becomes obvious that the queen is going to be lost.

The positive horizon effect - MAX may not realise that something good is going to be achievable. For example, MAX would like to take MIN's queen and that can happen - but the restricted horizon prevents MAX from making the right choices to realise this possibility.

The remedies are only partial. First, use a more flexible lookahead tree. Rather than chopping off everything below a certain level, be more responsive to what is happening at the terminal nodes. If one features a lot of ``interest'' (however that is assessed) then expand the tree a little until the leaf states are ``quiet''.

Also introduce a stronger sense of strategy - don't just play individually good moves.


paulb@comp.lancs.ac.uk
Tue Jan 9 10:51:07 GMT 1996