New game : Plus_one

Decision and strategy, simulations and probability models, card and board games, ...
JeanFrancois
Posts: 29
Joined: Wed Feb 13, 2013 10:32 pm

New game : Plus_one

Post by JeanFrancois » Thu Feb 14, 2013 9:24 pm

Game : Plus_one

Plus_one is 2 players game.
You need a 5x5 board and 74 stones (or matchsticks).

Goal of the game :
2 conditions to win :
1. either you are the first player to get rid of all of your stones.
2. either you are the last one who made a legal move

At the setup the board is empty.
Each player start with 37 stones.
Choose who plays first then players alternate their turns.
On his turn player place stone (s) on an empty square.
Player can not pass his turn.

There a single rule for placing stones on the board.
The rule is called Plus_one (+1).
Let us note each square n(i,j) where i is the column and j the row.
The number of stones placed on an empty square n(a,b) has to be equal to max(max(a,j),max(i,b))+1.

An example :

Player wants to place his stones on n(3,4).
The maximal number of stones placed yet on the column 3 is 2.
The maximal number placed on the row 4 is 3.
Then he has to place 4 stones = max(3,2)+1=3+1=4.

Precision :
Each square is initialized at zero at the start of the game so player start by placing one stone. As long as the intersection of the column and the row are empty player place one stone =0+1.
If a player place one stone in some empty square it does not mean that his opponent has to place his stone(s) in the same column and the same row.

The game ends when there is no legal move for one of the players or when one of the players get rid of his 37 stones.
No draw is possible.

Is there a winning strategy for one of the players?

thundre
Posts: 356
Joined: Sun Mar 27, 2011 9:01 am

Re: New game : Plus_one

Post by thundre » Fri Feb 15, 2013 2:00 pm

JeanFrancois wrote:Is there a winning strategy for one of the players?
Yes. :D If there is no chance of draw and no random element, there must be a winning strategy for one or the other. Which?

If the stones were not limited to 37 per player, this woud be an impartial game. http://en.wikipedia.org/wiki/Impartial_game.
Image

JeanFrancois
Posts: 29
Joined: Wed Feb 13, 2013 10:32 pm

Re: New game : Plus_one

Post by JeanFrancois » Fri Feb 15, 2013 3:02 pm

Which one?
First or second player?

thundre
Posts: 356
Joined: Sun Mar 27, 2011 9:01 am

Re: New game : Plus_one

Post by thundre » Sun Feb 17, 2013 9:56 am

JeanFrancois wrote:Which one?
First or second player?
First.

If you give the players 38 or 39 stones, the second player can force a win.
Image

JeanFrancois
Posts: 29
Joined: Wed Feb 13, 2013 10:32 pm

Re: New game : Plus_one

Post by JeanFrancois » Sun Feb 17, 2013 2:58 pm

thundre wrote:
JeanFrancois wrote:Which one?
First or second player?
First.

If you give the players 38 or 39 stones, the second player can force a win.
Thank you.
Are you ready to play with me.
37 stones for each player.
You play first.

First player : Thundre
Second player : JeanFrancois

Here is the board
Columns A,B,C,D,E
Rows : 1,2,3,4,5

1-2-3-4-5
0-0-0-0-9
0-0-0-0-0
8-1-6-5-7
0-0-0-0-8-

Thundre : 37 stones
Used : 28
Remaining : 9

JeanFrancois : 37 stones
Used : 31
Remaining : 6

