Go Simulation - Mark dead stones

[j0k3r]

Hiya, i'm trying to create a Go (the game) simulation in PHP, the problem is how to mark dead stones.

each stone has some liberties wich are the empty territories nearby, when a group of stones is completly enclosed in stones of another color, is dead.

here the example of what i've done so far:

http://www.k4s.ch/test/sca/test.php

p= player [1: black, 2: white]
x,y = [move coordinates]
&reset to wipe

We can have 4 things near a stone, let's say im black (1):
- another stone of the same color (1)
- another stone of another color (2)
- nothing (out of the board, ie. on the border)
- an empty space (marked as '0')

that's what i was thinking to do.. for instance each time i place a new stone:

[PHP]
function check($x,$y) {
//$array is an array with all the places with some stone ie. [4][5] = 2, [4][6] = 1, ..
global $array;
//$me is the player 1 or 2
$me = $array[$x][$y];
//$near is an array with the north, south, east, west stones (if any)
$near[0] = $array[$x][$y-1];
$near[1] = $array[$x+1][$y];
$near[2] = $array[$x][$y+1];
$near[3] = $array[$x-1][$y];
for ($a=0;$a<=3;$a+ +) {
//how can i re-exec the same function to the next stone ?
if (($near[$a] !== $me) && ($near[$a] !== 0) && (isset($near[$a]))) { OMG there is an enemy stone ! let's see if it has some liberty.. otherwise it's dead! }
}
}
[/PHP]

That's it.. hopefully someone will understand what im talking about :P

In the end how many liberties a stone has is not important.. the important thing is the stone near that one (because if it ain't liberties it dies) O_o

(sorry for the bad english lol)

[pbmods]

Heya, j0k3r. Welcome to TSDN^K^K^K^KByt es!

Grr. That's going to take some getting used to.

Anyway, could you be a little more specific?

What is your code doing that it's not supposed to do? Give an example.
What is your code *not* doing that it is supposed to do?

[j0k3r]

Hi, it's working - just doesn't do what I need :)

It schould be something like this, when I add a stone I'd call this function that:
1) checks the stones nearby (ok)
2) if it finds some enemy stones (ok)
---> that's ok, it does it properly
3) checks the stones near the enemy (that means i need to re-call the same function with the coordinates of the stone it just found)
4) .. it loops between the enemy stones until it comes to a completly sourrended stone, if any, and that group of stone is dead.

Basically what I miss is the idea on HOW to do it :)

[pbmods]

Hm. I remember doing a path-finding assignment in Computer Science 101... shortly before I dropped out. As they say, for every action... :P

Anyway, sounds like you want to do this procedurally, so let's start with basics:

Let's get rid of one dimension. In high school, you learn how to traverse a tree.

It looks something like this:

[code=php]
function traverse( $node )
{
if( is_null($node) )
{
return;
}

doSomethingTo($ node);
traverse($node->left);
traverse($node->right);
}
[/code]

