Какова стратегия победы в такой игре?

Question

Однажды мне задали такой вопрос: два игрока (A, B) и 4 слота, каждый из которых поставил «N» или «O» в эти слоты, и первое заклинание «NON» выиграло эту игру.Есть ли у игрока стратегии А или игрока Б наверняка успех?Я не очень знаком с этим, поэтому он дает некоторые подсказки для нижеследующего случая: успех B будет иметь значение, независимо от того, что помещает А.

[N (A помещает) | _ |_ |N (B ставит)]

Сначала A ставит N в первый индекс этого массива, затем B ставит N в последнюю позицию.Тогда независимо от того, что и куда А ставит, победит B.

Так что вопрос в том, добавляются ли слоты к 7 слотам, есть ли такая же стратегия?

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

Я думал, что путь похож на случаи с четырьмя сольтами, но для этого нужны такие предварительные условия.Я не уверен, что за этим стоит какая-то теория.

[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;
}