Sanity Check for a newbie

If it is ready for testing come and grab me sometime when I'm world to test the play system, and even to test the game logic if you want.

This is something I've put on my list of "Cool things I could do in SL" and I'm happy to see that someone has actually taken on a project as complex as this instead of shoving it on some utopian to-do list. I'm pretty new to SL and have only slightly touched the building/scripting part of it, but I do have some programming and 3d modelling experience outside of it.

Anyway, I'm a fairly consistent amateur go player (think I'm currently rated at 9 kyu by my federation - equivalent to 5 kyu by japanese standards) and I'd love to see this project develop into an actual playable board.

I'd happily provide any assistance, although I'm not really sure about how I could help given my limited SL "developing" abilities. I am quite knowledgable of the game itself though and could help out with the more obscure parts of the game, such as the different scoring rules (ING and traditional japanese), how to better handle the post-game sequence (removing end of game dead groups, identifying Seki, counting and scoring), identifying three-ko rule, even providing you with some go life and death problems to display on the board so it can be used solo.

Anyway, if you're interested IM me IW.

Clearly you'd thrash me, even if I weren't way out of practice. Basic mechanics of group capture are pretty much done now, though my group-detection is recursive and I worry about it hitting some sort of stack limit with big groups on a full size game. I was also petrified the first time I tested it that it'd go into runaway recursion and crash the sim, seems okay so far though

I remember there being not too much difference between the scoring methods? The method I've always used is that your score is your captured stones plus your territory owned at the end of the game.

Just looked up triple ko. Never ever happened in a game I've played. I won't worry
about it too much.

Seki I'd forgotten about. I've just looked it up, and unfortunately it seems the easy way to score it (seki eyes count) does not match with the territory scoring I'm used to. Hmm. I don't want to even begin to think about how to algorithmically decide if an eye is a seki eye or not.

The life or death problems for solo play are an interesting idea, but I won't start thinking about that yet. I'm going to need to do handicaps too aren't I.. (though I guess just agreeing to pass could work for that).

What have I got myself into ..

A good project you could easily work months improving, but then, board games are very much in demand.

Out of curiosity, how are you doing the recursion algorithm for capturing? Originally, back when I'd considered doing this, I'd seen myself writing an algorithm that would attempt to form a "loop" of select colored pieces... but decided against it and moved along with other projects that were engrossing at the time.

However, you should only be concerned about hitting the stack limit if you're storing hundreds of variables in a single script (or long ones). The way I see it, you shouldn't be having to store more than score for both players, board control (black and white), and 19 variables (or one large one) to store piece locations, plus roughly five to ten local variables depending on how you work it. That shouldn't stack heap, and it definitely won't crash a sim unless you're really working hard at it.

The only reason I could see you run out of script memory, then, is if you're storing values for your capture algorithm. Not sure if you have to do even that - but before I get into how I would do it this time around, I'd be interested in how you decided to. You could also split up various functions into different, linked scripts, to use a larger script buffer as well, much like what I like to call Xylorcode.

By the way, Samhain, something like this actually has three states, not two, so using 0 or 1 wouldn't work too well (you'd need a state for black, white, and empty). You'd need two bits, not one.

To be fair to Samhain, he did suggest having two separate bitfields. One for occupancy or not, one for colour (if occupied), so giving you the three states needed. I'm actually being slightly sneaky and using four states, having a ring of occupied but not in black or white squares around the edge of the board to help with capture detecting, rather than having
to deal with messy bounds checking at edges.

My algorithm is something like this, in rough pseudocode as I'm at work and can't
log on to Second Life from here

for each position on the board surrounding a newly played piece which contains
a stone of the opposite colour {

    initialise a list of pieces in group to empty.
    initialise a number of liberties found to 0.
    call recursive group_detect for position;
    if liberties is > 1 - do nothing.
    if liberties is 1 - given an Atari warning.
    if liberties is 0 {
       add size of 'list of piecees in group' to player's score.
       remove each piece that's in the list from the board.
    }
}

where the group_detect function does something like {
  if liberties > 1 - exit.
  if position already in pieces in group list - exit 
  add position to pieces in group list.
  for each position around current position {
    if surrounding position is empty, increase liberties by 1.
    if surrounding position is other colour stone (or stone around edge of board) do nothing.
    if surrounding position is same colour, call group_detect again on it.
  }
}

I also always pass in the direction I've come from, to avoid checking back the stone
I've just come from, for an added bit of efficiency.

