在最佳玩的 2 人游戏中决定获胜者

Question

我遇到了 this question。根据问题：

‘samu’ and ‘vibhu’ are playing a game where there are N integers from 1 to N lying on the table. In each turn, the player gets to pick one integer to mark as visited from among the previously unvisited ones. If in a turn, the player picks a number which completes the picking of three consecutive numbers, he wins. i.e., say at some stage in the game 2 and 4 are already picked(visited) if the player now picks 3, he wins. Assuming samu starts first and both the players play perfectly optimally, who is the winner.

我尝试应用 WL 算法（在正确理解之后）described here 即：

boolean isWinning(position pos) {
    moves[] = possible positions to which I can move from the position pos;
    for (all x in moves) 
        if (!isWinning(x)) return true;
    return false; 
}

所以，我的代码是（适当修改WL算法后）：[=16=]

public class HelloWorld{

    public static boolean[] visited;
    public static int n;
    public static void main(String []args){

        n=12;
        visited=new boolean[n];
        java.util.Arrays.fill(visited,false);
        for(int i=0; i<n; i++){
            visited[i]=true;
            if(isWinning(i)){
                System.out.println("first one wins");
                System.exit(0);
            }
            visited[i]=false;
        }
        System.out.println("second one wins");
    }

    public static boolean isWinning(int x){
        if(threeStrikes()){
            return true;
        }
        for(int i=0; i<n; i++){
            if(!visited[i]){
                visited[i]=true;
                if(!isWinning(i)){
                    return true;
                }
                visited[i]=false;
            }
        }
        return false;
    }
    public static boolean threeStrikes(){
        for(int i=0; i<n-2; i++){
            if(visited[i]&&visited[i+1]&&visited[i+2]){
                return true;
            }
        }
        return false;
    }
}

问题是它为 n=6 打印 "first one wins"。在 this discussion 线程中，op 表示对于 n=6，第二个应该获胜。我不知道他是不是错了，或者我的代码是否遗漏了什么。感谢任何帮助。

Answer 1

首先，这是您的代码的修订版：

public class HelloWorld {

    public static boolean[] visited;
    public static int n;
    public static void main(String []args){

        n=12;
        visited=new boolean[n];
        java.util.Arrays.fill(visited,false);
        for(int i=0; i<n; i++){
            visited[i]=true;
            if(!isOpponentWinning()){
                System.out.println("first one wins");
                System.exit(0);
            }
            visited[i]=false;
        }
        System.out.println("second one wins");
    }

    public static boolean isOpponentWinning(){
        for(int i=0; i<n; i++){
            if(!visited[i]){
                visited[i]=true;
                if(threeStrikes() || !isOpponentWinning()){
                    visited[i]=false;
                    return true;
                }
                visited[i]=false;
            }
        }
        return false;
    }
    public static boolean threeStrikes(){
        for(int i=0; i<n-2; i++){
            if(visited[i]&&visited[i+1]&&visited[i+2]){
                return true;
            }
        }
        return false;
    }
}

修改为：

isWinning() 实际上是检查当前玩家的对手是否获胜所以我将其更改为 isOpponentWinning() 只是为了清晰度。
当对手有 threeStrikes() 时返回 true 是错误的，因为它被调用者（获胜玩家）否定了).因此，当最后一名球员达到三分球时，停止标准现在为真，因此返回真这里是正确的。
因为我们正在检查对手是否获胜（而不是当前玩家），所以也应该在第一次调用 isOpponentWinning() 时添加否定（在主程序中功能）。
为了正确回溯，我在 isOpponentWinning() 中返回 true 之前添加了 visited[i]=false。

关于你关于 n=6 的问题，确实第二个应该赢。假设玩家 A 先玩，B 第二玩。

如果A选择1，B可以选择4，然后A接下来选择什么B可以在下一回合获胜
如果A选择2，B可以选择5，然后A接下来选择什么B可以在下一回合获胜
如果A选择3，B可以选择6，然后A接下来选择什么B可以在下一回合获胜

其余选项是对称的。我们得到无论A第一步选择什么，B都可以保证获胜。

在最佳玩的 2 人游戏中决定获胜者

Deciding winner in an optimally played 2-player game

algorithm

recursion

game-theory

minmax