Game Algorithm for Removing Subsets [HW / Study]
We are given a problem, which I led to the following: You are assigned a binary number with all (for example, 11111) and a set of binary numbers of the same length (00101, 10000, 01100, 00100, 11100). There are two players A and B. At each step, the player can subtract any of the smaller numbers from the base binary number (11111), so that the AND binary code from number 2 is less. then the next player can subtract from the resulting, etc. The player who can no longer subtract loses. eg.
A B
11111 11010 // Now A cannot subtract
-00101 -10000 // anymore in the next turn.
------- ------ // So B wins the game.
11010 01010
------- ------
If both players are playing optimally (making the best choices to win), then I have to figure out which player wins for a given combination of binary numbers.
I've tried the O (n ^ 2) approach, but is there a faster way?
Edit: O (n ^ 2): where n is the number of states. For a binary number of length 6 (111111), 2 ^ 6 states are possible. so my complexity is O ((2 ^ 6) ^ 2).
Edit: My code that generates all possible states:
void makeAllStates() /* Bottom Up Approach. Starting from 00000 and going to 11111 */
{
// bool states[i] : True if state[i] is a winning position.
// bool isWord[i] : True if the given state matches a smaller number. (eg. If the main number has been reduced to 10110 and there is a smaller number 10110, then isWord[i] is true.
// bool visited[i] : True If the given state has been visited
// int statecount : Total number of states
int temp;
for(int xx=1;xx<stateCount;xx++)
{
for(int yy=1;yy<stateCount;yy++)
{
if(xx&yy)
continue;
if(!(isWord[xx] || isWord[yy]))
continue;
if(!visited[yy])
continue;
temp = xx^yy;
if(isWord[temp])
continue;
if(states[temp])
continue;
if(isWord[xx] && isWord[yy])
states[temp] = false;
else
{
if(isWord[xx])
states[temp] = !states[yy];
else
states[temp] = !states[xx];
}
visited[temp] = true;
if(temp == stateCount-1 && states[temp])
{
return;
}
}
}
}
source to share
I don't know if this will help you (you said the O (n ^ 2) approach, but you didn't say what N stands for). Try a general approach for fair play (Sprague-Grundy theory):
- position in the game is your main number.
- Find all "lost" positions (positions that you can no longer subtract)
- for all "lost" positions x: Grundy function g (x) = 0;
- Then if you want to compute the grundy function for the y position: find all the x_1 ... x_k positions so you can rotate from the y position to the x_i position. g (y) = mex (g (x_1), ..., g (x_k)). "mex" - "minimum excludant" - the smallest non-negative integer of all except g (x_1), ..., g (x_k). For example, mex (2, 3, 4) = 0, mex (0, 1, 2, 5) = 3, mex (0, 1) = 2, etc.
Note that you can recursively consider each position in the game, and you will consider position x once (when calculating g (x)), so this algorithm is linear in the number of possible positions. linear by the number of possible rotations between positions, i.e. O (N * K), where N is the number of states and K is the size of the set of smaller numbers (with which you can make rotations in your game)
If g (START_POSITION) = 0, then the starting position is the lost position and the first player loses (every turn leads to a winning position). If g (START_POSITION)> 0, then the starting position is a winning position (there is a rotation to position x, so g (x) = 0), so the first player wins.
Sorry for the bad english and hope this is helpful
source to share
Based on K. Bulatov's input, here is the final code over time. The complexity is O (n ^ 2) worst case. After pruning, the number of calls was reduced to a great extent. The main function is as follows:
//state : The state for which grundy number is being queried.
//visited[i] : If the grundy number of the state has already been calculated.
//wordStates[] : an array with all the smaller numbers stored.
//mex() : "minimal excludant" - the smallest non-negative integer not in array
int grundyNum(int state)
{
if(visited[state])
return grundy[state];
int grundArr[wordStates.size()];
int loc =0;
visited[state] = true;
for(int xx =0;xx<wordStates.size();xx++)
{
if((state&wordStates[xx]) == wordStates[xx])
{
grundArr[loc] = grundyNum(state^wordStates[xx]);
loc++;
}
}
grundy[state] = mex(grundArr,loc);
return grundy[state];
}
Just calling a function with the following gives a winner:
result = grundy(1111111);
winner = result==0?"B":"A";
source to share