NOTE: Not specific to the GNUgo game. If you don't take extraneous queries, just trash this now, and save time.
I'm developing an online Go game using Flash, actionscript 2.0. Until recently, I've been primarily a designer, and not a programmer, my programming expeirence is limited to php, java, db management, and extensive, extensive actionscript development.
I'm including game review, realtime online play, automatic online saving. In terms of gameplay, I've successfully programmed placement, capture, and prevented any illegal moves including the rule I can't remember the name of (it prevents the board from looking the same way twice in the one-piece capture).
The problem is that to do this, I've built an algorithm that works roughly like so:
place { while build = true { (check all piece positions for a match to the placed pieces potential liberties)
if (there's a friend) {build = true & go to a sub function to add the piece to the structure} if (there's an enemy or an edge) {subtract a liberty} } }
The sub function adds to the structure. On the initial placement, this function solely builds, ignoring enemy pieces, until it has a map of the structure. Then it uses this same algorithm to make sure that structure has at least one liberty. Then it checks to see if the placed piece has any ajoining enemy pieces; if so, it runs the same function to build structures for all those pieces, then runs the liberty check (same function) on each of the threatened sturctures, breaking the loops immedietly on open verts.
In my head, this seems fine. But the process of checking all the pieces so far against every piece in a structure starts producing, at say, 30, something on the order of
initial = 30 assume 3 piece structure;
30 * 3 assume two six piece sturctures potentially threatened 30 * 12
for 30 * 16 cycles of a fairly complex alogrithm. And that's just an idiot's guess.
It's not a problem per se, but the game starts to lag for al;most two seconds before determining legality, a mere 100 or so moves in.
There's got to be a better way?
I've reviewed some C solutions to the issue, but I don't know C syntax, so it's a bit of a hack job when I try to emulate it.
Would love some help. Name your required _expression_ of gratitude (other than money).