Algorithm for memory depth for finite state machine players

[marcharper]

We need one!

[drvinceknight]

👍

[drvinceknight]

See for context: #591 (comment)

[drvinceknight]

At the moment a generic FSM strategy has default memory 1, I think the number of states in the underlying FSM is a better estimate (until we obtain a better algorithm).

[gaffney2010]

I've been giving this some thought, and I think I have an approach to analyze a FSM for memory depth. [Would work for other games too.] I describe my idea below. If it seems good, I could code it up.

My idea:

The memory is the length of memory needed to determine which state we're in. The algorithm I'm thinking about will take each state and walk backward along the edges that are coming into that state. The edges each of one of four types (C in reponse to C, C resp to D, D resp to C, and D resp to D). For a given edge type, if there is one or fewer states with that edge type incoming, then we could determine the state if we're given that history. If there are two or more, then one edge worth of history is not enough, and we similarly walk backwards from each of the state we ended on. For example if states 1 and 4 both have incoming C/C edges coming from states 5 and 3 (resp), then we can look at all the incoming edges on states 5 and 3. If 5 only has incoming C/C and C/D edges and 3 only has incoming D/C and D/D edges, then we only two edge's worth of history would be enough to distinguish. If on the other hand, they both had an incoming D/C edge, then we'd have to continue to trace those edges back. [I call this breaking a tie.] Otherwise we would have to repeat until we've broken all the ties. When this terminates, we'd know how much history would be needed to be guaranteed to be determine the state.

We'd start this algortihm by listing all incoming edges for each state. Then the time it'd take for for each step back would be O(E). If we went back 4E steps (maybe too many), then we'd know that infinite memory is needed, because by then we'd certainly have entered a looping pattern.

