search

SanchoGGP / ggp-base

The General Game Playing Base Package
8 stars 4 forks source link

Failure to detect goal latch in trap.gdl #192

Open arr28 opened 9 years ago

arr28 commented 9 years ago

Not surprised that we don't detect that lost is a goal "latch" because it isn't a true goal latch. At least, it isn't a constant goal latch because the goal depends on both lost and must-match. (Assuming we're playing player then, if player has must-match then lost is a 0 goal latch. If opponent has must-match then lost is a 100 goal latch. And vice-versa if we're playing opponent.)

This is another example of conditional latching that I was talking about in our chat this evening.

SteveDraper commented 9 years ago

Yes, but both must-match and lost are latches.

Doesn't it follow that if A and B are latches then (A AND B) must be a latch? This could be a trivial-case extension...?

arr28 commented 9 years ago

In this case, neither A nor B are goal latches on their own. Testing all possible sets of non-goal latches to see if they form a combined goal latch is exponential in the number of non-goal latches. That's fine in this game, because there are very few of them. However, in any of the board-filling games (e.g. Hex, C4) there are an excessive number of non-goal latches. Even TTT would cause us to do 2^18 work.

However, perhaps in games where the number of non-goal latches is very small, I could try combining them.

But maybe this should wait for conditional latches. When we expanded a state that set a must-match, we'd identify lost as the appropriate goal latch for all sub-states.

SteveDraper commented 9 years ago

No need to test all combinations surely. You can apply propagation rules to propagate latch implications through the propnet (I think?).

If P = A AND B, and A and B are both positive latches (or both negative latches in fact), then so is P. Also works for OR.

Consequently any component in the propnet whos inputs are all latches must also be a latch (NOTs in the propagation path might be a problem...not sure).

In this case Goal = must_match AND lost. Since both must_match and lost are latches it follows directly (without testing any combinations in a search, but from propagation through the propnet) that the goal value is also latched.