그런 게임에서 승리 전략은 무엇입니까?

Question

언젠가 나는 두 명의 플레이어 (A, B)와 4 개의 슬롯이 주어졌고, 각 플레이어는이 슬롯에 "N"또는 "O"를 넣었습니다. 전략 선수 A 또는 B가 확실하게 성공할 것입니까? 저는이 사실에 익숙하지 않으므로 아래의 경우에 대한 몇 가지 힌트를주었습니다. B는 A가 무엇을 넣어도 성공하지 않을 것입니다.

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

처음으로이 배열의 첫 번째 인덱스에 N을 넣은 다음 B는 N을 마지막 위치에 놓습니다. 그러면 A가 어디에 무엇을 넣든지간에 B가 이길 것입니다.

슬롯이 슬롯 7 개에 추가되는 경우 문제는 동일한 전략입니까?

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

나는 4 개의 솔트의 경우와 비슷한 방법이라고 생각했지만, 그러한 전제 조건이 필요합니다. 그 뒤에 몇 가지 이론이 있는지 확신 할 수 없습니다.

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

Answer 1

첫 번째 플레이어는 항상이 게임에서 이길 것입니다. 승리의 움직임은 _ _ _ N _ _ _

오직 7 개의 슬롯이므로이 게임의 상태는 3^7입니다. 따라서 각 상태는 동적 프로그래밍을 통해 쉽게 계산할 수 있습니다. 여기 내 솔루션은 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; 
}