Re: [pbmserv-dev] [adam.luter@gmail.com: [werewolf] And now for something completely different]

[Lyman Hurd <lhurd@yahoo.com>]

Two words:

hash table!

Lyman

--- Richard Rognlie <rrognlie@gamerz.net> wrote:

> From the werewolf-users list...
> 
> ----- Forwarded message from Adam Luter
> <adam.luter@gmail.com> -----
> 
> X-DKIM: Sendmail DKIM+DK Filter v0.1.1-0.3.0
> play.gamerz.net j9KHuVDp027999
> DKIM-Signature: a=rsa-sha1; c=nowsp; d=gamerz.net;
> s=dk20040503;
> 	t=1129830991;
> h=Received:X-Authentication-Warning:Received:X-DKIM:
> 	
>
Received:Message-ID:Reply-To:Sensitivity:Importance:To:Subject:
> 	 From:Date:Content-type:MIME-Version:X-MASF:
> 	
>
Content-Transfer-Encoding:X-MIME-Autoconverted:Sender:Precedence;
> b=Y
> 
>
oKnOwK0tGYp0ukqwfG1X6vwlpf2W1QIhZA+SzcwHcXwie0bMAQe1BvNu9zMuCFi
> X-Authentication-Warning: play.gamerz.net: esquire
> set sender to werewolf-users-bounce@gamerz.net using
> -f
> X-DKIM: Sendmail DKIM+DK Filter v0.1.1-0.3.0
> play.gamerz.net j9KHuRxg027978
> Reply-To: adam.luter@gmail.com
> Sensitivity: Normal
> Importance: Normal
> To: PBM <werewolf-users@gamerz.net>
> Subject: [werewolf] And now for something completely
> different
> From: Adam Luter <adam.luter@gmail.com>
> Date: Thu, 20 Oct 2005 17:56:18 +0000 GMT
> X-MASF: 0.00%
> X-MIME-Autoconverted: from base64 to 8bit by
> play.gamerz.net id j9KHuTxg027983
> Precedence: bulk
> 
> Ok, this is off topic and random, but I know at
> least one of you play go, and I know at least a few
> of you program.  So, I'm asking a question:
> 
> I am writing a go engine to a cellphone version of
> go, and I am trying to make the valid rules checks
> quick (say this five times fast).
> 
> Quick primer, in go you place pieces of alternating
> colors, and if any connected same-color group is
> totally surrounded (referred to as having no
> liberties) then it is captured and the stones are
> removed from the board.  Diagonals do not count for
> connecting or surrounding.  The edges of the board
> may be used for surrounding.
> 
> Besides this basic premise, there are only two other
> rules.  One, you may not place a piece such that it
> will be captured (ie because the placement is such
> that it would have no liberties) - unless such a
> move would also capture an enemy group, in which
> case thr enemy group gets captured and yours does
> not.  This often called 'no suicide'.
> 
> Two is known as 'ko' which means eternity.  The idea
> is that you may not place a piece that will bring
> the board back to a previous state.  Usually, this
> is not followed in the strictest sense (which is
> called super-ko) but rather that the board may not
> look like it did at the end of your previous turn.
> 
> Ok so my question relates to a quick ko check.  My
> original (and straightforward) check was to play out
> the move and compare the new board with the board
> from the previous turn.  This works but unless I
> want to do super-ko (by checking all previous boards
> in the same way) there should be a faster check.
> 
> ? b w ?
> b e e w
> ? b w ?
> 
> Ok so the above (? = don't care, b = black, w =
> white, e = empty) is a setup that is potential for
> ko.  (The black and white stones shown can be
> subsituted with the edge of the board.)
> 
> So ko can happen by white playing at the empty left
> square, if black responds (at any later time) at the
> right empty spot he will capture the white piece -
> additionally white may not -immediately- respond at
> the left spot becuase it would be ko.  White must
> play at some other place on the board (or pass). 
> Generally black then has an opportunity to play at
> the left most spot or play elsewhere.  If he does
> not play left only then may white play left, which
> would then make black's play right ko, etc.
> 
> So now that we have an example to look at, here is
> my proposed check logic:
> 
> If and only if, the current move captures a single
> stone and is itself a single stone (is not connected
> to any friendly units) and it is without any
> liberties itself (except the one provided by the
> capture) -then- the captured stone's location is
> marked as a ko move.
> 
> I'm pretty sure this is correct, but I wanted to
> bounce this off some fellow programmers and if they
> happen to know the rules of go, all the better.
> 
> Oh and I think you can extend a regular ko check to
> super-ko by keeping track of previous ko positions,
> but I'm not trying to solve that right now and this
> email is long enouigh.
> 
> Thanks,
>   Gryn
> 
> 
> To unsubscribe, send a message to esquire@gamerz.net
> with
> 	unsubscribe werewolf-users@gamerz.net
> as the BODY of the message.  The SUBJECT is ignored.
> 
> 
> ----- End forwarded message -----
> 
> -- 
>  /  \__  | Richard Rognlie / Sendmail Ninja /
> Gamerz.NET Lackey
>  \__/  \ | http://www.gamerz.net/~rrognlie   
> <rrognlie at gamerz.net>
>  /  \__/ | Creator of pbmserv@gamerz.net
>  \__/    |                Helping reduce world
> productivity since 1994
> 
> 
> To unsubscribe, send a message to esquire@gamerz.net
> with
> 	unsubscribe pbmserv-dev@gamerz.net
> as the BODY of the message.  The SUBJECT is ignored.
> 
>