473,320 Members | 2,029 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

Go Simulation - Mark dead stones

7
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)
May 28 '08 #1
10 2159
pbmods
5,821 Expert 4TB
Heya, j0k3r. Welcome to TSDN^K^K^K^KBytes!

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?
May 29 '08 #2
j0k3r
7
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 :)
May 29 '08 #3
pbmods
5,821 Expert 4TB
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:

Expand|Select|Wrap|Line Numbers
  1. function traverse( $node )
  2. {
  3.     if( is_null($node) )
  4.     {
  5.         return;
  6.     }
  7.  
  8.     doSomethingTo($node);
  9.     traverse($node->left);
  10.     traverse($node->right);
  11. }
  12.  
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).

Expand|Select|Wrap|Line Numbers
  1. function checkSpot( $index, $myColor )
  2. {
  3.     global $theBoard;
  4.  
  5.     // The rules:
  6.     // - If this spot is empty, we're still alive.
  7.     // - If this spot is an edge or enemy piece, this path is dead.
  8.     // - If this spot is a friendly piece, continue down the path.
  9.  
  10.     if( isset($theBoard[$index]) and is_null($theBoard[$index]) )
  11.     {
  12.         // Empty spot.  Life is good.
  13.         return true;
  14.     }
  15.     elseif( empty($theBoard[$index]) or $theBoard[$index] != $myColor )
  16.     {
  17.         // Edge of the board or enemy piece.  Life is over.
  18.         return false;
  19.     }
  20.     else
  21.     {
  22.         // Friendly piece.  Continue pathing.
  23.         return
  24.                 checkSpot($index - 1, $myColor)
  25.             or  checkSpot($index + 1, $myColor);
  26.     }
  27. }
  28.  
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:
Expand|Select|Wrap|Line Numbers
  1. if( true or doSomethingUnexpected() ) { }
  2.  
In the code above, doSomethingUnexpected() will never get executed because PHP hits the true first and realizes that no matter what doSomethingUnexpected() 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 doSomethingUnexpected().

Similarly:
Expand|Select|Wrap|Line Numbers
  1. if( false and doSomethingUnexpected() ) { }
  2.  
Since (anything && false) is always false, doSomethingUnexpected() never gets executed in the code above.

So going back to the recursion in the checkSpot() method:
Expand|Select|Wrap|Line Numbers
  1. return
  2.                 checkSpot($index - 1, $myColor)
  3.             or  checkSpot($index + 1, $myColor);
  4.  
Let's say our board looks like this:
Expand|Select|Wrap|Line Numbers
  1. [ ]
  2. [o] = friendly
  3. [x] = enemy
  4. [ ][ ][x][o][o][o][ ][ ]
  5.  
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');
Expand|Select|Wrap|Line Numbers
  1. .        \ /
  2. [ ][ ][x][o][o][o][ ][ ]
  3.  
$theBoard[3] is a 'o' which means we have to go to the third option:

Expand|Select|Wrap|Line Numbers
  1. // Friendly piece.  Continue pathing.
  2. return
  3.                 checkSpot(2, 'o')
  4.             or  checkSpot(4, 'o');
  5.  
So first we run checkSpot(2):
Expand|Select|Wrap|Line Numbers
  1. .     \ /
  2. [ ][ ][x][o][o][o][ ][ ]
  3.  
$theBoard[2] is a 'x', which results in the second option:
Expand|Select|Wrap|Line Numbers
  1. // Edge of the board or enemy piece.  Life is over.
  2.         return false;
  3.  
