Monday, July 19, 2010

[dyejvfef] Difficult Dodgem positions

Difficult position := (if (exists. forward move) then (exists. forward losing move) else True)

If (difficult position) then local_easiness = #winning / #total moves else local_easiness = 1

Not sure what to do about moves which don't lose but also don't make progress.

Path easiness is built up by dynamic programming.

Path easiness of a computer's move from a losing position = minimum path easiness child node.

Path Easiness of a human's move from a winning position = (local_easiness of this position) * (maximum path easiness among winning children)

Unfortunately, because the game is loopy, this will not work.  Instead, we iterate.  In the first approximation, the move assumed chosen is the shortest win, taking the mean easiness if several equal. I don't know if it'll converge: might have to max local_easiness to (1-epsilon), handled symbolically; avoid moves which don't make progress.

No comments :