Deciding winner in an optimally played 2-player game

Question

I came across this question. According to the 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.

I tried to apply the WL algorithm (after understanding it properly)described here which is:

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

So, my code is(after suitably modifying the WL algorithm):

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

The problem is that it prints "first one wins" for n=6. In this discussion thread, the op has said that for n=6, the second one should win. I don't know if he is wrong or if my code is missing something. Any help is appreciated.

zohar.kom zohar.kom · Accepted Answer · 2018-08-13T20:28:27

First, here is a revised version of your code:

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

The modifications were:

isWinning() is actually checking if the opponent of the current player is winning so I changed it to isOpponentWinning() just for clarity.
Returning true when the opponent has threeStrikes() is wrong, since it was negated by the caller (who is the winning player). So the stopping criterion is now true when the last player reached a three-strike, and thus returning true here is correct.
Since we're checking if the opponent is winning (and not the current player), negation should be added also in the first call to isOpponentWinning() (in the main function).
For correct backtracking, I added visited[i]=false before returning true in isOpponentWinning().

About your question regarding n=6, indeed the second one should win. Say player A plays first and B plays second.

If A chooses 1, B can choose 4 and then whatever A chooses next B can win in it's next turn.
If A chooses 2, B can choose 5 and then whatever A chooses next B can win in it's next turn.
If A chooses 3, B can choose 6 and then whatever A chooses next B can win in it's next turn.

The rest of the options are symmetrical. We get that whatever A chooses as it's first move, B can guarantee a win.

Deciding winner in an optimally played 2-player game

1 Answers