What is the winning strategy in such a game?

Question

Someday I was asked such a question, two players (A, B) and 4 slots, each player put "N" or "O" in these slots, which first said "NON", winning this game. Is the strategy of player A or player B certainly successful? I am not very familiar with this, so he gives some clues for the following case, B will be successful, no matter what A puts.

[N (A puts) | _ | _ | N (B puts)]

First, put N at the first index of this array, then B put N at the last position. Then no matter what and where A puts, B will win.

So the question is, are slots added to 7 slots, is there the same strategy?

[_ | _ | _ | _ | _ | _ | _]

I thought this was similar to the four hundredth cases, however, this requires such preconditions. I am not sure if there is any theory.

[N | _ | _ | N | _ | _ | N]

Answer 1

The first player will always win this game. Winning move - _ _ _ N _ _ _

As soon as 7 slots, so there are only 3 ^ 7 states of this game. Therefore, each state is easily computed by dynamic programming. Here is my solution in C ++

#include <cstdio> #include <string> #include <map> #include <iostream> using namespace std; map<string, string> mp; string go(string s) { if (mp.find(s) != mp.end()) { return mp[s]; } if (s.find("_") == -1) { cout<<s<<" "<<"DRAW"<<endl; return mp[s] = "DRAW"; } string s1 = s; bool draw_found = false; for (int i = 0; i < s.size(); ++i) { if (s[i] == '_') { string t = "NO"; for (int j = 0; j < t.size(); ++j) { s[i] = t[j]; if (s.find("NON") != -1) { cout<<s1<<" WIN by move: "<<s<<endl; return mp[s1] = "WIN"; } string r = go(s); if (r == "LOSE") { cout<<s1<<" "<<" WIN by move: "<<s<<endl; return mp[s1] = "WIN"; } else if (r == "DRAW") { draw_found = true; } s[i] = 'O'; } s[i] = '_'; } } if (draw_found) { cout<<s<<" "<<"DRAW"<<endl; return mp[s] = "DRAW"; } cout<<s<<" "<<"LOSE"<<endl; return mp[s] = "LOSE"; } int main (void) { string s; for (int i = 0; i < 7; ++i) { s += "_"; } string g = go(s); cout<<g<<endl; return 0; }