It's not the most efficient algorithm possible, a non-recursive solution would probably be better, but then it'd also be far more complex to code, whereas I got the above working in an hour last night The only things passed into the recursive function are three integers, for coordinates and direction of checking, to keep the stack usage at a minimum, rest are global.

Jonathan (who is bored senseless at work hence wittering on on here)

Interesting. I do believe you've coded it as I'd considered doing originally! Neat.

However, I have a more efficient solution for you that would not involve a recursive list of values. The list method will most definitely stack heap to hell in large groups.

I would do something like this:
Upon placing a piece, check pieces next to placed piece for same color.
If same color, do recursion doing a min/max value approach where:
- Minimum and maximum values for recursion are established by how many connecting pieces we have on one axis
- If none of our pieces are found within the upper and lower bounds, and within appropriate distance of our current piece values, we have a liberty
- If a liberty is found, make appropriate min/max adjustments
- If all pieces between upper and lower bounds are our color, we've hit the end of a group - exit.


That way, you're storing at most 19 entries in your recursive list. May have problems though, since I'm not a big Go player, so feel free to pick it apart.

If I'm reading you right, that won't work, it wouldn't handle a group shaped something like

 
    xxxxx
    x   x
    

or any group that was in some way convex in shape for that matter. But I might not be reading you right ...

Edit: Ahem, I mean concave of course, not convex ...

So Jonathan, how quickly does your algorithm run? I recently had to do a similar recursive algorithm for a game I'll be releasing soon, and the first time I implemented it, the algorithm tended to take a minute or more to run Not conducive to gameplay, really. I did speed it up... but this kind of thing is exactly what SL is worst at, and the most efficient algorithm I could come up with was still 20-30 seconds in the worst case.

Yours actually seems like it should be much more efficient than what I had to do for my game... I didn't realize you were only going to have to find a liberty and then get out. I suppose this thing won't keep warning them of an atari that they haven't attended to, but that's the way RL Go works, so...

I'll let you know once I've tested it with a group size of bigger than 2 ..

Not necessarily. While I don't have the patience to draw it all out, one by one, you would check the next space something like this:

 
    xxxxx
   123 123
    

... and loop until they converge, you find one or more holes, or run off the board. The only problem I can think of is if you have more than one path (same with a recursive "perimeter" detection), as you would potentially need to trace several paths.

... something tells me that either way you work this, you're going to end up using more than one script buffer for the final version. I'd like to see this in action sometime, though.

Bah, none of you spotted the flaw in my algorithm. It mostly works, but a single liberty can be counted multiple times if it's bordered by more than one stone in the group, so the 'atari' warning doesn't always work when it should.

Speedwise, it does slow down with larger groups - tried with group sizes up to 10 or 12 or so, but not horrendously so, still less than a second delay I think.

Have I mentioned yet i'm thinking about building a go board as well?
My understanding of the game is pretty basic. I know how to play but i don't know most of the terms off the top of my head. I'm not a very good player. My interest is the design and building of the scripts.

My thought was to have the boader broken up into regions. Probably 16 regions.
Region specs:
5x5 grid
linked messages are used to tell neighboring regions that an update has occured to a boarder structure.
Then name of prim with the region script is contained in is used for storing data about the edges of the region.
the string is a list containing hexstrings. Each location is described by 3 hex characters.
on an update this can send out structure merger commands. This will result in all regions recalculating there structures if they contain 2 or more of the structures being merged. Structure updates are sent to the global structure handler

character 1
bit 0 - black
bit 1 - white
bit 2 - reserved
bit 3 - reserved
characters 2 & 3
global structure identifier

Global structure handler:
when a stone is placed the structures it effects are updated.
a peice that forms a structure that crosses a boarder is asigned a unique structure number.
on a structure merge a new identifier is sent replacing all the old ones.
two lists, one with structure identifiers, the other with hex strings
hex string format:
2 bits structure color.
9 bits stones in structure.
9 bits for single liberties.
2 hex char per list entry of structures this structure depends on. (we make structures of liberties)


definately nasty stuff.

Ignore the atari warning for now. It is NOT a game rule. Its just a nicety players use when playing casually. You won't see atari warning at a go tournament unless its a very relaxed one. Think of it as the equivalent of announcing a queen check or a rook check in chess.

Well it's already coded, so ...
But yes, I wasn't sure whether or not it should be automated really. For experienced players, it's not an issue as they're very unlikely to not notice anyway, but it might be helpful for beginners.