CODEWITHSUNDEEP
algorithmdynamic-programming
Ashish Negi
Ashish Negi

Reputation: 5301

Dynamic Programming: States in a 2-player game

This is the problem in a programming contest where i "found" how to go through the states in 2-player games.

The problem is: An alternative game is played between two players A and B where A always start first and chooses some letters from given matrix and make words from a given dictionary. These letters are then discarded. Next player chooses from left over letters. The last one who cann't make a word loses. Each play optimally.

From the editorial i quote here 

    To iterate over all non-empty subsets of the given 
    set when they represented using bitmasks:

    submask = mask
    while submask > 0
        // do the job with the submask
        submask = (submask - 1) AND mask

In one of the solutions i saw 

    int solve(int state)
    {
        if(dp[state]!=-1)
            return(dp[state]);

        int res=1;
        int nstate=state;
        while(1)
        {
            if(valid[nstate])
                res=solve(state&(~nstate));
            if(res==0)
                break;
            nstate=((nstate-1)&state);
            if(nstate==0)
                break;
        }
        if(res==0)
            dp[state]=1;
        else
            dp[state]=0;
        return(dp[state]);
    }

This code has another AND with ~.

I cann't understand what is a '"STATE" here actually, and How this AND takes us through all the states ? Please explain this.

Upvotes: 1

Views: 1221

Answers (1)

Peter de Rivaz
Peter de Rivaz

Reputation: 33519

EXPLANATION OF STATE

The state is the set of remaining letters.

We replace letters that we still have with 1's, and letters that have gone with 0's.

This results in a binary number which is the number held in the variable mask.

For example, suppose we had the letters ABCDEFGH at the start of the game, and at a certain point we only had the letters B and D remaining.

The number 0x50 would represent this current state:

ABCDEFGH  at start
-B-D----  at current point in game
01010000  replace with 1's for letters we still have
0x50      treat as a binary number

BIT TWIDDLING

Both solutions use the bit twiddle nstate=((nstate-1)&state) .

If you start with nstate=state, this code will generate all the subsets of the state.

What does this mean? Well, suppose we had the state with current letters B and D. All possible non-empty subsets of this state are {B,D},{B},{D}.

These would be represented by the binary numbers 01010000,01000000,00010000.

And we can see that these are indeed generated by executing the following Python code:

state=0b01010000
nstate=state
while nstate:
    print bin(nstate)
    nstate=(nstate-1)&state

Gives output: 

0b01010000
0b01000000
0b00010000

Why does this work?

Roughly speaking, the code use nstate = nstate-1 to count down through all possible binary numbers, and the & state skips out the parts where there are just changes in the bits we don't care about (by immediately setting them to zero, instead of waiting for them to count down to zero).

Upvotes: 2

Related Questions