On Tue, Nov 13, 2007 at 04:10:54PM -0500, John Tromp wrote:
> > > Yes, you can generalize pseudoliberties by extending them
> > > with another field, such that if the (summed) pseudoliberty field
> > > is between 1 and 4, then the other (summed) field will tell you if all
> > these
> > > are coming from a single true liberty.
> >
> > Can you elaborate on this?
>
> Let me pose it as an exercise.
>
> You can assign to each point p a value code[p]
> such that if you add up the code[] of between 1 and 4 points
> (not necessarily different), then from this sum you can tell whether
> all these points are identical, and if so, what that point is.
>
> It's like an error correcting code.
>
> instead of plain pseudoliberties, which sum the value 1 for each
> stone-empty adjacency,
> we can sum these code[]s as well...
I have tried to clean up the exercise a bit:
I have a number domain P={1..400} and a black box. I need the black box to:
(a) Determine if the black box is empty.
(b) Insert and remove numbers \in P, where every number can be in
the box up to four times at once. Every remove corresponds
to a previous insert.
(c) Determine if the black box has only one number \in P inside
(possibly duplicated).
(d) Be as small as possible.
(e) Be as fast as possible - (a), (b), (c) listed in order of
time-sensitivity. Time is also more important than space.
Example black box:
struct blackbox {
int items;
char map[400];
};
#define a(b) !(b.items)
#define b_in(b, i) (b.items++, b.map[i]++)
#define b_rm(b, i) (b.items--, b.map[i]--)
#define c(b)
{ /* optimized only for readability */
for (i in 0..399) {
if (b.map[i] == b.items)
return true;
}
return false;
}
(The example blackbox is completely useless. It would be faster to just
have board bitmap of liberties for every group. And maybe that is simply
the best solution?)
--
Petr "Pasky" Baudis
We don't know who it was that discovered water, but we're pretty sure
that it wasn't a fish. -- Marshall McLuhan
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
