[Subscribe to Daily Digest] |
Hi,
The reason why it is tricky is because there are about 18^14 possible
permutations of moves.
Anyway, I wrote a program to figure out the game, and after crunching
numbers all night, it came up with a winning move for the case where
_you_ go first.
On your first move, leave 2 pearls on the last row (the one with 6
pearls).
Then, just modify the board in the following code:
---------------------------------------------------------------------
#include <stdafx.h>
#include <iostream.h>
#include <assert.h>
#error Don't compile this
#define EXAMINE_LEVEL 3
void solve_board
(
int *begin_board,
int *sure_win,
int *sure_loss,
int *winning_move_i,
int *winning_move_j,
int level
)
{
int *copy_board;
int i;
int j;
int sum;
int num_possible_moves;
int num_sure_losses;
int opp_sure_win;
int opp_sure_loss;
int opp_winning_move_i;
int opp_winning_move_j;
num_sure_losses = 0;
num_possible_moves = 0;
sum = 0;
*sure_win = FALSE;
*sure_loss = FALSE;
for(i=0;i<4;i++)
{
assert(begin_board[i]>=0);
sum+=(begin_board[i]);
}
if (0==sum)
{
*sure_win = TRUE;
}
else if (1==sum)
{
*sure_loss = TRUE;
}
else
{
copy_board = (int *)malloc(sizeof(int)*4);
for(i=0;i<4;i++)
{
if (level<EXAMINE_LEVEL)
{
cerr << "i : " << i << " level : " << level << endl;
}
if (begin_board[i])
{
memcpy(copy_board,begin_board,sizeof(int)*4);
for(j=(begin_board[i]-1);j>=0;j--)
{
if (level<EXAMINE_LEVEL)
{
cerr << "j : " << j << " level : " << level << endl;
}
num_possible_moves++;
copy_board[i] = j;
solve_board(copy_board,
&opp_sure_win,
&opp_sure_loss,
&opp_winning_move_i,
&opp_winning_move_j,
level+1
);
if (opp_sure_loss)
{
*sure_win = TRUE;
*winning_move_i = i;
*winning_move_j = j;
}
else if (opp_sure_win)
{
num_sure_losses++;
}
}
}
}
free(copy_board);
if (num_sure_losses==num_possible_moves)
{
*sure_loss = TRUE;
}
}
if ((level<EXAMINE_LEVEL) && (*sure_win))
{
cerr << "Intermediate Sure Win at level : " << level << endl;
}
} /* solve_board */
void foo(void)
{
int begin_board[4];
int sure_win;
int sure_loss;
int winning_move_i;
int winning_move_j;
begin_board[0] = 0;
begin_board[1] = 3;
begin_board[2] = 2;
begin_board[3] = 0;
solve_board(begin_board,
&sure_win,
&sure_loss,
&winning_move_i,
&winning_move_j,
0
);
if (sure_win)
{
cerr << endl << "Sure Win" << endl;
cerr << "Winning Move i : " << winning_move_i << endl;
cerr << "Winning Move j : " << winning_move_j << endl;
}
else
{
cerr << "No sure win" << endl;
}
} /* foo */
-----------------------------------------------------------------------
It will give you moves step by step. The computer has no chance.
thanks
Jae
posted by 172.140.4...
No Site Registration is Required to Post - Site Membership is optional (Member Features List), but helps to keep the site online
for all Saabers. If the site helps you, please consider helping the site by becoming a member.