I`m waiting for your move.
Go ahead!

I will update every move.

1. A1 (1) - B4(1)
2. B1 (2) - C1 (3)
3. D1(4) - D4(5)
4. C4(6) - E1(5)
5. E4(7) - E5(8)
6. A4(8) - E2(9)
Updated
Last edited by JeanFrancois on Mon Feb 18, 2013 1:47 am, edited 8 times in total.

thundre
Posts: 356
Joined: Sun Mar 27, 2011 9:01 am

Re: New game : Plus_one

Post by thundre » Sun Feb 17, 2013 11:50 pm

OK, I will play.

First moves are all equivalent. I will take A-1, for 1 stone.
Image

JeanFrancois
Posts: 29
Joined: Wed Feb 13, 2013 10:32 pm

Re: New game : Plus_one

Post by JeanFrancois » Mon Feb 18, 2013 12:10 am

thundre wrote:OK, I will play.

First moves are all equivalent. I will take A-1, for 1 stone.
Follow my moves in the updated post above.

B4(1 stone)

thundre
Posts: 356
Joined: Sun Mar 27, 2011 9:01 am

Re: New game : Plus_one

Post by thundre » Mon Feb 18, 2013 12:41 am

JeanFrancois wrote: Follow my moves in the updated post above.

B4(1 stone)
B1, 2 stones. (edited)
Image

JeanFrancois
Posts: 29
Joined: Wed Feb 13, 2013 10:32 pm

Re: New game : Plus_one

Post by JeanFrancois » Mon Feb 18, 2013 1:12 am

My moves will be updated in the same and previous box.

thundre
Posts: 356
Joined: Sun Mar 27, 2011 9:01 am

Re: New game : Plus_one

Post by thundre » Mon Feb 18, 2013 1:19 am

OK, I will take D1 with 4 stones.

Processing time just dropped from ~5 minutes to 8s.
Image

JeanFrancois
Posts: 29
Joined: Wed Feb 13, 2013 10:32 pm

Re: New game : Plus_one

Post by JeanFrancois » Mon Feb 18, 2013 1:23 am

thundre wrote:OK, I will take D1 with 4 stones.

Processing time just dropped from ~5 minutes to 8s.
Just go ahead one hour from now I will not be occupied

thundre
Posts: 356
Joined: Sun Mar 27, 2011 9:01 am

Re: New game : Plus_one

Post by thundre » Mon Feb 18, 2013 1:34 am

C4, 6 stones.
Image

thundre
Posts: 356
Joined: Sun Mar 27, 2011 9:01 am

Re: New game : Plus_one

Post by thundre » Mon Feb 18, 2013 1:40 am

E4, 7 stones
Image

thundre
Posts: 356
Joined: Sun Mar 27, 2011 9:01 am

Re: New game : Plus_one

Post by thundre » Mon Feb 18, 2013 1:44 am

A4, 8 stones
Image

JeanFrancois
Posts: 29
Joined: Wed Feb 13, 2013 10:32 pm

Re: New game : Plus_one

Post by JeanFrancois » Mon Feb 18, 2013 1:49 am

You win!

Congratulations!

thundre
Posts: 356
Joined: Sun Mar 27, 2011 9:01 am

Re: New game : Plus_one

Post by thundre » Mon Feb 18, 2013 1:49 am

A5, 9 stones.

I'm out of stones.
Image

JeanFrancois
Posts: 29
Joined: Wed Feb 13, 2013 10:32 pm

Re: New game : Plus_one

Post by JeanFrancois » Mon Feb 18, 2013 1:52 am

thundre wrote:A5, 9 stones.

I'm out of stones.
You win

I made a mistake in my last move.
A5 was the required move.

JeanFrancois
Posts: 29
Joined: Wed Feb 13, 2013 10:32 pm

Re: New game : Plus_one

Post by JeanFrancois » Mon Feb 18, 2013 1:56 am

It is not easy to play while you are editing the game.
I will play better if the game was implemented.

Anyway I`m thinking to introduce a new rule :
- each player start with the same number of stones (10 for example)
- each time you drop k stones you could replace them by k+1 or k+2 stones picked some fixed pool of stones (80 for example)

Thank you for having played with me.

thundre
Posts: 356
Joined: Sun Mar 27, 2011 9:01 am

Re: New game : Plus_one

Post by thundre » Mon Feb 18, 2013 2:24 am

JeanFrancois wrote:
thundre wrote: I made a mistake in my last move.
A5 was the required move.
If you do that, I still have E2.

I'm glad to validate the algorithm.

Code: Select all

public class PlusOne {
    
    public class Position implements Comparable<Position> {
        private long usedSquares;
        private int rowMax[] = new int[rows];
        private int colMax[] = new int[cols];
        /** Next player is 0, values swap at move time */
        private int stonesRemaining[] = new int[2];
        private long rowHash[] = null;
        private long colHash[] = null;
        private String rowName[] = new String[rows];
        private String colName[] = new String[cols];
        
        public Position(int stones) {
            usedSquares = 0;
            stonesRemaining[0] = stonesRemaining[1] = stones;
        }
        
        public Position(int stones0, int stones1, int board[][],
                String rowName[], String colName[]) {
            stonesRemaining[0] = stones0;
            stonesRemaining[1] = stones1;
            System.arraycopy(rowName, 0, this.rowName, 0, rows);
            System.arraycopy(colName, 0, this.colName, 0, cols);
            for (int r = 0; r < rows; r++) {
                for (int c = 0; c < cols; c++) {
                    if (board[r][c] > 0) {
                        rowMax[r] = Math.max(rowMax[r], board[r][c]);
                        colMax[c] = Math.max(colMax[c], board[r][c]);
                        usedSquares |= rowBits[r] & colBits[c];
                    }
                }
            }
            for (int i = rows-1; i > 0; i--) {
                for (int j = rows-1; j >= i; j--) {
                    normalize(j,j);
                }
            }
        }
        
