Dual of finite state machine players

[drvinceknight]

In Ashlock and Kim 2008 the dual of a strategy is defined as:

Strategy $A'$ is said to be the dual of strategy $A$ if $A$ and $A'$ can be written as finite-state machines that are identical except that their responses are reversed.

Note: this does not correspond to flipping the actions (using the FlippedTransformer for example), but needs to actually go in to the finite state machine and change the response (not the states).

This would be an easy addition to do for the generic finite state machine strategies (could be done nicely by writing a function that maps a finite state machine to the corresponding dual finite state machine) and could also be implemented for a few others (for example Pavlov/WSLS is it's own dual when you change the initial move from C to D).

This is relevant to the work being done on #138 as the dual strategies are used for the fingerprinting approach described in Ashlock's work. FYI the more we (@theref is working on this with @Nikoleta-v3 and I) work on #138 the more we feel that an alternative approach is necessary (and will no doubt be obtained).

[meatballs]

....the more we feel that an alternative approach is necessary

An alternative to what?

Ashlock's work itself? (i.e Is there some issue with how the fingerprinting is done)? Using Ashlock's work for #138? (i.e The fingerprinting is fine, but doesn't solve our issue)?

[drvinceknight]

An alternative to what?

Ashlock's work itself? (i.e Is there some issue with how the fingerprinting is done)? Using Ashlock's work for #138? (i.e The fingerprinting is fine, but doesn't solve our issue)?

No issue with how it's done, just that it's not the best approach for #138 in general. He does what he describes but what he describes seems to be particularly aimed at finite state machine strategies and not immediately applicable to "any" strategy. My hunch is also that it's not terribly robust but time will tell as we evaluate it more. We've got a couple of ideas for other approaches for #138 that we'll explore in time.

[marcharper]

Dual Strategy Transformer?

[drvinceknight]

Thought about that but it would have to only apply to finite state machines (dual is only defined on fsm strategies). But there are also some strategies like WSLS that could have a dual although it's not currently written as a fsm.

My thinking was to write a transformer for the fsm and build the fsm strategies using it. We could still expose the fsm transformer. What do you think?

[theref]

I've come up with an algorithm that would allow us to create a Dual Strategy Transformer for any strategy. I don't think it will be difficult to implement either. A quick explanation:

• Get the history for the game so far (Dual v's Probe)
• Flip the Dual's moves to obtain the history for the original Strategy (Vince, this is the step we were missing on Monday)
• Obtain the original strategy's next move based on the flipped history
• Flip this to get the move for the dual strategy

This is much easier to show with a whiteboard, but any questions let me know!

[drvinceknight]

Very nice @theref. That sounds like it would work! Fantastic.

[marcharper]

Interesting. Perhaps every strategy can be realized as a sufficiently complex finite state machine?

[drvinceknight]

Perhaps every strategy can be realized as a sufficiently complex finite state machine?

Yeah, I think that's definitely true for deterministic strategies. The existence proof would simply be that the sequence of [finite state machine] states correspond to cumulative histories of the interactions. So state 1 is the state of no histories, then depending on the actions the next state can be a choice of 4: CC, CD, DC or DD. And then a choice of 16 etc...

I'm not entirely sure what/how that works for stochastic strategies though. The same applies for a stochastic strategy on a given Markov path (ie for a given seed).

What @theref's approach does is in essence carry around the player and gleam from it's action what state it's underlying finite state machine is in (without needing to know what that finite state machine is). Computationally we can obviously do the same for stochastic strategies.

Have spoken to @theref and he'll be implementing that after carrying out some more experiments (I forget if you know or not @marcharper, @theref is currently doing his final year project with me on this).

[marcharper]

Let me know if I can help!

[drvinceknight]

Thanks, we will :)