New game : Plus_one

 Posts: 29
 Joined: Wed Feb 13, 2013 10:32 pm
New game : Plus_one
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?
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?
Re: New game : Plus_one
Yes. If there is no chance of draw and no random element, there must be a winning strategy for one or the other. Which?JeanFrancois wrote:Is there a winning strategy for one of the players?
If the stones were not limited to 37 per player, this woud be an impartial game. http://en.wikipedia.org/wiki/Impartial_game.

 Posts: 29
 Joined: Wed Feb 13, 2013 10:32 pm
Re: New game : Plus_one
Which one?
First or second player?
First or second player?
Re: New game : Plus_one
First.JeanFrancois wrote:Which one?
First or second player?
If you give the players 38 or 39 stones, the second player can force a win.

 Posts: 29
 Joined: Wed Feb 13, 2013 10:32 pm
Re: New game : Plus_one
Thank you.thundre wrote:First.JeanFrancois wrote:Which one?
First or second player?
If you give the players 38 or 39 stones, the second player can force a win.
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
12345
00009
00000
81657
00008
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.
Re: New game : Plus_one
OK, I will play.
First moves are all equivalent. I will take A1, for 1 stone.
First moves are all equivalent. I will take A1, for 1 stone.

 Posts: 29
 Joined: Wed Feb 13, 2013 10:32 pm
Re: New game : Plus_one
Follow my moves in the updated post above.thundre wrote:OK, I will play.
First moves are all equivalent. I will take A1, for 1 stone.
B4(1 stone)
Re: New game : Plus_one
B1, 2 stones. (edited)JeanFrancois wrote: Follow my moves in the updated post above.
B4(1 stone)

 Posts: 29
 Joined: Wed Feb 13, 2013 10:32 pm
Re: New game : Plus_one
My moves will be updated in the same and previous box.
Re: New game : Plus_one
OK, I will take D1 with 4 stones.
Processing time just dropped from ~5 minutes to 8s.
Processing time just dropped from ~5 minutes to 8s.

 Posts: 29
 Joined: Wed Feb 13, 2013 10:32 pm
Re: New game : Plus_one
Just go ahead one hour from now I will not be occupiedthundre wrote:OK, I will take D1 with 4 stones.
Processing time just dropped from ~5 minutes to 8s.

 Posts: 29
 Joined: Wed Feb 13, 2013 10:32 pm
Re: New game : Plus_one
You win!
Congratulations!
Congratulations!
Re: New game : Plus_one
A5, 9 stones.
I'm out of stones.
I'm out of stones.

 Posts: 29
 Joined: Wed Feb 13, 2013 10:32 pm
Re: New game : Plus_one
You winthundre wrote:A5, 9 stones.
I'm out of stones.
I made a mistake in my last move.
A5 was the required move.

 Posts: 29
 Joined: Wed Feb 13, 2013 10:32 pm
Re: New game : Plus_one
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.
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.
Re: New game : Plus_one
If you do that, I still have E2.JeanFrancois wrote:thundre wrote: I made a mistake in my last move.
A5 was the required move.
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 = rows1; i > 0; i) {
for (int j = rows1; 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 viceversa)
*/
int r1 = r0;
for (int r = r01; 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 = c01; 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 * (r0r1));
usedSquares ^= leftBits;
usedSquares ^= leftBits << cols;
int r0Max = rowMax[r0];
String r0Name = rowName[r0];
for (int r = r0; r > r1; r) {
rowMax[r] = rowMax[r1];
rowName[r] = rowName[r1];
}
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 >> (c0c1);
usedSquares ^= leftBits;
usedSquares ^= leftBits << 1;
int c0Max = colMax[c0];
String c0Name = colName[c0];
for (int c = c0; c > c1; c) {
colMax[c] = colMax[c1];
colName[c] = colName[c1];
}
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 " + (t1t0) + " ms");
System.exit(0);
}
}

 Posts: 29
 Joined: Wed Feb 13, 2013 10:32 pm
Re: New game : Plus_one
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.
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.