So checkSpot(2) returns false, which means that we go back to checkSpot(3) (which hasn't returned yet).

Now it looks like this:

Expand|Select|Wrap|Line Numbers
  1. // Friendly piece.  Continue pathing.
  2. return
  3.                 false
  4.             or  checkSpot(4, 'o');
  5.  
Since (false || true) is true, PHP can't short-circuit here. So it has to execute checkSpot(4):

Expand|Select|Wrap|Line Numbers
  1. .           \ /
  2. [ ][ ][x][o][o][o][ ][ ]
  3.  
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.
May 30 '08 #4
pbmods
5,821 Expert 4TB
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:
Expand|Select|Wrap|Line Numbers
  1. 1:
  2. [ ]  [x]  [o]  [ ]
  3. [ ]  [o]->[o]  [ ]
  4. [o]  [o]  [o]  [ ]
  5.  
  6. 2:
  7. [ ]  [x]  [o]  [ ]
  8. [ ]->[o]  [o]  [ ]
  9. [o]  [o]  [o]  [ ]
  10.  
  11. 3:
  12. [ ]  [x]  [o]  [ ]
  13. [ ]  [o]  [o]  [ ]
  14. [o]->[o]  [o]  [ ]
  15.  
  16. 4:
  17. [ ]  [x]  [o]  [ ]
  18. [ ]  [o]  [o]  [ ]
  19. [o]  [o]->[o]  [ ]
  20.  
  21. 5:
  22. [ ]  [x]  [o]  [ ]
  23. [ ]  [o]->[o]  [ ]
  24. [o]  [o]  [o]  [ ]
  25.  
  26. 6:
  27. [ ]  [x]  [o]  [ ]
  28. [ ]->[o]  [o]  [ ]
  29. [o]  [o]  [o]  [ ]
  30.  
  31. 7:
  32. [ ]  [x]  [o]  [ ]
  33. [ ]  [o]  [o]  [ ]
  34. [o]->[o]  [o]  [ ]
  35.  
  36. 8:
  37. [ ]  [x]  [o]  [ ]
  38. [ ]  [o]  [o]  [ ]
  39. [o]  [o]->[o]  [ ]
  40.  
  41. .
  42. .
  43. .
  44.  
  45. 1,000,058:
  46. [ ]  [x]  [o]  [ ]
  47. [ ]  [o]->[o]  [ ]
  48. [o]  [o]  [o]  [ ]
  49.  
Oops.
May 30 '08 #5
j0k3r
7
wow, i love you :P

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

i'll work on it today :) thx
May 30 '08 #6
j0k3r
7
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:

Expand|Select|Wrap|Line Numbers
  1. [ ]  [o]  [ ]  [ ]
  2. [o]->[o]  [o]  [ ]
  3.  
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)..

Expand|Select|Wrap|Line Numbers
  1. [ ]  [2]  [ ]  [ ]
  2. [1] >[o]  [3]  [ ]
  3. [o]  [o]  [o]  [4]
  4. [z]  [o]  [5]  [ ]
  5. [9]  [o]  [o]  [6]
  6. [ ]  [8]  [7]  [ ]
  7.  
it begins from ">":
- array: 1,2,3

then it goes down:
Expand|Select|Wrap|Line Numbers
  1. . [ ]  [2]  [ ]  [ ]
  2.   [1]  [o]  [3]  [ ]
  3.   [o] >[o]  [o]  [4]
  4.   [z]  [o]  [5]  [ ]
  5.   [9]  [o]  [o]  [6]
  6.   [ ]  [8]  [7]  [ ]
  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:

Expand|Select|Wrap|Line Numbers
  1. . [ ]  [2]  [ ]  [ ]
  2.   [1]  [o]  [3]  [ ]
  3.  >[o]  [o]  [o]  [4]
  4.   [z]  [o]  [5]  [ ]
  5.   [9]  [o]  [o]  [6]
  6.   [ ]  [8]  [7]  [ ]
  7.  
- array:1,2,3,z

AND

Expand|Select|Wrap|Line Numbers
  1. [ ]  [2]  [ ]  [ ]
  2. [1]  [o]  [3]  [ ]
  3. [o]  [o] >[o]  [4]
  4. [z]  [o]  [5]  [ ]
  5. [9]  [o]  [o]  [6]
  6. [ ]  [8]  [7]  [ ]
  7.  
