[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [computer-go] Modern brute force search

Yes, you are right.   I did not properly define terms.

I consider any move "best" if it maintains the best possible game theoretic
value at that node.    There are many possible definitions of "best", but 
my trivial proof assumes this one definition.   Let's make sure it's clear:

  1.  If 7 moves draw,  and 3 moves lose and zero moves win,  then any one of
      those 7 drawing moves are considered "best" by my definition.

  2.  If all moves lose, then all moves are "best."

  3.  If one move leads to checkmate in 20 moves, and another leads to checkmate
      on the move,  then BOTH moves are "best" by my definition.  

Even with more  restrictive definitions of "best", I  think it's still
true, using Mark  Boon's terminology, that the "best"  line of play is
still a "tree."  I don't know  if it's possible to prove this from the
opening position but  you can prove it from  arbitrary points near the
end of games.

I also assume that "resign" and  "make draw offer" is not considered a
valid move to play.  But if you want to consider them as just possible
valid moves, then  my proof becomes even easier and  even works in the
draw case since now we can add one move to the list of "best" moves.

- Don







   X-Original-To: computer-go@xxxxxxxxxxxxxxxxx
   Date: Fri, 12 Nov 2004 12:09:48 +0000
   From: joss <joss@xxxxxxxxxxxxxxxxx>
   X-Accept-Language: en-us, en
   X-Enigmail-Version: 0.86.0.0
   X-Enigmail-Supports: pgp-inline, pgp-mime
   Reply-To: computer-go <computer-go@xxxxxxxxxxxxxxxxx>
   Sender: computer-go-bounces@xxxxxxxxxxxxxxxxx
   X-Scanned-By: MIMEDefang 2.42

   -----BEGIN PGP SIGNED MESSAGE-----
   Hash: SHA1

   Hi,

   Whilst I agree with almost everything that you have been saying so far,
   ~ I just wanted to pick up on this point in your contradiction proof (and
   I am not a chess/go programmer, so could well be missing something):

   |  Even though  blacks 20 responses all  lose, white must  still have a
   |  response for  each of  those 20 moves.   That means we  have already
   |  branched to 20 different lines of play, all of them based on perfect
   |  play by both sides.

   This depends on your definition of "best line". Assuming that white can
   always win, there are two sets of possibilities for this definition:

   1) White wins and so black has no real "best move", (s)he therefore
   plays as well as possible, but always knowing that a loss was inevitable
   assuming that white plays perfect responses.

   This would be a good strategy if there is a chance that white doesn't
   know the correct response to all possible black moves. If not, black may
   as well resign after the first move and so the single best line is
   simply: White moves, black resigns.

   2) Black does have a "best move". This could be based on a criterion
   such as making the game last as long as possible before a loss, or
   having as much material as possible when the game finishes (or some
   other criteria). In this case, black also has a defined set of "best
   moves" to follow, resulting in a single line of play (aside from some
   coincidental cases where there _are_ equal results, however the
   branching factor would be much, much lower).

   Without either of these considerations, how can you define "perfect
   play"? The only way that this could fit would be if all of black's 20
   response moves have exactly equal outcomes, which also seems unlikely.

   I know that you picked up this point by considering the case for only
   one line that results in a draw, all others resulting in a white win,
   but this extends beyond that situation.

   This isn't really disagreeing with (any of) your point(s), I'm just
   interested in your thoughts on this, and am happy to learn :o)

   Joss
   -----BEGIN PGP SIGNATURE-----
   Version: GnuPG v1.2.6 (GNU/Linux)
   Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

   iD8DBQFBlKgLLCkMByTrb38RAhFqAJ9bD2XlhQlEKtxxIfUNSUfTQOTa3gCfQLYN
   eVXbnlL51+P+PtKDT67a7pg=
   =WKzu
   -----END PGP SIGNATURE-----
   _______________________________________________
   computer-go mailing list
   computer-go@xxxxxxxxxxxxxxxxx
   http://www.computer-go.org/mailman/listinfo/computer-go/

_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/