这样的游戏中获胜的策略是什么？

Question

有一天，我遇到了这样一个问题：两个玩家（A、B）和4个插槽，每个玩家在这些插槽中放置“N”或“O”，谁先拼出“NON”就赢得游戏。是否存在某种策略使玩家A或玩家B一定会成功？

对于下面的情况，我不太熟悉，所以他给了一些提示，无论A放什么，B都会成功。

[N（A放）| _ | _ | N（B放）]

首先，A将N放在此数组的第一个索引处，然后B在最后一个位置放置N。然后无论A在哪里放什么，B都会获胜。

因此，问题是如果将插槽添加到7个插槽中，是否存在相同的策略？

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

我认为这种方式类似于四个插槽的情况，但需要满足某些前提条件。我不确定是否有一些理论支持这一点。

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

- Ivan

---

这在很大程度上取决于他们为了实现“成功”需要做什么。 - Sergey Kalinichenko

你的规则没有描述获胜条件，因此它们要么是不完整的，要么就不存在获胜策略。 - Sylvain Defresne

既然我们现在有了一个合适的问题，让我们撤销所有的踩。下次在发布问题之前最好先写完整的问题，以避免这种情况发生。 - Matti Virkkunen

@dasblinkenlight 抱歉，大家，我因误操作发布了这条未完成的消息。请现在检查一下。 - Ivan

如果游戏结束时没有拼出NON，那么谁会赢得胜利？ - Nabb

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

- Arif

---

根据我的理解，您的程序试图迭代 3^7 中所有可能的值，并检查玩家 A 是否可以赢得这个游戏，对吗？如果不允许先计算这些可能性，那么您怎么能够找出答案呢？ - Ivan