[There's an off-by-one issue because knowing that an edge is of type C/C requires 2-turn history because it requires knowing that the opponent cooperated two turns ago. When our algorithm ends (i.e. the last ties is broken), we need to check if we could have broken the tie with only the knowledge of what the player did in response. That is, is knowing that the edge is of type */C enough inforamtion?]

[marcharper]

Would it handle a case where the first move fragments the graph into two subgraphs, both of which cannot be escaped? In that case the memory depth would be infinite, and there's a cycle as you described. However if the entire graph was just a cycle that goes through CCD regardless of the opponents action, then the memory depth is at most three (maybe two?) so we can't conclude a cycle implies infinite depth. (Maybe the cycles described above are not quite the same thing.)

Regardless, if you think you have an algorithm that works, and can show it works for various cases, then we can merge it into the library. Even if it's a bit slow that's probably fine since we can just run it at test time, and at runtime only if the FSM changes.

I haven't searched through the literature for such an algorithm -- one may exist. And if not, such an algorithm is potentially publishable.

[gaffney2010]

I think that the algorithm can handle these cases.

Let's look at the second example, a CCD cycle. Let's say that the states are 1, 2, 3.

1 --C--> 2 --C--> 3 --D--> 1

My algorithm starts building these trees of incoming edges for each node. [In this example, the trees are straight lines.]:

1: D
2: C
3: C

Because 2 and 3 are "tied," we have to keep going.

1: D
2: C, D
3: C, C

There are no more ties. The tallest tree is 2, so the length of memory is 2. Because with a history of two I can distinguish between these trees and decide which node I'm on.

Above when I talk about a cycle, I mean that I would have to keep building these trees forever, because I would fall into one of these cycles still without breaking a tie. If had to go one more back on these trees and I still hadn't broken the tie, it'd be hopeless because both 2 and 3 would be looping at that point. I guess you can restate this as: A graph has infinite memory if and only if there exists an identical cycle in two different places on the graph. I think I can prove this formally.

As for your other example: I don't think that implies infinite memory. Let's say that use the same example, but we have a new state 0 that goes to state 1 if C (and Cs in response), and otherwise goes to state 4 (and Ds in response), which there forever Ds. Now I repeat the algorithm.

0: (empty)
1: D
2: C
3: C
4: D

So we keep going

0: (empty)
1: D, C
2: C, D
3: C, C
4: D, D

With just the last two moves, I could determine which state I'm in.

I'll code up my algorithm, and make sure I have these as tests, with others.

[marcharper]

SG and thanks for the explanation.

[gaffney2010]

I've been thinking about this more, and thinking about how we could prove it.

It occurs to me that it's somewhat trivial if the FSM has a finite memory. Say that our algorithm says that the memory is x. We know that we can always figure out the state if we have x memory, because the algorithm produces a set of rules for determining. [In the example above, we know that given D, C, we know we're in state 1. C, D then state 2. Etc.] So the memory must be at most x. If on the other hand, somebody said that the memory was less than x, then the algorithm produces counterexamples on all the previous steps. [In the example above, if somebody claimed the memory was 1, I could say, what if the memory is C? Then you wouldn't know if you were in state 2 or 3.]

On the other hand, the infinite case is challenging. More than I had previously thought. I'm able to prove that we could conclude infinite memory after running the algorithm for E(E-1) steps, but I suspect that this is not an efficient upper bound. The proof of this follows:

Suppose that we did have infinite memory, then that would mean that no amount of memory would distinguish two states. The two states must be in cycles, for otherwise, the start would be guaranteed to be at a fixed finite point in the memory. Say that these cycles are made up of m and n edges. [m, n <= E] Call L = lcm(m, n) = sm = tn, and the type of the i-th edge tracing backwards from the two states x_i and y_j. From our naming it follows that x_i=x_{am+i} for any integer a and y_j=y_{bn+j} for any integer b. Now suppose that it's found that x_i=y_i for all 0<i<=L, then we could conclude that x_k=y_k for all k, because k can be written as qL+r for 0<r<=L, so that x_k = x_{qL+r} = x_{qsm+r} = x_r = y_r = y_{qtn+r} = y_{q*L+r} = y_k. All that's left is to note that since m, n <= E, lcm(m, n) <= E(E-1).

[marcharper]

What about the following example?

Suppose the FSM contains two cycles of length n and m where m = k * n for integers m, k, and n, and the cycles produce the same sequence (with the m cycle producing the sequence k times, and the sequence may be cyclicly permuted). For simplicity let's consider a FSM that has a CD cycle and a DC cycle, and that one can get into either cycle with either an even or odd sequence of initial transitions. Then it would be necessary to unravel the entire history of play to the point where the cycle was entered to determine which cycle were are in (and hence which internal node the strategy is at). That's larger than E(E-1) = 2 IIUC.

[gaffney2010]

Thanks for the question.

For simplicity let's consider a FSM that has a CD cycle and a DC cycle, and that one can get into either cycle with either an even or odd sequence of initial transitions.

If you had a CD cycle (1 --C--> 2 --D--> 1) and a DC cycle somewhere else (1' --D--> 2' --C--> 1'), then this would have infinite memory, since there are identical cycles ending at both state 1 and state 2'. I think you agree that this makes this an infinite memory FSM, because you say that we'd need to unravel the whole history. I'm saying that if we repeated my algorithm E(E-1) times, and it still didn't converge (break all the ties), then we could conclude that it will never converge and that therefore the memory must be infinite. And of course it won't converge by then because of the trees I'm making for 1 and 2', they'll both have a branch that goes DCDCDCDCDC... forever.

That's larger than E(E-1) = 2 IIUC.

E should be total edges, so if this equaled 2, then E=2. So that we have something like 1 --C--> 2 --D--> 1 with no other edges. This FSM is finite, memory 1. So I'm claiming that the algorithm will converge within 2 steps, and it does.

1: D
2:C

It's converged after just 1 step.

On the other hand I could have a disjoint FSM, 1 --C--> 1 and 2 --C--> 2. If I run this, I get.

1: CC
2: CC

My algorithm would stop after 2 steps and say that this is infinite memory, which is right in the sense that I'll never know what state I'm in. [In practice we know where we start, so maybe I should throw away disjointed components before beginning.]

Suppose the FSM contains two cycles of length n and m where m = k * n for integers m, k, and n, and the cycles produce the same sequence (with the m cycle producing the sequence k times, and the sequence may be cyclicly permuted).

Okay, say we have 1 --C--> 2 --D--> 1 and somewhere else 1' --C--> 2' --D--> ... --C--> 6 --D--> 1', and the problem of course is that you have these branches that go like,

1: DCDCDCDC...
1' DCDCDCDC...

These branches are cycling with period 2 and period 6. L=lcm(2, 6)=6. I'm arguing that if these branches ever stop cycling it will be within the first 6 actions.

1: DCDCDC
1' DCDCDC

Because, which action comes next? What's the 7th action? Because of the period 2 on state 1, it must be the same as the 5th, 3rd, and 1st action. Because of the period 6 on state 1', the 7th action must match the 1st action. So the next action for BOTH matches the first action for both, but these were the same.

The next action after that is equal to the 2nd action for each, which is equal. And the next action is the 3rd action for both. And so on... You can see why I wanted to have a period that's a common multiple.

In practice we won't know the period, but we know that it'll be <= E, and even though we end up checking too many most of the time, that's okay.

[drvinceknight]

I've worked my way through this and I think it looks right. I tried to come up with some other examples that might break it but with no success.

Very neat @gaffney2010 👍

I haven't searched through the literature for such an algorithm -- one may exist. And if not, such an algorithm is potentially publishable.

👍 This would make for a neat little paper indeed.

Even if it's a bit slow that's probably fine since we can just run it at test time,

👍

In practice we won't know the period, but we know that it'll be <= E, and even though we end up checking too many most of the time, that's okay.

👍

[gaffney2010]

I guess this fails in the following regard:

You may have a complex graph, and you would need a memory of N to know what state you're in. However, if the two paths out of every state say to C, then this is memory 0. More tricky, you could use easily write a 4-state TFT, and my algorithm would fail.

I've assumed that we must know what state we're in.

What I want to actually do is tie-break the next-action decision. I'll include the two examples above in my tests.

[drvinceknight]

Closed by #1233 :) thanks @gaffney2010 👍