        public Position(Position p0, int r, int c) {
            int stones = Math.max(p0.rowMax[r], p0.colMax[c]) + 1;
            usedSquares = p0.usedSquares | (rowBits[r] & colBits[c]);
            System.arraycopy(p0.rowMax, 0, rowMax, 0, rows);
            System.arraycopy(p0.colMax, 0, colMax, 0, cols);
            rowMax[r] = colMax[c] = stones;
            stonesRemaining[0] = p0.stonesRemaining[1];
            stonesRemaining[1] = p0.stonesRemaining[0] - stones;
            
            normalize(r, c);
        }
        
        public boolean isValid(int r, int c) {
            if ((usedSquares & rowBits[r] & colBits[c]) != 0)
                return false;
            int stonesRequired = Math.max(rowMax[r], colMax[c]) + 1;
            return stonesRequired <= stonesRemaining[0];
        }
        
        public String moveString(int r, int c) {
            if ((usedSquares & rowBits[r] & colBits[c]) != 0)
                return "illegal move";
            int stonesRequired = Math.max(rowMax[r], colMax[c]) + 1;
            return "place " + stonesRequired + " stones at " + rowName[r] + "-" + colName[c];
        }
        
        private void normalize(int r0, int c0) {
            /*
             * Sort rows in the order of their max value, with a tiebreaker
             * being the value set of the empty column max.
             * (also vice-versa)
             */
            int r1 = r0;
            for (int r = r0-1; r >= 0; r--) {
                if (rowMax[r] > rowMax[r0])
                    break;
                if (rowMax[r] == rowMax[r0] &&
                        rowTieBreak(r) >= rowTieBreak(r0))
                    break;
                r1 = r;
            }
            if (r1 < r0) {
                insertRow(r0, r1);
            }
            
            int c1 = c0;
            for (int c = c0-1; c >= 0; c--) {
                if (colMax[c] > colMax[c0])
                    break;
                if (colMax[c] == colMax[c0] &&
                        colTieBreak(c) >= colTieBreak(c0))
                    break;
                c1 = c;
            }
            if (c1 < c0) {
                insertCol(c0, c1);
            }
        }
        
        private long rowTieBreak(int r) {
            if (rowHash == null)
                rowHash = new long[rows];
            if (rowHash[r] > 0)
                return rowHash[r];
            long result = 1;
            for (int c = 0; c < cols; c++) {
                if ((usedSquares & rowBits[r] & colBits[c]) == 0)
                    result *= sieve.getPrime(colMax[c]);
            }
            rowHash[r] = result;
            return result;
        }
        
        private long colTieBreak(int c) {
            if (colHash == null)
                colHash = new long[cols];
            else if (colHash[c] > 0)
                return colHash[c];
            long result = 1;
            for (int r = 0; r < cols; r++) {
                if ((usedSquares & colBits[c] & rowBits[r]) == 0)
                    result *= sieve.getPrime(rowMax[r]);
            }
            colHash[c] = result;
            return result;
        }
        
        /** Moves row r0 down to r1 and the rest up 1 */
        private void insertRow(int r0, int r1) {
            rowHash = null;
            long rightBits = usedSquares & rowBits[r0];
            long leftBits = 0;
            for (int r = r1; r < r0; r++) {
                leftBits |= (usedSquares & rowBits[r]);
            }
            usedSquares ^= rightBits;
            usedSquares ^= rightBits >> (cols * (r0-r1));
            usedSquares ^= leftBits;
            usedSquares ^= leftBits << cols;
            int r0Max = rowMax[r0];
            String r0Name = rowName[r0];
            for (int r = r0; r > r1; r--) {
                rowMax[r] = rowMax[r-1];
                rowName[r] = rowName[r-1];
            }
            rowMax[r1] = r0Max;
            rowName[r1] = r0Name;
        }
        
        /** Moves column c0 down to c1 and the rest up 1 */
        private void insertCol(int c0, int c1) {
            colHash = null;
            long rightBits = usedSquares & colBits[c0];
            long leftBits = 0;
            for (int c = c1; c < c0; c++) {
                leftBits |= (usedSquares & colBits[c]);
            }
            usedSquares ^= rightBits;
            usedSquares ^= rightBits >> (c0-c1);
            usedSquares ^= leftBits;
            usedSquares ^= leftBits << 1;
            int c0Max = colMax[c0];
            String c0Name = colName[c0];
            for (int c = c0; c > c1; c--) {
                colMax[c] = colMax[c-1];
                colName[c] = colName[c-1];
            }
            colMax[c1] = c0Max;
            colName[c1] = c0Name;
        }

