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

Re: New game : Plus_one

Post by JeanFrancois » Mon Feb 18, 2013 3:05 pm

Can I ask you which programming language did you use to write down your code above?

Thank you.

User avatar
jaap
Posts: 535
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: New game : Plus_one

Post by jaap » Mon Feb 18, 2013 3:32 pm

JeanFrancois wrote:Can I ask you which programming language did you use to write down your code above?

Thank you.
That's Java.

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

Re: New game : Plus_one

Post by JeanFrancois » Mon Feb 18, 2013 3:36 pm

jaap wrote:
JeanFrancois wrote:Can I ask you which programming language did you use to write down your code above?

Thank you.
That's Java.
Thank you.
Sorry to bother you again I`m almost an ignorant when it comes to programming
How to make it executable?

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

Re: New game : Plus_one

Post by JeanFrancois » Mon Feb 18, 2013 5:04 pm

I tried to run it here :

http://ideone.com/

It did not work.
Message : compilation error

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

Re: New game : Plus_one

Post by thundre » Mon Feb 18, 2013 5:12 pm

JeanFrancois wrote: Thank you.
Sorry to bother you again I`m almost an ignorant when it comes to programming
How to make it executable?
Java usually runs as interpreted bytecode, so it is not technically executable. You need to load a JDK (java development kit) on your computer. Some prefer using an IDE (integrated development environment) such as Eclipse. http://www.eclipse.org

I just realized that the class I posted depends on another class -- PrimeSieve. You can replace the getPrime() calls with a hardcoded array of the first few primes. I think 2*sqrt(37)=12 primes would be sufficient for a 37-stone game.

To play, you must edit the board position b[][] in the play() method to reflect the current position. The numbers 9 and 6 are the stones remaining for the player to move and the other player.

If you decide to learn Java, it wouldn't be too hard to add a GUI to this to make an interactive game out of it. However, there is one thing you should know about the algorithm before you go to that effort. It doesn't make a move unless it has analyzed the game to the end and determined that that move is a winning move. It chooses the first winning move it finds, and if it doesn't find one it doesn't have a clue how to choose a losing move.

edit: new version of code, not dependent on PrimeSieve.

Code: Select all

import java.util.TreeSet;

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 *= PRIMES[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 *= PRIMES[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 long PRIMES[] = new long[] {
        2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43
    };
    
    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[][] {
                {1,0,0,0,0},
                {0,0,0,0,0},
                {0,0,0,0,0},
                {0,1,0,0,0},
                {0,0,0,0,0},
        };
        Position p = new Position(36,36,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 » Tue Feb 19, 2013 2:33 pm

Thank you for the code.
I will try to make it usable with the help of one of my friends.

Post Reply