[computer-go] .. if Monte-Carlo programs would play infinitestrong

[Don Dailey]

I've often wondered how I would program a computer to play a game, chess
or go,
if I had perfect information about the game.    How do you make it more
difficult
to win against a fallible opponent?

I assume that in many positions there are more than 1 maximizing move.
I would of
course restrict the computer to those moves (I call those moves "good"
moves in an
idealistic sense and everything else as "bad")   

I guess you would simply steer towards positions where the computer had
lot's of "good" moves and the opponent had very few "good" moves.  

If I were doing this for chess, I might just build an evaluation
function based on trying to maintain the highest legal move count
possible and do a limited depth search - restricting myself of course to
only maximizing or "good" moves.  

In go, I think you would want to keep as many things going on at the
same time as possible, and you would want to increase the number of
interactions on the board.

I am sure a perfect computer could gain a few stones by confusing the
opponent in this way as opposed to playing a straightforward game. 

- Don


On Mon, 2006-11-27 at 11:06 -0800, steve uurtamo wrote:
> > A good point to consider - is "God" actively trying
> > to confuse his
> > opponent and complicate things, or is he simply
> > playing objectively best
> > moves?
> 
> good question.  if his goal is to win with zero
> handicap, all he has to do is pick a branch that
> ends with a win for, say, W.  if he is starting
> from a branch without such a terminus, he has to
> try to move the game into such a branch.
> 
> if it's a handicap game, then the question boils
> down to getting "over" to a winning branch from
> the tree whose initial state is completely
> different -- there are handicap stones on the
> board.
> 
> more likely is that you play with high komi --
> then the goal is to move "over" to a branch
> whose terminus is both a win and is by more than
> "komi" points.
> 
> since there's no guarantee that you can get
> to such a branch, and since it's unlikely that
> the "absolute advantage" of W over B is more than
> 4 stones (or, say, 30 komi), this means that
> you have to try to get your opponent to make a
> mistake that will take you over into one of these
> "> komi + win" branches.
> 
> likely the human opponent will play non-optimally
> in the first few moves.  this will negate some of
> the komi.  any move outside a "win w/o komi"
> branch will take you to a "lose by X w/o komi"
> branch, and "god" will know how to capitalize upon 
> that to make up some more komi.  this isn't enough
> to win the game, however, so "god" has to figure
> out how to maneuver the game over there.
> 
> one approach might be to play moves where the
> greatest number of terminal nodes in that move
> subtree have winning scores in the "> komi" range.
> then you maximize the probability that an error (or
> series of errors) by the human player will result in
> a win for you.
> 
> of course, once you're in a "win by > komi" branch,
> you're done.  you just play it out with perfect
> refutations of every move.
> 
> however, objectively the game is a win for only
> one player at the start, and the only way to
> overcome enough handicap (or komi) is to attempt
> to capitalize on errors (or inefficiencies, which
> in a completely solved game can be considered errors)
> made by your opponent.
> 
> s.
> 
> 
>  
> ____________________________________________________________________________________
> Sponsored Link
> 
> $200,000 mortgage for $660/ mo - 
> 30/15 yr fixed, reduce debt - 
> http://yahoo.ratemarketplace.com
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/