        public int compareTo(Position that) {
            long result1 = this.usedSquares - that.usedSquares;
            if (result1 != 0) return Long.signum(result1);
            int result = this.stonesRemaining[0] - that.stonesRemaining[0];
            if (result != 0) return result;
            result = this.stonesRemaining[1] - that.stonesRemaining[1];
            if (result != 0) return result;
            for (int r = 0; r < rows; r++) {
                result = this.rowMax[r] - that.rowMax[r];
                if (result != 0) return result;
            }
            for (int c = 0; c < cols; c++) {
                result = this.colMax[c] - that.colMax[c];
                if (result != 0) return result;
            }
            return 0;
        }
    }
    
    private static final PrimeSieve sieve = PrimeSieve.getInstance();
    
    private final int startStones;
    private final int rows, cols;
    private final long rowBits[];
    private final long colBits[];
    //private TreeMap<Position,Boolean> winners = new TreeMap<Position,Boolean>();

    public PlusOne(int startStones, int rows, int cols) {
        this.startStones = startStones;
        this.rows = rows;
        this.cols = cols;
        rowBits = new long[rows];
        colBits = new long[cols];
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                long bit = 1L << (r * cols + c);
                rowBits[r] |= bit;
                colBits[c] |= bit;
            }
        }
    }

    public boolean isWinner(Position p0) {
        // did the other player just win by placing all his stones?
        if (p0.stonesRemaining[1] == 0) return false;

        TreeSet<Position> checked = new TreeSet<Position>();
        
        int legalMoves = 0;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (p0.isValid(r, c)) {
                    legalMoves++;
                    Position p1 = new Position(p0, r, c);
                    if (!checked.contains(p1)) {
                        if (!isWinner(p1)) {
                            //winners.put(p0, true);
                            return true;
                        }
                        checked.add(p1);
                    }
                }
            }
        }
        //winners.put(p0, false);
        return false;
    }
    
    public boolean printWinner(Position p0) {
        // did the other player just win by placing all his stones?
        if (p0.stonesRemaining[1] == 0) return false;

        TreeSet<Position> checked = new TreeSet<Position>();
        
        int legalMoves = 0;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (p0.isValid(r, c)) {
                    legalMoves++;
                    Position p1 = new Position(p0, r, c);
                    if (!checked.contains(p1)) {
                        if (!isWinner(p1)) {
                            //winners.put(p0, true);
                            System.out.println("Winning move for " + p0 + 
                                    " is " + p0.moveString(r, c));
                            return true;
                        }
                        checked.add(p1);
                    }
                }
            }
        }
        //winners.put(p0, false);
        System.out.println("No winning move for " + p0);
        return false;
    }
    
    public boolean solve() {
        Position p0 = new Position(this.startStones);
        boolean result = isWinner(p0);
        System.out.println("(" + startStones + "," + rows + "," + cols + "): " + 
                (result ? "First" : "Second") + " player can win; ");
                //+ this.winners.size() + " meaningful positions evaluated");

        return result;
    }
    
    public void play() {
        int b[][] = new int[][] {
               //A B C D E
                {1,2,3,4,5},// 1
                {0,0,0,0,0},// 2
                {0,0,0,0,0},// 3
                {8,1,6,5,7},// 4
                {9,0,0,0,8},// 5
        };
        Position p = new Position(9,6,b,
                new String[] {"1", "2", "3", "4", "5"},
                new String[] {"A", "B", "C", "D", "E"});
                
        this.printWinner(p);
    }
    
    public static void test() {
        for (int s = 37; s <= 37; s++) {
            PlusOne p = new PlusOne(s, 5, 5);
            p.solve();
        }
    }

    public static void main(String args[]) {
        long t0 = System.currentTimeMillis();
        PlusOne p = new PlusOne(37, 5, 5);
        p.play();

        long t1 = System.currentTimeMillis();
        System.out.println("Run time " + (t1-t0) + " ms");
        System.exit(0);
    }
}
Image

JeanFrancois
Posts: 29
Joined: Wed Feb 13, 2013 10:32 pm

Re: New game : Plus_one

Post by JeanFrancois » Mon Feb 18, 2013 2:35 am

With E2 you will surely win.
It reminds me when I played hex for the first time.
I do not have big knowledge in programming (in practised Basic long long time ago).
I will start learning Visual Basic the next month.
I have enough documentation now.

Thank you for your program.

Post Reply