If you were to play Go on a tree (which conjures a funny image, I'm sure), you might do something similar.

There's one little problem, as you'll see later. Go isn't played on a tree; it's played on a board, or more pertinently, a two-dimensional array. But for now, let's keep it simple and pretend we're playing Go on a Stick™ (one-dimensional array).

[code=php]
function checkSpot( $index, $myColor )
{
global $theBoard;

// The rules:
// - If this spot is empty, we're still alive.
// - If this spot is an edge or enemy piece, this path is dead.
// - If this spot is a friendly piece, continue down the path.

if( isset($theBoard[$index]) and is_null($theBoa rd[$index]) )
{
// Empty spot. Life is good.
return true;
}
elseif( empty($theBoard[$index]) or $theBoard[$index] != $myColor )
{
// Edge of the board or enemy piece. Life is over.
return false;
}
else
{
// Friendly piece. Continue pathing.
return
checkSpot($inde x - 1, $myColor)
or checkSpot($inde x + 1, $myColor);
}
}
[/code]

That last return statement is key. Using recursion, we continue pathing until we hit a terminator. Since as soon as we hit *ANY* empty space, we know we're OK, we'll use an 'or' operator to handle the recursion.

PHP uses what's known as 'short circuiting' when it evaluates conditionals.

For example:
[code=php]
if( true or doSomethingUnex pected() ) { }
[/code]
In the code above, doSomethingUnex pected() will never get executed because PHP hits the true first and realizes that no matter what doSomethingUnex pected() could possibly return, the statement will evaluate to true because (anything || true) is always true, so it skips the rest of the conditional, thereby bypassing doSomethingUnex pected().

Similarly:
[code=php]
if( false and doSomethingUnex pected() ) { }
[/code]
Since (anything && false) is always false, doSomethingUnex pected() never gets executed in the code above.

So going back to the recursion in the checkSpot() method:
[code=php]
return
checkSpot($inde x - 1, $myColor)
or checkSpot($inde x + 1, $myColor);
[/code]

Let's say our board looks like this:
[code=text]
[ ]
[o] = friendly
[x] = enemy
[ ][ ][x][o][o][o][ ][ ]
[/code]

Looking at this board, we know that the 'o' pieces are still alive because there's an empty space to the right. But how does PHP know this?

Let's run checkSpot(3, 'o');
[code=text]
. \ /
[ ][ ][x][o][o][o][ ][ ]
[/code]

$theBoard[3] is a 'o' which means we have to go to the third option:

[code=php]
// Friendly piece. Continue pathing.
return
checkSpot(2, 'o')
or checkSpot(4, 'o');
[/code]

So first we run checkSpot(2):
[code=text]
. \ /
[ ][ ][x][o][o][o][ ][ ]
[/code]

$theBoard[2] is a 'x', which results in the second option:
[code=php]
// Edge of the board or enemy piece. Life is over.
return false;
[/code]

So checkSpot(2) returns false, which means that we go back to checkSpot(3) (which hasn't returned yet).

Now it looks like this:

[code=php]
// Friendly piece. Continue pathing.
return
false
or checkSpot(4, 'o');
[/code]

Since (false || true) is true, PHP can't short-circuit here. So it has to execute checkSpot(4):

[code=text]
. \ /
[ ][ ][x][o][o][o][ ][ ]
[/code]

Since $theBoard[4] is a friendly piece, we have to recurse again.

Now this is where it gets tricky, because we have to keep track of which spot we just checked. I've purposely omitted this from the example I gave you above.

[pbmods]

This should get you started. All that you have to do is:

• Adapt this function so that it checks in four directions instead of two, and
• Check to see which spot it just finished checking so that you don't hit infinite recursion. Note that while this is relatively easy to do with one dimension, it gets somewhat tricky when you have to work with two.

For example:
[code=text]
1:
[ ] [x] [o] [ ]
[ ] [o]->[o] [ ]
[o] [o] [o] [ ]

2:
[ ] [x] [o] [ ]
[ ]->[o] [o] [ ]
[o] [o] [o] [ ]

3:
[ ] [x] [o] [ ]
[ ] [o] [o] [ ]
[o]->[o] [o] [ ]

4:
[ ] [x] [o] [ ]
[ ] [o] [o] [ ]
[o] [o]->[o] [ ]

5:
[ ] [x] [o] [ ]
[ ] [o]->[o] [ ]
[o] [o] [o] [ ]

6:
[ ] [x] [o] [ ]
[ ]->[o] [o] [ ]
[o] [o] [o] [ ]

7:
[ ] [x] [o] [ ]
[ ] [o] [o] [ ]
[o]->[o] [o] [ ]

8:
[ ] [x] [o] [ ]
[ ] [o] [o] [ ]
[o] [o]->[o] [ ]

.
.
.

1,000,058:
[ ] [x] [o] [ ]
[ ] [o]->[o] [ ]
[o] [o] [o] [ ]
[/code]
Oops.

[j0k3r]

wow, i love you :P

i see what you mean with tricky.. sure it is :S

i'll work on it today :) thx

[j0k3r]

Ok, now it's a bit i'm thinking about it and while making it search in 4 direction instead of 2 is quite easy (just adding $theBoard[$ind_X][$ind_Y] and 2 other "or" statements, isn't it ?).. making it check every stone is.. a problem.

I mean... if we have this:

[ ]  [o]  [ ]  [ ]
[o]->[o]  [o]  [ ]

let's say it starts from the upper stone, it sets the upper stone "1" just to know we already were there,
then it goes down to the middle one an sets it to "1",
now it will go left or right, in each case the other stone will never be checked because the middle one is a wall between the two.

I think the only solution is to have 4 pointers (->) instead of only 1. In that case if it checks simultaneously 4 directions setting each checked stone at "1", i could set up an array containing all the stones in the border (except for the ones of my color) and in the end when all the stones are "1" just checking the array will tell me if the group is dead (array full of "x" enemy stones) or alive (array with some empty spaces in it)..

[ ]  [2]  [ ]  [ ]
[1] >[o]  [3]  [ ]
[o]  [o]  [o]  [4]
[z]  [o]  [5]  [ ]
[9]  [o]  [o]  [6]
[ ]  [8]  [7]  [ ]

it begins from ">":
- array: 1,2,3

then it goes down:

. [ ]  [2]  [ ]  [ ]
  [1]  [o]  [3]  [ ]
  [o] >[o]  [o]  [4]
  [z]  [o]  [5]  [ ]
  [9]  [o]  [o]  [6]
  [ ]  [8]  [7]  [ ]

here it checks in 4 directions, at this moment
- array: 1,2,3
because i have only friends nearby

now we have somethink like:

. [ ]  [2]  [ ]  [ ]
  [1]  [o]  [3]  [ ]
 >[o]  [o]  [o]  [4]
  [z]  [o]  [5]  [ ]
  [9]  [o]  [o]  [6]
  [ ]  [8]  [7]  [ ]

- array:1,2,3,z

AND

[ ]  [2]  [ ]  [ ]
[1]  [o]  [3]  [ ]
[o]  [o] >[o]  [4]
[z]  [o]  [5]  [ ]
[9]  [o]  [o]  [6]
[ ]  [8]  [7]  [ ]

- array:1,2,3,z,4 ,5

AND

[ ]  [2]  [ ]  [ ]
[1]  [o]  [3]  [ ]
[o]  [o]  [o]  [4]
[z] >[o]  [5]  [ ]
[9]  [o]  [o]  [6]
[ ]  [8]  [7]  [ ]

- array:1,2,3,z,4 ,5
..
..

the key is to make it look at the same time in 4 directions, in each case the array will add the border stones and set the checked friend to 1.. so it's not really a pathway.. but more like a spreading virus XD


Omg, i'm not being clear at all.. i know.. anyway I have no idea on how set up this thing xD

thank you :)

[j0k3r]

[PHP]
function checkSpot( $ind_X, $ind_Y, $myColor )
{
global $theBoard;
//$checked is the array containing the positions "x,y"
global $checked;
//just the html version of print_r
show($checked);
//this returns everytime true (i never see this text)
if (!notckd($ind_X ,$ind_Y)) { echo "Already been there!"; }
// The rules:
// - If this spot is empty, we're still alive.
// - If this spot is an edge or enemy piece, this path is dead.
// - If this spot is a friendly piece, continue down the path.
if( isset($theBoard[$ind_X][$ind_Y]) and is_null($theBoa rd[$ind_X][$ind_Y]) )
{
echo "Empty spot. Life is good.<br>";
return true;
}
elseif( empty($theBoard[$ind_X][$ind_Y]) or $theBoard[$ind_X][$ind_Y] != $myColor )
{
echo "Edge of the board or enemy piece. Life is over.<br>";
return false;
}
else
{
//creating/updating the array
$checked[] = $ind_X.",".$ind _Y;
//remove clones if any..
$checked = array_unique($c hecked);

echo "Friendly piece. Continue pathing.<br>";
//4 directions ?
return
checkSpot($ind_ X - 1, $ind_Y, $myColor)
or checkSpot($ind_ X + 1, $ind_Y, $myColor)
or checkSpot($ind_ X, $ind_Y - 1, $myColor)
or checkSpot($ind_ X, $ind_Y + 1, $myColor);
}
}
//check if not checked
function notckd($x,$y) {
global $checked;
if (!$checked) { return true; }
foreach ($checked as $check) {
if ($check == $x.",".$y) { return false; }
else { return true; }
}
}
checkSpot(1,1,o );

/*
[o] [o] [o] [ ] [ ]
[ ] [ ] [x] [ ] [ ]
[ ] [ ] [x] [ ] [ ]
*/
[/PHP]

Problem is, it won't stop eheheh..

Friendly piece. Continue pathing.

Array
(
    [0] => 1,1
)

Friendly piece. Continue pathing.

Array
(
    [0] => 1,1
    [1] => 2,1
)

Friendly piece. Continue pathing.

Array
(
    [0] => 1,1
    [1] => 2,1
    [2] => 3,1
)

Edge of the board or enemy piece. Life is over.

Array
(
    [0] => 1,1
    [1] => 2,1
    [2] => 3,1
)

Friendly piece. Continue pathing.
.....
......

[pbmods]

Try adding this line right after the opening curly brace for your function:

echo "checkSpot( $ind_X, $ind_Y, $myColor )<br />";

Incidentally, if either of the 'colors' is 0, then you'll also need to change:
[CODE=PHP]elseif( empty($theBoard[...]) )[/CODE]
to
[CODE=PHP]elseif( ! isset($theBoard[...]) )[/CODE]

[j0k3r]

It only works for the first set of coordinates.. let's say the board is:

1	1	1	0
0	0	2	0
0	0	2	0
0	0	0	0

(just using '1' (= o) and '2' (= x), 'cause in the DB is set as INT and i don't want to change it now eheh)

here's the code:

http://www.nomorepasting.com/getpaste.php?pasteid=16366

the result is:

checkSpot( 1, 1, 1 )
Friendly piece. Continue pathing.

Array
(
    [0] => 1,1
)

checkSpot( 0, 1, 1 )
Edge of the board or enemy piece. Life is over.

checkSpot( 2, 1, 1 )
Friendly piece. Continue pathing.

Array
(
    [0] => 1,1
    [1] => 2,1
)

checkSpot( 1, 1, 1 )
Already checked. Over.

checkSpot( 3, 1, 1 )
Friendly piece. Continue pathing.

Array
(
    [0] => 1,1
    [1] => 2,1
    [2] => 3,1
)

checkSpot( 2, 1, 1 )
Friendly piece. Continue pathing.

Array
(
    [0] => 1,1
    [1] => 2,1
    [2] => 3,1
)

checkSpot( 1, 1, 1 )
Already checked. Over.

checkSpot( 3, 1, 1 )
Friendly piece. Continue pathing.

Array
(
    [0] => 1,1
    [1] => 2,1
    [2] => 3,1
)

So you see, it only works for checkSpot( 1, 1, 1 ).. why ? *_*

[j0k3r]

OMG i'm so stupid.. the notckd function is totally wrong.. i just had to use "in_array" *_*

(code)

Result:

checkSpot( 1, 1, 1 )
Friendly piece. Continue pathing.

Array
(
    [0] => 1,1
)

checkSpot( 0, 1, 1 )
Edge of the board or enemy piece. Life is over.

checkSpot( 2, 1, 1 )
Friendly piece. Continue pathing.

Array
(
    [0] => 1,1
    [1] => 2,1
)

checkSpot( 1, 1, 1 )
Already checked. Over.

checkSpot( 3, 1, 1 )
Friendly piece. Continue pathing.

Array
(
    [0] => 1,1
    [1] => 2,1
    [2] => 3,1
)

checkSpot( 2, 1, 1 )
Already checked. Over.

checkSpot( 4, 1, 1 )
Edge of the board or enemy piece. Life is over.

checkSpot( 3, 0, 1 )
Edge of the board or enemy piece. Life is over.

checkSpot( 3, 2, 1 )
Edge of the board or enemy piece. Life is over.

checkSpot( 2, 0, 1 )
Edge of the board or enemy piece. Life is over.

checkSpot( 2, 2, 1 )
Edge of the board or enemy piece. Life is over.

checkSpot( 1, 0, 1 )
Edge of the board or enemy piece. Life is over.

checkSpot( 1, 2, 1 )
Edge of the board or enemy piece. Life is over.

- AND HERE IT STOPS -