- array:1,2,3,z,4,5

AND

Expand|Select|Wrap|Line Numbers
  1. [ ]  [2]  [ ]  [ ]
  2. [1]  [o]  [3]  [ ]
  3. [o]  [o]  [o]  [4]
  4. [z] >[o]  [5]  [ ]
  5. [9]  [o]  [o]  [6]
  6. [ ]  [8]  [7]  [ ]
  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 :)
May 31 '08 #7
j0k3r
7
[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($theBoard[$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($checked);

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..
Expand|Select|Wrap|Line Numbers
  1. Friendly piece. Continue pathing.
  2.  
  3. Array
  4. (
  5.     [0] => 1,1
  6. )
  7.  
  8. Friendly piece. Continue pathing.
  9.  
  10. Array
  11. (
  12.     [0] => 1,1
  13.     [1] => 2,1
  14. )
  15.  
  16. Friendly piece. Continue pathing.
  17.  
  18. Array
  19. (
  20.     [0] => 1,1
  21.     [1] => 2,1
  22.     [2] => 3,1
  23. )
  24.  
  25. Edge of the board or enemy piece. Life is over.
  26.  
  27. Array
  28. (
  29.     [0] => 1,1
  30.     [1] => 2,1
  31.     [2] => 3,1
  32. )
  33.  
  34. Friendly piece. Continue pathing.
  35. .....
  36. ......
  37.  
May 31 '08 #8
pbmods
5,821 Expert 4TB
Try adding this line right after the opening curly brace for your function:

Expand|Select|Wrap|Line Numbers
  1. echo "checkSpot( $ind_X, $ind_Y, $myColor )<br />";
Incidentally, if either of the 'colors' is 0, then you'll also need to change:
Expand|Select|Wrap|Line Numbers
  1. elseif( empty($theBoard[...]) )
to
Expand|Select|Wrap|Line Numbers
  1. elseif( ! isset($theBoard[...]) )
Jun 1 '08 #9
j0k3r
7
It only works for the first set of coordinates.. let's say the board is:

Expand|Select|Wrap|Line Numbers
  1. 1    1    1    0
  2. 0    0    2    0
  3. 0    0    2    0
  4. 0    0    0    0
  5.  
(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:
Expand|Select|Wrap|Line Numbers
  1. checkSpot( 1, 1, 1 )
  2. Friendly piece. Continue pathing.
  3.  
  4. Array
  5. (
  6.     [0] => 1,1
  7. )
  8.  
  9. checkSpot( 0, 1, 1 )
  10. Edge of the board or enemy piece. Life is over.
  11.  
  12. checkSpot( 2, 1, 1 )
  13. Friendly piece. Continue pathing.
  14.  
  15. Array
  16. (
  17.     [0] => 1,1
  18.     [1] => 2,1
  19. )
  20.  
  21. checkSpot( 1, 1, 1 )
  22. Already checked. Over.
  23.  
  24. checkSpot( 3, 1, 1 )
  25. Friendly piece. Continue pathing.
  26.  
  27. Array
  28. (
  29.     [0] => 1,1
  30.     [1] => 2,1
  31.     [2] => 3,1
  32. )
  33.  
  34. checkSpot( 2, 1, 1 )
  35. Friendly piece. Continue pathing.
  36.  
  37. Array
  38. (
  39.     [0] => 1,1
  40.     [1] => 2,1
  41.     [2] => 3,1
  42. )
  43.  
  44. checkSpot( 1, 1, 1 )
  45. Already checked. Over.
  46.  
  47. checkSpot( 3, 1, 1 )
  48. Friendly piece. Continue pathing.
  49.  
  50. Array
  51. (
  52.     [0] => 1,1
  53.     [1] => 2,1
  54.     [2] => 3,1
  55. )
So you see, it only works for checkSpot( 1, 1, 1 ).. why ? *_*
Jun 1 '08 #10
j0k3r
7
OMG i'm so stupid.. the notckd function is totally wrong.. i just had to use "in_array" *_*

(code)

Result:
Expand|Select|Wrap|Line Numbers
  1. checkSpot( 1, 1, 1 )
  2. Friendly piece. Continue pathing.
  3.  
  4. Array
  5. (
  6.     [0] => 1,1
  7. )
  8.  
  9. checkSpot( 0, 1, 1 )
  10. Edge of the board or enemy piece. Life is over.
  11.  
  12. checkSpot( 2, 1, 1 )
  13. Friendly piece. Continue pathing.
  14.  
  15. Array
  16. (
  17.     [0] => 1,1
  18.     [1] => 2,1
  19. )
  20.  
  21. checkSpot( 1, 1, 1 )
  22. Already checked. Over.
  23.  
  24. checkSpot( 3, 1, 1 )
  25. Friendly piece. Continue pathing.
  26.  
  27. Array
  28. (
  29.     [0] => 1,1
  30.     [1] => 2,1
  31.     [2] => 3,1
  32. )
  33.  
  34. checkSpot( 2, 1, 1 )
  35. Already checked. Over.
  36.  
  37. checkSpot( 4, 1, 1 )
  38. Edge of the board or enemy piece. Life is over.
  39.  
  40. checkSpot( 3, 0, 1 )
  41. Edge of the board or enemy piece. Life is over.
  42.  
  43. checkSpot( 3, 2, 1 )
  44. Edge of the board or enemy piece. Life is over.
  45.  
  46. checkSpot( 2, 0, 1 )
  47. Edge of the board or enemy piece. Life is over.
  48.  
  49. checkSpot( 2, 2, 1 )
  50. Edge of the board or enemy piece. Life is over.
  51.  
  52. checkSpot( 1, 0, 1 )
  53. Edge of the board or enemy piece. Life is over.
  54.  
  55. checkSpot( 1, 2, 1 )
  56. Edge of the board or enemy piece. Life is over.
  57.  
  58. - AND HERE IT STOPS - 
  59.  
Jun 1 '08 #11

Sign in to post your reply or Sign up for a free account.

Similar topics

1
by: Steaming Balturd | last post by:
are there any php based economic simulations out there - not trading games per se, but more like simulating an economy, be it running a business or running a government? All i've been able to...
0
by: Constandinos Mavromoustakis | last post by:
Dear all, first we apologize if you receive multiple copies of this announcement. please see below if you are interested. Thank you in advance....
0
by: Constandinos Mavromoustakis | last post by:
http://agent.csd.auth.gr/~cmavrom -------------------------------------------------- ============================================================================ = 37th Annual Simulation...
0
by: Gus | last post by:
---------------------------------------------------------------------------- ------------------------------------ Call for Papers: 38th Annual Simulation Symposium Part of the 2005 Spring...
23
by: coinjo | last post by:
In "Thirteen Stones" game, two players alternately take 1, 2, or 3 stones from a pile of 13 stones until no stones are left. The last player to pick up a stone is the winner. I need to make a...
0
by: Karatza Helen | last post by:
Our apologies if you have received multiple copies -------------------------------------------------- Call for Papers: 38th Annual Simulation Symposium Part of the 2005 Spring Simulation...
17
by: meital | last post by:
There are three kinds of stones: red,green and blue. Each cell of the array contains one stone. The array needs to be sorted so that all the red stones will come first, then the blue ones and...
2
by: ALi Shaikh | last post by:
I already did the game once and it works but now I need to change it to add a function that will make the computer take player 1 turn and always win. heres the original #include<iostream.h> ...
1
by: Leiram | last post by:
I am trying to write a game where there is 13 stones and you play against the computer to make sure that you don't take the last stone. You or the computer (depending on the turn) is allowed to take...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
0
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.