how does go compare with chess?
Darse Billings
>I'm a chess player (around 2000) and am currently learning go. I'm finding
>it a bit difficult in that all the pieces are the same. There is no variey
>and it'll take some getting used to.
This reminds me of an analogous chess story, supposedly based on an actual
event... While sitting on stage in front of an audience, a world-class
grandmaster executes a brilliant attack leading to checkmate. After the
applause dies down, a woman approaches the grandmaster, and says excitedly,
"That was a wonderful performance! But tell me, how do you remember how
all those different pieces move?"
Somewhat astonished, the grandmaster replies "I don't really know...".
> Anyone care to comment on whether
>skills are transferable? In both directions? What sort of time limits are
>used in go? Do good chess players make good go players, and vice versa?
I have been playing chess since I was a kid, and became a fairly decent
player after investing several hundred hours on the game...
It took me about three weeks of learning Go to discover that it was a much
better game -- broader in scope and richer in strategy. Once you begin to
see how groups of stones relate to each other, certain patterns will
emerge and your understanding and appreciation for the game will increase
rapidly.
Go will probably be most enjoyable to the strategic, positional type of
chess player. While the tactics in Go can be much more complicated than
chess, Go is usually played at a higher, more intuitive, level. Concepts
like "shape" and "efficiency" generally take precedence over direct
threats and parries. So if you are a wizard at combinations, and enjoy
computing variations, then Go may not be your cup of tea. Even so, there
are aggressive and dynamic styles of playing Go which may suit you fine.
I believe my chess abilities helped me to learn Go very quickly (I was
able to defeat three different 8 kyu players after playing only half a
dozen serious games). This was not a direct transference of skills, but
an application of certain intangible qualities, such as discipline of
thought and the ability to focus and concentrate. Despite my affinity
and appreciation for Go, I decided to not pursue it (at least for now).
I am more interested in a wide variety of challenging games, some of
which have certain tangible advantages (money :-) over chess or Go...
Incidentally, in the same way that learning Go can help your chess game,
mastering Poker or backgammon can help sharpen your "gambling instincts"
for chess and Go. There *is* an element of randomness in chess and Go,
because the game is played between imperfect opponents; and knowing how
to distinguish between a good risk and a bad risk can be worth a lot,
even in a game of "pure skill".
Cheers, - Darse.
--
Go is better than Chess. Poker is more lucrative. Sex is more fun.
Darse Billings, 7 kyu; 2065 CFC; meaningless IRC sb/hand ratios:
(rayzor on IRC) Hold'em +0.22 ; HiLo Omaha +0.76
Chris Sanderson
elastic game. The board can change size without changing the
game. The standard go board is 19x19, but you could use a
smaller or larger board. Training boards are 13x13 I think. To
compare chess with go, you have to state the size of go board
being used. Checkers is the same way. You can change the size of
the board, increase the number of pieces without changing the
game. Chess is stuck on its 8x8 board. You couldn't play chess
on something different.
Go and checkers are too slow. It takes a long time to develop
the pieces and create strategy for the game. For this reason,
computers have a hard time with go and large sized checkers.
Chess used to be like this, pawns moved one square always, there
was no castleing. Then, chess was also slow and took time to
develop. But then chess changed into the current rules of
castleing, 2 square pawn moves and en passant capture. Chess
requires more attention and discipline that go, and its speed is
not a problem, its a feature.
-- Chess is better than go.
Michael Richard
: The consequenses of a bad move in go are far smaller than in
: chess. A person ahead tends to stay ahead even after a weak
: move. A person ahead would have to *keep on blundering* to lose.
This may be true for people who don't really know how to
play, but becomes less and less true as you become stronger.
: Chess is still better than go.
I personally feel it is the height of folly to consider
any game better than any other unless you state up front
a rigorous set of criteria. Chess and Go are both fine
games, but so are football, strip poker, and mumbly-peg.
veg
Lee Schumacher
>Go and checkers are too slow. It takes a long time to develop
^^^^^^^^
>the pieces and create strategy for the game. For this reason,
[munch]
>castleing, 2 square pawn moves and en passant capture. Chess
>requires more attention and discipline that go, and its speed is
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>not a problem, its a feature.
Huh ? overlooking the obvious ignorance of your *opinions*, aren't
you contradicting yourself ? Go is slower than chess *and* it requires
*less* concentration ? What are go players doing with all that extra
time spent developing ? whistling dixie ?
>-- Chess is better than go.
Well, that's your opinion.
Lee.
Anthony Ragan
mric...@cie-2.uoregon.edu (Michael Richard) writes:
>
>: Chess is still better than go.
>
> I personally feel it is the height of folly to consider
> any game better than any other unless you state up front
> a rigorous set of criteria. Chess and Go are both fine
> games, but so are football, strip poker, and mumbly-peg.
>
> veg
But I wouldn't recommend strip mumbly-peg. :)
--Anthony
ecz...@mvs.oac.ucla.edu -OR- Iris...@aol.com
Rune Chia Pet of Ernalda, Snotling in Chief
David Forthoffer
: The consequenses of a bad move in go are far smaller than in
: chess. A person ahead tends to stay ahead even after a weak
: move. A person ahead would have to *keep on blundering* to lose.
In go, a move that loses a lot of points can lose the game, and
a move that loses a few points usually doesn't.
In chess, a move that blunders a piece can lose the game, and
a move that creates an unneccessary weakness usually doesn't.
I suspect you have no idea what constitutes a slightly weak move
in chess.
: I play these games I worry mostly about the long term prospects of
: my move without concern for the immediate impact. This is
: because one move won't have much immediate impact. In chess,
: long term strategic thinking is required. But in addition, the
: player must consider the immediate tactical situation and
: prevent any quick attacks. This two tiered nature of chess,
: versus the one for go, is what I was talking about.
When I play go, I worry a lot about the strategic impact of my move
and a lot about the local impact. Go is two-tiered in my mind.
Even if it's not, why would a one-tier nature make go better than go?
: Chess is still better than go.
Chess is still has many similarities and differences compared to go.
--
David Forthoffer (1k* 2260 USCF) NEC Technologies Printer Division
dav...@lpd.sj.nec.com 110 Rio Robles, San Jose CA 95134
"I'm not speaking for NEC unless I explicitly say so."
ToeKnee
Sanderson) wrote:
> The previous poster believes that because a game is slow, the
> player must concentrate harder and longer because of all the
> moves required to develop the game.
No, he was explaining that since go is more complicated, it requires
more time to think and, consequently, more concentration. I think that
'concentrating harder' is a notion that has relevance only if you can
somehow quantify the 'density' of thought. This being the case, let's
just assume that the length of time that a player concentrates (relative
to other games, let's say) is the only important variable to consider when
analyzing 'levels' of concentration in a game.
>...I was refering to the way small errors in chess are pounced upon quickly,
> and how hard it is to make the right move. Concentration is needed
because the
> consequences of an error in chess is far higher than in other games. The speed
> of chess is what gives it this edgy quality.
I certainly do agree with your description of how even the smallest
error can lead to disaster in chess, and that you really need to focus
your attentions on the game in order to avert calamity. However, isn't
this true of most things? And why can't this be true for go?
It sounds like you have a very 'chess-centric' view of games.
Certainly, the consequnces of error in chess is high, but this is a
perception that is based on a level of understanding about chess which is
deep. Possibly, if you were to have a similar deep perception of go, you
would also have the capacity to recognize that the consequences of an
error in go, even a small one, are also great.
Go is a game that you can win by one point, and if you make an error
that is valued at one point, you could lose the whole game. Think about
it. Think about the level of concentration you have to maintain to assure
yourself that you aren't losing a point here, a point there, how careful
you have to be to avoid playing sequences which turn out to leave you a
point down in the denouement. This always leaves me feeling 'edgy'.
> In go, no pieces move at all, it's a static game. It's modern chess that
> has overcome these problems (which other games don't even think
> are problems) and works well.
Just because 'no pieces move' in go doesn't mean that it is a static
game. Open your mind a little.
> The consequenses of a bad move in go are far smaller than in
> chess. A person ahead tends to stay ahead even after a weak
> move. A person ahead would have to *keep on blundering* to lose.
How did this person get ahead in the first place? Luck?
If a person is ahead in a game of chess and they make a weak move, do
they automatically lose?
Are you trying to say that it really doesn't matter *that much* if you
make a bad move in go? I wish I could have such a carefree appraisal of
my own game; instead, I worry about every mistake I make, and
subsequently try to improve my game so those tiny consequences of my bad
moves don't force me to consistently take handicap stones from stronger
players who don't make those tiny, inconsequential mistakes as often as I
do.
Give me an example of a bad move in go that has a smaller consequence
than an analagous move in chess, and then I'll show you how a person ahead
can lose after a single 'weak' move in go. It is not wise to
overgeneralize.
> To answer the question, yes, they are whistling dixie. When I
> play these games I worry mostly about the long term prospects of
> my move without concern for the immediate impact.
Then I would say you are an unskilled go player, with very little
understanding of the game. I don't think you are fit to argue a pro/con
case of go vs. chess.
> This is because one move won't have much immediate impact.
Duh! Are you kidding? The group isn't in atari, right?
> In chess, long term strategic thinking is required. But in addition, the
> player must consider the immediate tactical situation and
> prevent any quick attacks. This two tiered nature of chess,
> versus the one for go, is what I was talking about.
Ok, so chess is two-tiered. Big deal. Go is infinitely-tiered.
> Chess is still better than go.
Opinions are not facts... and a weakly argued opinion is certainly won't
win others to your viewpoint. Try arguing your point again after you
become a dan-level go player, or stop trying to discuss something you
obviously don't understand.
--
ToeKnee, 2d* toe...@teleport.com
Mason House Co-Op
Chris Sanderson
cconcentration*.
The previous poster believes that because a game is slow, the
player must concentrate harder and longer because of all the
whisting dixie?" These two things are not a contradiction but
rather go together. I was refering to the way small errors in
chess are pounced upon quickly, and how hard it is to make the
right move. Concentration is needed because the consequences of
an error in chess is far higher than in other games. The speed
with no castleing and 1 move pawns. Those are he old rules. Its
slow, and to be honest feels a good deal like checkers. In go,
no pices move at all, its a static game. Its modern chess that
has overcome these problems (which other games don't even think
are problems) and works well.
The consequenses of a bad move in go are far smaller than in
chess. A person ahead tends to stay ahead even after a weak
move. A person ahead would have to *keep on blundering* to lose.
To answer the question, yes, they are whistling dixie. When I
play these games I worry mostly about the long term prospects of
my move without concern for the immediate impact. This is
because one move won't have much immediate impact. In chess,
long term strategic thinking is required. But in addition, the
player must consider the immediate tactical situation and
prevent any quick attacks. This two tiered nature of chess,
versus the one for go, is what I was talking about.
Chess is still better than go.
John Katic
>
>Chess is still better than go.
>
I am curious to know how well you play Go (ie rank) and how well
you play chess (ie. rating).
You conclusion :chess is better than Go shouls be re-phrased to "
I prefer Chess to Go". Chess is not better, nor is Go better.
I my humble opinion, I will tell you why I like Go. In chess, there is
no degrees of winning, you win or lose (exclude draws). You can lose a
game in chess without "blunders" or you can lose by a gross blunder.
In the end, it is all the same ultimate CHECKMATE.
Go is like an election campaign. Yes, you still can lose the election
but you can make it a close race. There are degrees of losing and degrees
of wiining. Also, the handicap system in Go allows for a greater variance
in player strengths. Giving, say 6 stones handicap to your opponent says to
your opponent " you are allowed 6 BIG mistakes". If your opponent makes
less than 6 mistakes he will win, more than 6 mistakes he will lose.
Chess doesn't have this concept. One BIG mistake in chess and it is game
over.
I play both, enjoy both and I don't need to compare them.
That's my 2 cents worth.
--
John Katic e-mail address aq...@freenet.carleton.ca
fax number 1-613-820-5993
-----------------------------------------------------------------
Scott Brown
>Chris Sanderson wrote:
>> In go, no pieces move at all, it's a static game. It's modern chess that
>> has overcome these problems (which other games don't even think
>> are problems) and works well.
ToeKnee writes:
> Just because 'no pieces move' in go doesn't mean that it is a static
>game. Open your mind a little.
Furthermore, it's not true that the pieces don't move. They
move from the bowl of stones onto the board, after which they
don't move again (unless removed). Until placed on the board,
each stone is identical; after being played, no two stones are
alike (indeed, a stone may change purposes many times).
That sounds flippant, but I don't mean it to be so. Consider:
while it is true that the _position_ of a stone, once placed,
cannot be changed, in go the _role_ the stone plays can change
several times. It may begin as an extension into uncharted
territory, then turn into part of an iron post or the base
of a running group. Later, it may be treated as an unimportant
kikashi stone, until the opponent ignores a ko threat and the
stone becomes the launching point for an invasion of the
opponents corner.
In go, the positions of stones are less flexible than in
chess but the roles of each stone can be far more flexible.
Rooks, bishops and queens, while employable in many
configurations, do not change their "character" as much
as a stone may do so.
>Chris Sanderson wrote:
>> In chess, long term strategic thinking is required. But in
>> addition, the player must consider the immediate tactical
>> situation and prevent any quick attacks. This two tiered nature
>> of chess, versus the one for go, is what I was talking about.
This is a joke, right? You aren't _really_ saying there's no
need for tactical thinking in go?
>Chris Sanderson wrote:
>> Chess is still better than go.
This is also a joke, right? It would, after all, be very
childish to claim one's own tastes and hobbies are the
"best ones".
Scott Brown
Lee Schumacher
>Contradiction between being *too slow* and requiring *less
>cconcentration*.
>The previous poster believes that because a game is slow, the
>player must concentrate harder and longer because of all the
>moves required to develop the game. "What are they doing,
>whisting dixie?" These two things are not a contradiction but
>rather go together. I was refering to the way small errors in
>chess are pounced upon quickly, and how hard it is to make the
>right move. Concentration is needed because the consequences of
>an error in chess is far higher than in other games. The speed
Well, this is just flat out false. Why don't you go out and
study go, and learn something about the game before you spew
out crap like this. Try logging in to the internet go server
and play a real go player and just see how long it takes for
your 'small' errors to be pounced on. Try studying professional
games and reading professional commentaries on them and see
what effects a small mistake can have on the whole course
of a game.
>of chess is what gives it this edgy quality. I've played chess
>with no castleing and 1 move pawns. Those are he old rules. Its
>slow, and to be honest feels a good deal like checkers.
> In go,
>no pices move at all, its a static game.
Just because the pieces don't move doesn't mean that its static.
You're obviously too ignorant to recognize the flow and the beauty of go.
> Its modern chess that
>has overcome these problems (which other games don't even think
>are problems) and works well.
>The consequenses of a bad move in go are far smaller than in
>chess. A person ahead tends to stay ahead even after a weak
>move. A person ahead would have to *keep on blundering* to lose.
And how did you get ahead ?
>To answer the question, yes, they are whistling dixie. When I
>play these games I worry mostly about the long term prospects of
>my move without concern for the immediate impact. This is
>because one move won't have much immediate impact. In chess,
>long term strategic thinking is required. But in addition, the
>player must consider the immediate tactical situation and
>prevent any quick attacks. This two tiered nature of chess,
>versus the one for go, is what I was talking about.
There's more than one tier to go, in fact there are so many
tiers to go that you can't even percieve the gradations.
And besides, your whole analysis conviently ignores the one clear
advantage of go - no draws. In many chess positions even large
material advantages don't ensure a win. Draws represent a significant
portion of the games at high levels in chess, this is because the
advantage of the opening move is probably insufficient to ensure a win
for white. Within that space of drawn games there is plenty of room
for blundering without affecting the final outcome of the game, or
possibly changing wins to draws. In go correct play from a superior
position always results in a win.
>Chess is still better than go.
I don't know why i let this obvious flame bate annoy me ...
Michael Sullivan
Chris Sanderson <cis...@gamma.std.com> wrote:
>rather go together. I was refering to the way small errors in
>chess are pounced upon quickly, and how hard it is to make the
>right move. Concentration is needed because the consequences of
>an error in chess is far higher than in other games. The speed
[...munch...]
>The consequenses of a bad move in go are far smaller than in
>chess. A person ahead tends to stay ahead even after a weak
>move. A person ahead would have to *keep on blundering* to lose.
You are correct. Some people *like* this aspect of go. One of the
things that always disturbed/frustrated me about chess was that I could
build up a winning game with superior play, but there were still tons of
chances to throw that win away with a single careless move. It's true
that in go, you can build nearly insurmountable leads, but to do so, you
have to play significantly better than your opponent for a long time.
Small leads change hands easily. In chess there really are no leads
except at levels where major tactical blunders never happen.
Chacun a son gout (Where's that cedilla?!:)) You like being terribly
nervous and edgy the whole game. *I* like being able to focus in a
natural way that is similar to the way I focus on real life problems. Go,
for me is good practice at problem solving in general. Unless the
problems you care to solve involve highly critical tactical decisions made
at lightning speed (such as flying a fighter plane) chess is less of an
analogy.
I've met a lot of very strong chess players who think that the game of go
is a lot bigger and more interesting. That once you have eliminated the
tactical blunders from your game (which is done all the time by amateur
players), chess becomes a research contest -- to find an opening or
variation your opponent won't be familiar with, because the kinds of
tactical/strategical mistakes that top players make are too small to
determine the game. In go even top players make plenty of small errors
This is true of chess too. but in go these very small errors add up to the
difference in the game, in chess there is a certain fairly large
discrepancy (to a very good player) that must be met otherwise there will
be a draw.
I wonder how much go you have played. I don't like to make
generalizations, but in my experience, people who have gotten beyond
novice rankings in both games (say ~1400 Elo and 3-4kyu) nearly always
prefer go, often to the point where they give up chess almost completely.
If you're still with me, you are reading the words of one such person
right now.
That's skewed of course, because it's harder to find go games. Anyone
who gets to 3-4kyu has to do a lot more logistical work than they had to
to play the chess, so they probably did it because they were plenty
interested in go.
Don't get me wrong, chess is a *great* game. It's the only game I've
played that even deserves comparison with go:). (although I hear tell
that some of the oriental variants of chess are also quite good).
Mike
--
________________________________________________________________________
Michael Sullivan (Society for the Incurably Pompous) m...@pcnet.com
"Life is like a sewer -- what you get out of it, depends on what you put
into it." -- Tom Lehrer.
Mark Chess
Schumacher) writes:
"And besides, your whole analysis conviently ignores the one clear
advantage of go - no draws. In many chess positions even large
material advantages don't ensure a win. Draws represent a significant
portion of the games at high levels in chess, this is because the
advantage of the opening move is probably insufficient to ensure a win
for white. Within that space of drawn games there is plenty of room
for blundering without affecting the final outcome of the game, or
possibly changing wins to draws. In go correct play from a superior
position always results in a win."
----
In chess also, correct play from a superior position always results
in a win! That is, if we only define "superior position" as
"a position which is won with correct play"!
evan behre
: e...@netcom.com (Ed Wilkinson) writes:
: --
: Go is better than Chess. Poker is more lucrative. Sex is more fun.
worth keeping ^ ^ ^
i think chess plays an important role in developing the minds and
analytical ability of future go players, especially in the western world.
when i was growing up, my dad taught me how to play chess. i used to play
him, until i started beating him. ~-(
i enjoyed chess matches with friends and thought i was pretty good, got a
second place trophy at a chess tournament in college (big deal).
i learned about go from a friend in high school, whom i would play all
sorts of other board games with. when i went to college and discovered
the go club scene and the a.g.a. tournament scene, i discovered there was
a whole lot more to go, than what i and my self-taught buddies had
previously imagined. as i learned more about go, and my imagination was
captured, i just gave up chess. i considered go to be more open, more
wonderous, more intuitive, etc, and chess appeared to be so constipated,
etc. for me, go is prefered. let others with more ability than i play
chess, it is a fine game. after all, it led me to go.
another anecdote: i founded a club in my area: HoCoGo. we specialize in
helping beginners and double digit kyu players become stronger by giving
lessons, teaching games, lending library of go books, etc. there is this
guy from the U.K. who is a decent chess player and new to go who comes to
my club once in a while. this guy had never played any human opponents
before my club (just computer programs). he would think and take a long
time. we asked him to play a little faster since there are more moves in
a go game than in your average chess game. i could tell this guy was
burning (hard concentrating). so, he borrows a book and comes back to
club in a few weeks and plays at a level about 5 stones stronger. this
same pattern continues, and in less than a year, he is in the single
digit kyu range! he doesnt play very often, but when he does, he is
serious about it. the most impressive performance by a beginner i have
seen. i attribute his rapid improvement to his experience at "reading"
out tactical situations at the chess board.
chess is great, i prefer go. money is okay, but i prefer food.
-- -evan-
(wo shi da pangzi.) .-)
Chris Sanderson
about go. You people must like it a lot. For me, chess takes
less time, and I don't have much time.
I have a number of computer chess programs, but none for go. If
go is as big and complex as described, such a program would be
either slow or to big for memory. Is there any public-domain go
game I can download and practice with? I have an old 286 machine
with only 2meg of memory.
Lee Schumacher
>It seems I have stired up a hornets nest of people defensive
>about go. You people must like it a lot. For me, chess takes
>less time, and I don't have much time.
Well, as an avid go player, even i must admit that there's nothing
like a good game of blitz to get the adreneline pumping :-).
>I have a number of computer chess programs, but none for go. If
>go is as big and complex as described, such a program would be
>either slow or to big for memory.
bingo! got it in one! Some even claim that this is further evidence
for the superiority of Go. Its certainly the most objective piece
of evidence available. Current computer go programs do not provide
any challenge for a human player beyond the absolute novice stage.
>Is there any public-domain go
>game I can download and practice with? I have an old 286 machine
>with only 2meg of memory.
The public domain programs are all on the internet go archives
which is in (last i checked) bsdserver.ucsf.edu in the directory
pub/go (or something similar). Check the FAQ for rec.games.go
if I got it wrong. I warn you that the programs available there
are pathetically weak! However there is a lot of instructional
material there, as well as information about how to get on
the internet go server. Thats the place to get a real education ...
good luck,
Lee.
Paul A. Lane
>>I have a number of computer chess programs, but none for go. If
>>go is as big and complex as described, such a program would be
>>either slow or to big for memory.
>bingo! got it in one! Some even claim that this is further evidence
>for the superiority of Go. Its certainly the most objective piece
>of evidence available. Current computer go programs do not provide
>any challenge for a human player beyond the absolute novice stage.
Oh, please. How many idiots are going to be drawn in on this
specious argument. The number of possible moves in the tree
is no kind of evidence.
One could expand the chess board to 10x10 and add more pieces.
Would this be objectively superior to chess? No
Would there be more possible mores? Yes
Perhaps one could design an incredibly complex game that a
Cray couldn't fathom. It wouldn't be enjoyable, but at least
it's complex.
Paul
--
john_gipson
I have go nemesis, which I bought to improve my skill, and have played with
ManyFaces on IGS (available from ISHI press for $40). The problem with both
is that I always beat them! This is true even them I am IGS rated at 22kyu,
and ManyFaces is 15kyu.
I am better chess player than a go player, but my chess program always beats me.
Must be a lot harder to program go!
ToeKnee
pal...@iastate.edu (Paul A. Lane) wrote:
> In <31htcg$d...@news.doit.wisc.edu> schu...@math.wisc.edu (Lee
Schumacher) writes:
>
> >>I have a number of computer chess programs, but none for go. If
> >>go is as big and complex as described, such a program would be
> >>either slow or to big for memory.
>
> >bingo! got it in one! Some even claim that this is further evidence
> >for the superiority of Go. Its certainly the most objective piece
> >of evidence available. Current computer go programs do not provide
> >any challenge for a human player beyond the absolute novice stage.
>
> Oh, please. How many idiots are going to be drawn in on this
> specious argument. The number of possible moves in the tree
> is no kind of evidence.
>
> One could expand the chess board to 10x10 and add more pieces.
>
> Would this be objectively superior to chess? No
>
> Would there be more possible mores? Yes
If it were simply the 'number of possible moves in the tree' (the
heuristics tree, I assume you mean), then all you would have to do is take
the proverbial Cray with a hundred different accelerator boards to make an
awesome go program fly. However, go cannot be programmed solely with
heuristics (unlike chess)... there are too many conceptual (i.e.
pattern-based/non-computational) functions to implement; no tree-based
program can compete with a human player.
So, suggesting that expanding a chessboard by 36 squares would
effectively recreating the complexity of a go board (albeit on a smaller
scale) is misguided... there apparently are certain global relationships
between stones that cannot be ignored and unfortunately *would be* if
heuristics were the only means used for programming a better computer go
game.
So, you are right... the number of possible of moves in the tree is no
kind of evidence [for the superiority of Go] :)
However, I also don't think that it is possible to just find a
supercomputer and a good computer programmer and make a
professional-strength go-playing program. I believe it will take a
dramatic change in the current academic understanding of how the human
brain learns and operates before we can even create a program that can
defeat a strong amateur.
>Perhaps one could design an incredibly complex game that a
>Cray couldn't fathom. It wouldn't be enjoyable, but at least
>it's complex.
I honestly don't think that a Cray can fathom 19x19 go... and I would
even put money on my ability to beat it giving 9 stones :)
--
ToeKnee, 2d*, 2219 USCF toe...@teleport.com
Mason House Co-Op PDX/OR/USA
Lee Schumacher
>In <31htcg$d...@news.doit.wisc.edu> schu...@math.wisc.edu (Lee Schumacher) writes:
>>bingo! got it in one! Some even claim that this is further evidence
>>for the superiority of Go. Its certainly the most objective piece
>>of evidence available. Current computer go programs do not provide
>>any challenge for a human player beyond the absolute novice stage.
>Oh, please. How many idiots are going to be drawn in on this
>specious argument. The number of possible moves in the tree
>is no kind of evidence.
If you will carefully review the above paragraph, nowhere will you
find any discussion of *why* current computer programs are not a match
for humans. Even played on a 9x9 board, go is still too hard for
current computer programs to pose a challenge even too novices. Since
the complexity of 9x9 go is (more) comparable to that of chess, and
since chess programs, even running on pc class hardware play better
than 95% (or whatever) of all human players, I think the conclusion
has to be that computational complexity alone is not the issue here.
>One could expand the chess board to 10x10 and add more pieces.
>Would this be objectively superior to chess? No
>Would there be more possible moves? Yes
Would humans be any better at it than machines ? I think not.
While go is computationaly much more complex than chess, it
is also more amenable to the pattern matching skills of human
beings.
The thing about chess is that it is a very linear game. Serial tasks
are ideally suited for being solved by convential computers. Playing
go fully engages the parrallel processing power of the human mind while
also requiring a great deal of serial analysis. Since serial tasks
are the ones that we are 'conscious' (arguably by definition) of, they
are much easier to program. The pattern matching which goes on in
parallel is largely unconscious, and so is much more difficult to
translate into computer algorithms. The effect of this is that
Go 'feels' more intuitive, which is why many go players prefer it to
chess.
Personally, i only enjoy playing chess at blitz time controls,
because neither player has enough time to analyse very deeply, but
because of my go background i often have a much better strategic grasp
of the game than chess players who are much higher rated ..
>Perhaps one could design an incredibly complex game that a
>Cray couldn't fathom. It wouldn't be enjoyable, but at least
>it's complex.
Cray's don't 'fathom' anything, they're just machines. People
play go and chess because they enjoy the sense of accomplishment
they get from playing them well. You can play tic-tac-toe perfectly,
but do you derive any pleasure from it ?
sigh...
Lee.
Mark A Zabel
I'm sure he would have made similar comments on people who play that
game.
In article <toeknee-0108...@ip-ca.teleport.com>,
ToeKnee <toe...@teleport.com> wrote:
[Earlier excerpts of "debate" deleted]
>
> If it were simply the 'number of possible moves in the tree' (the
>heuristics tree, I assume you mean), then all you would have to do is take
>the proverbial Cray with a hundred different accelerator boards to make an
>awesome go program fly. However, go cannot be programmed solely with
>heuristics (unlike chess)... there are too many conceptual (i.e.
>pattern-based/non-computational) functions to implement; no tree-based
>program can compete with a human player.
>
> So, suggesting that expanding a chessboard by 36 squares would
>effectively recreating the complexity of a go board (albeit on a smaller
>scale) is misguided... there apparently are certain global relationships
>between stones that cannot be ignored and unfortunately *would be* if
>heuristics were the only means used for programming a better computer go
>game.
>
> So, you are right... the number of possible of moves in the tree is no
>kind of evidence [for the superiority of Go] :)
>
> However, I also don't think that it is possible to just find a
>supercomputer and a good computer programmer and make a
>professional-strength go-playing program. I believe it will take a
>dramatic change in the current academic understanding of how the human
>brain learns and operates before we can even create a program that can
>defeat a strong amateur.
>
>>Perhaps one could design an incredibly complex game that a
>>Cray couldn't fathom. It wouldn't be enjoyable, but at least
>>it's complex.
>
> I honestly don't think that a Cray can fathom 19x19 go... and I would
>even put money on my ability to beat it giving 9 stones :)
>
>--
>ToeKnee, 2d*, 2219 USCF toeknee@teleport.
com
>Mason House Co-Op PDX/OR/USA
-Regards, Mark
Paul A. Lane
>If you will carefully review the above paragraph, nowhere will you
>find any discussion of *why* current computer programs are not a match
>for humans.
The point was made that this is some kind of evidence for the super-
iority of go vs. chess.
>Even played on a 9x9 board, go is still too hard for
>current computer programs to pose a challenge even too novices. Since
>the complexity of 9x9 go is (more) comparable to that of chess, and
>since chess programs, even running on pc class hardware play better
>than 95% (or whatever) of all human players, I think the conclusion
>has to be that computational complexity alone is not the issue here.
Sorry. 9x9 go can be more quickly mastered than chess.
Perhaps checkers is a better analysis.
>Personally, i only enjoy playing chess at blitz time controls,
>because neither player has enough time to analyse very deeply, but
>because of my go background i often have a much better strategic grasp
>of the game than chess players who are much higher rated ..
The primary reason I dislike blitz (or to be precise, consider it only
an occasional amusement) is that games tend to be decided by blunder
rather than good moves.
>Cray's don't 'fathom' anything, they're just machines. People
>play go and chess because they enjoy the sense of accomplishment
>they get from playing them well. You can play tic-tac-toe perfectly,
>but do you derive any pleasure from it ?
I realize that picking nits is a famous net sport, but come on.
I understand exactly what computers do when processing. I suppose
I could have used an exact game theory term which wouldn't have
enlightened the post any further. However, my meaning should have
been clear.
> sigh...
> Lee.
Sigh. This is a silly squabble. A better question might be
what draws people to each of these games.
Paul
--
Chris Sanderson
more branches per node, and that more ply are needed to play
well. Go computers are no good against even a moderate go
player.
Yet the argument that says go is a better game for this reason
is spurious. This has been discussed in this thread for a while
now. Now the question is to decide if a game is "enjoyable" or
not. Now this is too subjective, it comes down to preferences
and orientation. Lets say someone likes 3x3 tic-tac-toe a whole
bunch, and prefers it over chess or go. Does this mean that 3x3
tic-tac-toe is the best game around? I don't think we want to
make things so subjective that there is no meaning to it.
I will use the concept of "diversity" to help make the question
less subjective.
* tic-tac-toe games have squares and pieces. The goal is to get
n in a row. There is not much diversity of types in this game.
* Go has only one kind of piece, again little diversity. But the
objective is to take territory, which gives it another
dimention. The game is large and complex by computational
standards, but not diversity standards.
* Chess has the square board like the others. In chess, the
different parts of the board add to its diversity: the center,
the wings, the corners. Go has this as well. Chess also has six
separate kinds of pieces, go only has one. Chess is far more
diverse than go, but go players probably don't care about that.
A similar way to say it is to ask "What is a shortest possible
way to describe the rules of the game?" Go would talk about the
board, the one piece, the atari rule, not a lot. Chess would
have to describe all six pieces, the en passant rule, castleing,
two move pawns, fifty move draws, etc. By this standard, chess
has a longer description and is more diverse.
Do the go players have something better? I would like to here
more about how the chess players exposed to go start playing go,
and go players exposed to chess keep on playing go. If I
expanded the go board, from 19x19 to 23x23 (the next prime
number) would that make it better or just bigger?
ToeKnee
mza...@magnus.acs.ohio-state.edu (Mark A Zabel) wrote:
> Yet more evidence that G.B. Shaw was correct. If he knew about Go
> I'm sure he would have made similar comments on people who play that
> game.
So what's the quote you are referring to? Do you realize I am a chess
player? Would that quote apply to me being 'a person who plays that game'
as well?
Cheers...
--
John Tromp
> In article <31jhu5$q...@hubcap.clemson.edu>, cis...@gamma.std.com (Chris Sanderson) writes:
> [...]
> |> If I expanded the go board, from 19x19 to 23x23 (the next prime
> |> number) would that make it better or just bigger?
>
> were done in Asia relatively recently, with professional go players.
> The conclusion was that the 17x17 game is too trivial to be
> interesting,
Haha! I almost killed myself laughing at this.
You must be confused with 7x7. Anything larger is highly nontrivial.
Why do you think professional players play 9x9 tournaments?
regards,
%!PS % -John Tromp (tr...@math.uwaterloo.ca)
42 42 scale 7 9 translate .07 setlinewidth .5 setgray/c{arc clip fill
setgray}def 1 0 0 42 1 0 c 0 1 1{0 3 3 90 270 arc 0 0 6 0 -3 3 90 270
arcn 270 90 c -2 2 4{-6 moveto 0 12 rlineto}for -5 2 5{-3 exch moveto
9 0 rlineto}for stroke 0 0 3 1 1 0 c 180 rotate initclip}for showpage
Peter Lasersohn
>* Go has only one kind of piece, again little diversity. But the
>objective is to take territory, which gives it another
>dimention. The game is large and complex by computational
>standards, but not diversity standards.
I don't think it's legitimate to compare individual pieces in go to
individual pieces in chess. This is a little like comparing
individual lines of assembly language code to individual lines of lisp
code. Just like a single command in a higher-level programming
language corresponds to a whole long program in machine language,
individual moves in chess are comparable to whole sequences of moves
in go. Individual pieces in chess correspond, not to individual
pieces in go, but to larger patterns involving several pieces. There
are a wide variety of possible patterns on this scale, some of which
come up all the time, others of which are less common -- but in any
case there are more than enough of them to produce as much "diversity"
as in chess.
A corollary of this is that a go board is not really "larger" than a
chess board, just more fine-grained. This presumably invalidates some
of the arguments based on board size that people have given in favor
of go, even while it also invalidates arguments in favor of chess like
the one above, based on piece variety.
It seems to me that chess and go are roughly comparable.
Peter Lasersohn
David Forthoffer
: cis...@gamma.std.com (Chris Sanderson) writes:
:
: >I have a number of computer chess programs, but none for go. If
: >go is as big and complex as described, such a program would be
: >either slow or to big for memory.
:
: bingo! got it in one! Some even claim that this is further evidence
: for the superiority of Go. Its certainly the most objective piece
: of evidence available. Current computer go programs do not provide
: any challenge for a human player beyond the absolute novice stage.
The superiority of Go (if any) is not proven by the difficulty
of programming Go.
Here's a game for you. You and your opponent each receive a piece of
paper with a story handwritten on it. Each sentence in the story is
handwritten by a different person. The goal of the game is to see who
can most correctly type the story into a computer.
If you judge the superiority of this game versus Go, you should conclude
that this game is superior to Go because the computer plays this game
so poorly.
--
David Forthoffer NEC Technologies Printer Division
David Forthoffer
: Is there any public-domain go
: game I can download and practice with? I have an old 286 machine
There are only commercial ones that I know of...
The problem with current programs is that you can learn to beat them
without becoming better at Go.
I can give Many Faces of Go a 31-stone handicap and beat it.
This is due to my ability to provoke and exploit certain repeatable
stupid maneuvers it makes. Some of my provocations are actually
weak moves, but turn out well due to the program's stupidity.
(I give it a 31-stone handicap by giving it 27 stones to start,
then passing 4 times. I can't give it a 32-stone handicap because
it claims a win then.)
--
David Forthoffer (1k*) NEC Technologies Printer Division
Mark Chess
Is it not true that there are many, many more tournament
chessplayers than go players, and therefore much more interesting
in creating good chess programs, than for go? That, to me, is
why chess programs are strong. 25 years ago chess programs were
pathetically weak, and everyone used the same arguments about why
they'll never be strong. But ingenious programming and lots of
hard work did the trick, not simply "deep tree searches." I
would assume that nowhere NEAR the man hours nor money have been
spent on go programs as chess programs.
Another point: Should we compare the number of BOOKS written about
the games to see which is "better"? Chess would win that criteria
hands down. Does THAT mean chess is more complex and more subtle,
because it takes more books to write about it?
I have an idea for a criteria that might determine which games in
the world, or sports in the world, are "harder": Count the number
of man-hours required for a person to become world champion. Just an
idea! Which is "harder," NBA point guard, or NFL quarterback, or
pro golfer, or olympic swimmer?
I've enjoyed this discussion!
Mark Kislingbury
Mark Chess
Schumacher) writes:
>Even played on a 9x9 board, go is still too hard for
>current computer programs to pose a challenge even too novices. Since
>the complexity of 9x9 go is (more) comparable to that of chess, and
>since chess programs, even running on pc class hardware play better
>than 95% (or whatever) of all human players, I think the conclusion
>has to be that computational complexity alone is not the issue here.
Lee, don't forget that MUCH more work has been expended in making
chess programs than go. Chess programs sell, therefore the monetary
incentive. Chessplayers outnumber go players by a huge margin, both
in t he U.S. in worldwide. There's no telling how good go programs
could be in 20 years if effort is put toward it. Remember, 25
years ago there existed Cray brute-force chess programs that could play
no better than 1600-level chess! Chessplayers said, "computers will
never play chess well, because there is much abstract thinking, such as
open lines, attacks, space, etc." In f act, there are STILL chess
positions that people can solve using abstract reasoning (not
calculation) that computers remain stumped on.
(Personal note: I grew up in Ames! Did you go to AHS?)
Mark Kislingbury
Roy Blackmer
|> number) would that make it better or just bigger?
|>
|>
I read somewhere that experiments with 17x17 and 21x21 go boards
were done in Asia relatively recently, with professional go players.
The conclusion was that the 17x17 game is too trivial to be
interesting, and that 21x21 is too complex.
-- Roy
al
schu...@math.wisc.edu "Lee Schumacher" writes:
> cis...@gamma.std.com (Chris Sanderson) writes:
>
> >I have a number of computer chess programs, but none for go. If
> >go is as big and complex as described, such a program would be
> >either slow or to big for memory.
>
> bingo! got it in one! Some even claim that this is further evidence
> for the superiority of Go. Its certainly the most objective piece
> of evidence available. Current computer go programs do not provide
> any challenge for a human player beyond the absolute novice stage.
>
Surely one could say that there are just far more people working in
the field of chess computers. If that's the case maybe it is because
chess is more of a challenge to them?
Al
J E H Shaw
compare with oranges"' compare with `"how does chalk compare with cheese"
compare with "how does go compare with chess"'?
--
J.E.H.Shaw, Department of Statistics, | JANET: st...@uk.ac.warwick
University of Warwick, | BITNET: strgh%uk.ac.warwick@UKACRL
Coventry CV4 7AL, U.K. | PHONE: +44 203 523069
An ex-algebraist who lost his ideals, his associates, and finally his identity
Lee Schumacher
>There's been a lot of argument about go chess programs vs. chess programs.
> Is it not true that there are many, many more tournament
>chessplayers than go players, and therefore much more interesting
>in creating good chess programs, than for go?
I honestly don't know, but it seems rather rash of you to assume so ...
Let's see, there are 5 million go players in Japan, another 5 million
in Korea, and ... oh yeah, I hear people play it in China too :-)
I met one fellow who wrote a go program for the nintendo
machine that was a bestseller in Japan at $130 a pop. I can
assure you that the quality of play was extremely low. A good go
program would make its author a multi-millionare.
>25 years ago chess programs were
>pathetically weak, and everyone used the same arguments about why
>they'll never be strong.
What arguments ? I've given reasons why programming chess is easier
than programming go, I've never made any claim that they'll never be
strong.
> But ingenious programming and lots of
> hard work did the trick, not simply "deep tree searches." I
>would assume that nowhere NEAR the man hours nor money have been
>spent on go programs as chess programs.
While this is probably true, I don't think it has any bearing. Sure
lots of 'man' hours have been spent on chess programming - lots of hours
on Sargon, lots of hours on Fritz, lots of hours on CM and they all
seem to be about equally successful. I don't think that any of those
programs represent the full time input of more than 1 - 2 programmers
per implementation. People have been trying to program Go for almost
as long (i've got reference's to work going back to the early 70's,
if you care ...). The reason that there aren't as many commercial
go programs is that nobody knows how to right one that plays an
interesting game. How much would you pay for a chess program that
didn't know how to move the pieces ? Go programs are nearly that bad ...
>Another point: Should we compare the number of BOOKS written about
>the games to see which is "better"? Chess would win that criteria
> hands down. Does THAT mean chess is more complex and more subtle,
>because it takes more books to write about it?
ahem. Assuming facts not in evidence. There are certainly a lot more
books in *english* or *russian* about chess, than there are in
*english* or *russian* about go. Most go books are in Chinese, Korean
and Japanese. Recorded go history (i.e. actual game records) is
*centuries* older than chess, even if you include the renaiscance
precursors of modern chess. Your credentials for expressing opinions
on this subject, please ? Do you have any knowledge of asian languages,
culture, or history ?
Just because go is small time were you live, don't assume that its
that way everywhere...
Lee.
Mark A Zabel
ToeKnee <toe...@teleport.com> wrote:
>In article <31j4ii$a...@charm.magnus.acs.ohio-state.edu>,
>mza...@magnus.acs.ohio-state.edu (Mark A Zabel) wrote:
>
>> Yet more evidence that G.B. Shaw was correct. If he knew about Go
>> I'm sure he would have made similar comments on people who play that
>> game.
>
> So what's the quote you are referring to?
Don't have the quote handy. The gist was that chess is a waste of
time that makes grown men think they are doing something clever.
I didn't say I agreed with it or him in general.
>Do you realize I am a chess
>player?
Yes.
>Would that quote apply to me being 'a person who plays that game'
>as well?
I believe it would.
I don't buy Shaw's arguments on why someone shouldn't play chess, and I
literally don't see any occupation of one's time that couldn't be said to be
a waste of time.
On the other hand, I don't see any point at all to asking "which
game is better - Go or Chess?", as the word better isn't clearly defined.
A more appropriate title for this thread would be "Why is go more difficult
to program than chess?" Perhaps this is even too subjective a question.
Note: Re-reading the title reminded me that it was in fact "How does go
compare with chess? - not Which is better... One wouldn't know it from the
debate on this thread.
Finishing up here: I taught at a chess camp in Pennsylvania a couple of
weeks ago. One of my students, a 6 year old boy, had an absolutely great
time cheating at tic-tac-toe against me during dinner. I also was able to
relate to him much better through that game than through chess. For me, this
was an instance where tic-tac-toe *was* better than chess. It is not, however,
an answer to "Is tic-tac-toe better than chess?" without any clear definition
of the word better.
-Regards, Mark
p.s. BTW, the reason I chose to comment on ToeKnee's post was because
he plays both go and chess. I figured I would ruffle less feathers that
way. I apologize if I ruffled any.
Mark Chess
Schumacher) writes:
>>Another point: Should we compare the number of BOOKS written about
>>the games to see which is "better"? Chess would win that criteria
>> hands down. Does THAT mean chess is more complex and more subtle,
>>because it takes more books to write about it?
>ahem. Assuming facts not in evidence. There are certainly a lot more
>books in *english* or *russian* about chess, than there are in
>*english* or *russian* about go. Most go books are in Chinese, Korean
>and Japanese. Recorded go history (i.e. actual game records) is
>*centuries* older than chess, even if you include the renaiscance
>precursors of modern chess. Your credentials for expressing opinions
>on this subject, please ? Do you have any knowledge of asian languages,
>culture, or history ?
>Just because go is small time were you live, don't assume that its
>that way everywhere...
I have no credentials in order to support my opinions on go; my only
credentials are how I play chess. The only reason I raised the
number-of-books-written issue is because I've read from numerous sources
that more books have been written on chess than any other game in the
world; now, they didn't specify what LANGUAGE the books were written in.
And when referring to number of tournament chessplayers to go players, I
meant "tournament go players." I made the perhaps-wrong assumption that,
worldwide, there are more tournament chessplayers. An admitted
assumption, my having only experienced the chess world.
It would be nice to see the numbers of worldwide tournament players in the
following games: chess, checkers, go, chinese chess, othello, shogi, and
also numbers of books written.
It seems to me that just because go is older, doesn't mean it would have
more books. The vast majority of books on games were all written in the
20th century (another assumption!).
Again, I have no credentials!
The point I'm desiring to make? Only that I thought much more effort has
been expended to make chess programs than go programs, but I could be
wrong.
However, I do believe, if memory serves me, that the vast majority of
chessplayers 25 years ago were convinced that a computer would never play
master level, and CERTAINLY not, God-forbid, grandmaster level! I myself
was in that camp.
That's all! I remain undogmatic and open to reason!
Yours truly,
Mark Kislingbury
Richard Resnick
AI's, I can honestly say that Go is MUCH harder to implement. Think
about it. Chess has maybe 30 or so possible moves that either player
can make during their turn. Say an average of 50 moves per
game... that's 30 to the 50th possible board positions. But go...
I'm not sure of the size of the go grid, but I know it's more than 8
by 8. I'll assume it's 16 by 16. Then, there are 256 possible moves to
be made (at least at the beginning, and towards the end there are
still 60 to 100). How many MOVES in a go game? Maybe 100, maybe 150, I
don't know. The point is, you're dealing in exponentiation. There are
approximately 256 to the 125th board positions in Go. That dwarves
chess by so much, it's unfathomable. There are a hundred times more Go
positions than chess, than there are particles in the universe.
The combinatorics are only the first part. How do you write a function
which rates board positions in Go? After all, each possible move you
might make needs to be evaluated! It turns out, this is just as
costly!! You need to look at the WHOLE board to judge how you are
doing! How many operations? For a 16 by 16 board, 256 of them!
Chess is way more manageable than Go, it's just the facts. They are
both beautiful games, and Chess is my personal favorite, but Go is by
far the more complex of the two, if you think about the word "complex"
mathematically.
Richard Resnick
---
Richard Resnick Center for Genome Research
ric...@genome.wi.mit.edu The Whitehead Institute, MIT
All opinions expressed within belong solely to Richard Resnick.
Nici Schraudolph
>Perhaps one could design an incredibly complex game that a
>Cray couldn't fathom. It wouldn't be enjoyable, but at least
>it's complex.
You're missing the point here: Go is a game with incredibly *simple*
rules that a Cray still can't fathom. That's part of its beauty.
I agree that the size of search space is a red herring, but think about
it this way: it is only because Go is so well-suited to the way humans
process information that we can play it on such a large board, despite
of the humongous search space.
>Sorry. 9x9 go can be more quickly mastered than chess.
By humans, yes. By computers, not yet. I'm interested in computer Go
because I believe it will force us to learn more about the humans mind.
Nothing against chess as a game, but I do wish AI had picked Go instead
as its touchstone problem in the 50s... of course there's no guarantee
that someone won't come up with a "magic bullet" for computer Go (like
search was for computer chess), but it doesn't look likely at this point.
--
Nicol N. Schraudolph | The purpose of words is to convey ideas: when
The Salk Institute, CNL | the ideas are grasped, the words are forgotten.
10010 N. Torrey Pines Rd | Where can I find one who has forgotten words?
La Jolla, CA 92037-1099 | That's the one I'd like to talk to. (Chuang Tzu)
Michael Sullivan
Chris Sanderson <cis...@gamma.std.com> wrote:
>I will use the concept of "diversity" to help make the question
>less subjective.
>* tic-tac-toe games have squares and pieces. The goal is to get
>n in a row. There is not much diversity of types in this game.
>* Go has only one kind of piece, again little diversity. But the
>objective is to take territory, which gives it another
>dimention. The game is large and complex by computational
>standards, but not diversity standards.
>* Chess has the square board like the others. In chess, the
>different parts of the board add to its diversity: the center,
>the wings, the corners. Go has this as well. Chess also has six
>separate kinds of pieces, go only has one. Chess is far more
>diverse than go, but go players probably don't care about that.
You were saying something about spurious arguments?
Essentially you are claiming that chess is more diverse because it has
more rules.
I've seen battle miniatures rule sets that will dwarf the chess rule book
many times over? Does this necessarily mean they are more diverse than
chess?
I think not. I think one of the marks of a truly great game is how
diverse the tactics and strategies are relative to the *simplicity* of the
rules. Chess scores very high on this scale, only a few games are
simpler, yet have significant tactical and strategic dimensions that can
even be mentioned in the same breath as chess (Othello, certain renju
variants, go, checkers -- off the top of my head).
Mike.
--
________________________________________________________________________
Michael Sullivan (Society for the Incurably Pompous) m...@pcnet.com
"Life is like a sewer -- what you get out of it, depends on what you put
into it." -- Tom Lehrer.
ToeKnee
> Now the question is to decide if a game is "enjoyable" or
> not.
What!? You are going to decide objectively once and for all if chess or
go is enjoyable? It is clear you don't enjoy go, so how will you get
around that bias?
> I will use the concept of "diversity" to help make the question
> less subjective.
> [ deleted ]
> * Go has only one kind of piece, again little diversity. But the
> objective is to take territory, which gives it another
> dimention. The game is large and complex by computational
> standards, but not diversity standards.
Ok, first of all, unless you define 'diversity' a bit better, your
subsequent statements won't make much sense. Secondly, in go the
*foremost* objective is to take territory, but there are many lower-level
objectives followed to accomplish this, the details of which I won't
elaborate upon here. Knowing this bit of info, can you see more
'diversity' in the game, or more dimensions perhaps?
> * Chess has the square board like the others. In chess, the
> different parts of the board add to its diversity: the center,
> the wings, the corners. Go has this as well. Chess also has six
> separate kinds of pieces, go only has one.
In go, rarely do players (unless they are rank beginners) consider the
pieces on a go board stone by stone. Instead, they think about the
arrangements of the stones, the 'shapes' of the stones, 'groups', and
sequences of moves. A single stone on the board cannot 'do' anything; it
is important to consider the effects that neighboring stones and strings
of stones will have on each other. By your own definition (if I
understand it correctly), this would mean in some sense that go has many,
many different kinds of pieces, since go players themselves perceive them
to exist.
> Chess is far more diverse than go, but go players probably don't care about
> that.
Kind of an overly-opinionated, blanket statement, don't you think?
> A similar way to say it is to ask "What is a shortest possible
> way to describe the rules of the game?" Go would talk about the
> board, the one piece, the atari rule, not a lot. Chess would
> have to describe all six pieces, the en passant rule, castleing,
> two move pawns, fifty move draws, etc. By this standard, chess
> has a longer description and is more diverse.
I still don't understand the 'diversity standard'... it seems to mean
that a game that has more rules is more diverse... Monopoly has a lot of
rules :)
> Do the go players have something better? I would like to here
> more about how the chess players exposed to go start playing go,
> and go players exposed to chess keep on playing go. If I
> expanded the go board, from 19x19 to 23x23 (the next prime
> number) would that make it better or just bigger?
Well, I started playing go because I had moved to a city that had very
few good chess players (at least, I couldn't find them :( ) and so I took
up go as a leisure activity. Chess was my first love, but go has many
things in its favor, some of which I have delineated in previous posts.
Games have been played on 21x21 boards, and 23x23 boards (experiments
discussed in GoWorld), but not much enthusiasm was expressed for these
variations, primarily because the balance present in a 19x19 board was
lost. The total number of points on a 19x19 board is 361: 120 points for
the corners, 120 points for the sides, and 121 for the center. In a 21x21
or 23x23 game, the value of the center is much bigger, and (I guess) this
removes the balanced quality of the game for professional player, puts it
'beyond human comprehension'. Better? Bigger? Are you just trying to
find material for some future argument? Play it... and try to appreciate
it. It's not a bad game....
ToeKnee
mza...@magnus.acs.ohio-state.edu (Mark A Zabel) wrote:
> In article <toeknee-0108...@ip-ab.teleport.com>,
> ToeKnee <toe...@teleport.com> wrote:
> >In article <31j4ii$a...@charm.magnus.acs.ohio-state.edu>,
> >mza...@magnus.acs.ohio-state.edu (Mark A Zabel) wrote:
> >
> >> Yet more evidence that G.B. Shaw was correct. If he knew about Go
> >> I'm sure he would have made similar comments on people who play that
> >> game.
> >
> > So what's the quote you are referring to?
>
> Don't have the quote handy. The gist was that chess is a waste of
> time that makes grown men think they are doing something clever.
> I didn't say I agreed with it or him in general.
Right! And talking about either chess or go is a waste of time that
makes people think they are doing something clever %^> Ah well... if I
weren't talking about it, I'd probably be doing it... what an empty life I
lead... <chuckle>
> I don't buy Shaw's arguments on why someone shouldn't play chess, and I
> literally don't see any occupation of one's time that couldn't be said to be
> a waste of time.
> On the other hand, I don't see any point at all to asking "which
> game is better - Go or Chess?", as the word better isn't clearly defined.
> A more appropriate title for this thread would be "Why is go more difficult
> to program than chess?" Perhaps this is even too subjective a question.
My original post (the one you quoted in full) was a response to what I
felt was an inadequate series of rebuttals by Paul A. Lane to Lee
Shumacher about the 'superiority' of go vs. chess as proved by the
difficulty of programming each game. (Whew! what a convoluted statement...
Sorry!) I thought that I was keeping in the spirit of the thread by
disagreeing with his hypothesis about 'make a chess program with a bigger
board, then you have a good go program', which seemed to be a comparison
of chess and go (in some small way). I probably got too windy (still
am)... I can't help it :) Anyhow, I wasn't saying that 'Go is better than
Chess', so I am sorry if this somehow came through in my writing.
> Note: Re-reading the title reminded me that it was in fact "How does go
> compare with chess? - not Which is better... One wouldn't know it from the
> debate on this thread.
Yeah, it always happens... you would think that either game is some
peoples' LIVES, or something :)
> p.s. BTW, the reason I chose to comment on ToeKnee's post was because
> he plays both go and chess. I figured I would ruffle less feathers that
> way. I apologize if I ruffled any.
Well, you did ruffle my feathers, mostly because I didn't know what
quote you were referring to, and I felt left out. %^>
Thanks for explaining...
Chris Goringe
> Chris Sanderson (cis...@gamma.std.com) wrote:
>
> : The consequenses of a bad move in go are far smaller than in
> : chess. A person ahead tends to stay ahead even after a weak
> : move. A person ahead would have to *keep on blundering* to lose.
>
> This may be true for people who don't really know how to
> play, but becomes less and less true as you become stronger.
Even at my humble 20k* level it is clear that a single bad move in, say, a
life/death situation can be enormous.
> : Chess is still better than go.
>
> I personally feel it is the height of folly to consider
> any game better than any other unless you state up front
> a rigorous set of criteria. Chess and Go are both fine
> games, but so are football, strip poker, and mumbly-peg.
Lots of people enjoy playing chess. Lots of people enjoy playing go. Thats
enough for me.
Chris
Anders Thulin
>
>I my humble opinion, I will tell you why I like Go. In chess, there is
>no degrees of winning, you win or lose (exclude draws).
There has been a number of proposals for fixing this, some by master
players -- one even by Lasker in the early 1920's or thereabouts.
For some reason, though, they haven't caught the fancy of the players.
--
Anders Thulin a...@linkoping.trab.se 013-23 55 32
Telia Research AB, Teknikringen 2B, S-583 30 Linkoping, Sweden
Richard Resnick
> compare with oranges"' compare with `"how does chalk compare with cheese"
> compare with "how does go compare with chess"'?
Perhaps there is not a soul in the entire world who could have more
effectively communicated the nature of this thread. Mr. Shaw, you have
gained my professional respect.
Olli Lounela
subject, and then into kill file with it unless this arguing in "not!"
"yes!" "not!" style stops. In particular, I find the quoted writer
actively useing blindfolds or not reading any responses (or perhaps not
understanding them).
In article <31jhu5$q...@hubcap.clemson.edu>,
Chris Sanderson <cis...@gamma.std.com> wrote:
>Go is a more complex game than chess in the sense that go has
> (...)
>Yet the argument that says go is a better game for this reason
>is spurious. This has been discussed in this thread for a while
Yes, this is very true. However, I have not seen many claim it better
(which, IMHO, it is :-) for this reason.
>now. Now the question is to decide if a game is "enjoyable" or
>not. Now this is too subjective, it comes down to preferences
> (...)
>I will use the concept of "diversity" to help make the question
>less subjective.
But then, you use the 'diversity' in a wholly subjective manner, which I
find disturbing from point of view of attempted objectivity. Also, you
give claims that I see as having little common with reality.
>* Go has only one kind of piece, again little diversity. But the
>objective is to take territory, which gives it another
>dimention. The game is large and complex by computational
>standards, but not diversity standards.
Isn't this self-contradictory? Adding another dimension does not
increase diversity? I expect anybody with any training in mathematics
above basics to disagree. That the pieces in go ("stones") *look* alike
and nominally are equally valuable (until played, that is) has nothing
to do with diversity.
>* Chess has the square board like the others. In chess, the
>different parts of the board add to its diversity: the center,
^^^^^^
Yes, add to, but in a manner I find hard to approve. From another point
of view this can be seen as an _attempt_ at adding another dimension(*),
and IMHO this attempt is poorly successful. It only adds some
complexity of calculative nature, since you need to keep tally on the
potential move destinations of each piece, and while this adds strain to
brain, I regard this a genuine kludge-type solution: ugly but sort of
(almost) works.
(*) I define dimension broadly as in "another aspect that does not
directly affect the others". This makes the diversity of possible moves
by different pieces in chess a discrete dimension of not much depth.
>the wings, the corners. Go has this as well. Chess also has six
>separate kinds of pieces, go only has one. Chess is far more
>diverse than go, but go players probably don't care about that.
I can see you claim this, but I find it hard to credit. Perhaps you use
different definition for word "diversity" than I or my dictionary do.
If it means "more possible moves per piece" you definitely are right,
since go stones don't move, but if you mean "a move has more effect on
position" you are plainly wrong(**), and if you mean "choice of move
makes more different games", you are still plain wrong. And, to mention
the definition "more different places to put the piece into"...
(**) Professionals regard 19x19 board small, and a move in one corner
can have non-tactical effects as far as the corner diagonally opposed
(i.e. on the whole board). Any player of dan level should be able to
see this, and most high kyus too. One cannot get to (high?) dan level
without taking this effect into account.
>A similar way to say it is to ask "What is a shortest possible
>way to describe the rules of the game?" Go would talk about the
>board, the one piece, the atari rule, not a lot. Chess would
>have to describe all six pieces, the en passant rule, castleing,
>two move pawns, fifty move draws, etc. By this standard, chess
>has a longer description and is more diverse.
Hm, does this mean that you define word diversity as "requires more
complex explanation"? In that case I believe many RFC's are more diverse
than chess.
But actually you miss one of the best parts of go by requiring the rules
be complex and long-winded: the rules of go are simple enough that most
anybody can learn them in a single sitting of at most half an hour. Yet
this does nothing to reduce the complexities of the game.
>Do the go players have something better? I would like to here
>more about how the chess players exposed to go start playing go,
>and go players exposed to chess keep on playing go. If I
>expanded the go board, from 19x19 to 23x23 (the next prime
>number) would that make it better or just bigger?
Expanding or reducing the board is not a taboo in go the way it seems in
chess. I have heard even professionals playing on extra-large boards
(23x23?) to see what it would be like. And it is a standard tool to
reduce the board and hence the complexity of the game when teaching
beginners: start at 9x9, next go to 13x13, then to full board. This
does not cripple game, it just shuts out some aspects and thus makes it
easier for the beginner to fathom the basics. And, indeed, it is not a
different game from go the way chess on another board would be from
chess.
And all this does not still claim that go would be a better game, just
that this "objectivity" is not. That some love chess means that it must
have some appeal, which I cannot see, but still it must be there. But
please do not claim go to be a worse game before you learn something
about it.
(And yes, I have refrained from joining this thread before since my
understanding of chess could be deeper -- I changed to go over 10 years
ago when I reached the level that it required excessive lookahead.)
--
Olli, 3 dan
E-mail: Olli.L...@Helsinki.FI ! .sig still under construction.
Blame me only for any opinions expressed. ! Never you mind, I don't either.
Peter W Gousios
>> How does `"How does go compare with chess" compare with "how do apples
>> compare with oranges"' compare with `"how does chalk compare with cheese"
>> compare with "how does go compare with chess"'?
>
>Perhaps there is not a soul in the entire world who could have more
>effectively communicated the nature of this thread. Mr. Shaw, you have
>gained my professional respect.
>
>ric...@genome.wi.mit.edu The Whitehead Institute, MIT
I like this statement too.
Point 1.
On the other end of the spectrum Go and Chess are instances of the same game!
That is finding the best path through a graph of legal board configurations
where each valid move is an arc, and each node a .
All other discussion is due to human inability to comprehend
the games in their entirty.
I like phrasing the apples to oranges comparison as follows:
Point 2.
To say something is better than something else begs the question
Better at what? You can define the what in whichever manner
leads to the point you wish to make.
This makes it extremely easy to get into arguments.
As a philosopher I find this discussion interesting, but limited in
use by the above points.
As a player of both games I enjoy both.
As a computer programmer I realize both programming tasks are very difficult.
Happy Playing. Enjoy both games.
Pete Gousios
AGA 8kyu
pe...@mail.csh.rit.edu
pwg...@cs.rit.edu
Kevin Gowen
>I am better chess player than a go player, but my chess program always beats me.
>Must be a lot harder to program go!
Not necessarily. Keep in mind that they've been writing chess programs for
computers ever since there have been computers. The first efforts date back
to the early 1950's. In contrast, serious go programming is, what, 10 years
old at the most?
It would even not be unreasonable to speculate that, when all is said and
done, go will probably turn out to be easier to progam then chess because
its rules are simpler, more elegant, and thus might easier lend themselves
to the sort of analysis that computers are good at. We'll see...
-kevin
kgo...@efn.org
Mark S. Hathaway
> ric...@genome.wi.mit.edu (Richard Resnick) writes:
>> How does `"How does go compare with chess" compare with "how do apples
>> compare with oranges"' compare with `"how does chalk compare with cheese"
>> compare with "how does go compare with chess"'?
> Perhaps there is not a soul in the entire world who could have more
> effectively communicated the nature of this thread. Mr. Shaw, you have
> gained my professional respect.
I thought he was just avoiding the question by asking other sillier ones.
Go and chess are games played by people.
They are as simple or as complex, as easy or as difficult as the people
who play them. Their rules aren't too difficult for a child to learn,
so all additional complexity or difficulty is created by the players.
Mark S. Hathaway <hath...@muvms6.mu.wvnet.edu>
John Brogan
>While go is computationaly much more complex than chess, it
>is also more amenable to the pattern matching skills of human
>beings.
Are you basing your statement that Go is "computationally much
more complex than chess" on the size of the game tree? Certainly,
Go's tree is much larger, but increasing the size of a tree does not
increase its complexity; it just makes it bigger. The structure is
the same.
Maybe "more compute-intensive than chess" is the phrase
everybody should be using in this thread. Certainly no one has
shown that Go is more "complex" than chess. In fact, it seems to me
that a reasonable case for the reverse could made. Consider: in
order to represent a position on a chess board, you must allow for
13 possible values for each square (empty, BP, WP, etc.). Only three
values are required for Go -- empty, white stone, or black stone.
Move generation for chess is orders of magnitude more complex than
that for Go, since the representation for the Go board is very nearly
a representation of all legal moves (a logical AND operation would
generate all legal moves). Tree searching techniques are the same
for Go and chess since the tree structures are identical. The only
significant operation left is the evaluation function, and since the
evaluation of a chess position or a Go position can't be quantified
with perfect accuracy, neither side can prove its case. All you can
do is argue about it.
---
John Brogan
Robert E. Maas
have to find some way to eliminate draws. I propose a margin-of-two
sudden-death match. Whenever one of the players has won two more games
than the other, that ends the match, otherwise the players keep
playing. I could imagine a Chess match like that might typically last
several days between nearly matched opponents, and Chess would turn out
to be much more tedious and exhausting than Go under such rules.
But now let's play the two games under such rules with slightly
mismatched players. The more mismatched the two players are, the higher
probability that the stronger player will indeed win the match. Suppose
we define "one rank" as the difference of skill that results in 2/3
chance of the stronger player winning a match and 1/3 chance of the
weaker player winning a match. (That would be about one amateur rank,
or three professional ranks, in Go. I don't know how many Chess
"points" it'd be, I wonder if an experiment has EVER been attempted
under these rules to calibrate Chess "points" against my definition of
"one rank" difference in skill?)
Now the purpose of this: After both games have been calibrated, we then
compare the best computer program in existance against the best human
player and see what the discrepancy is. I would bet the best human Go
player is about 20 ranks above the best Go program, while for Chess the
difference would be less than 3 ranks. Anybody want to hazard a
different prediction? Anybody want to actually do the experiment?
The point is that mechanical calculations are quite sufficient to play
Chess well enough to nearly match the best, whereas true intelligence
is needed to play Go anywhere near well. Thus Go is a good test of true
intelligence, but Chess isn't.
Note that regardless of which game is played under my margin-of-two
rules, the closer the two players are in skill the longer the match
would take, and with two exactly matched players it would theoretically
take forever. But given a nonzero difference between two players of a
fixed amount of my "rank"s, a Chess match would take a lot longer than
a Go match. So even though the claim has been made that a "Chess game"
is faster than a "Go game", actually a DECIDING Chess match would take
a LOT longer than a DECIDING Go match, and that is a more meaningful
measure than how long a "game" takes.
Jim Hill
John Brogan <jwbr...@unix2.netaxs.com> wrote:
> Maybe "more compute-intensive than chess" is the phrase
>everybody should be using in this thread. Certainly no one has
>shown that Go is more "complex" than chess. In fact, it seems to me
>that a reasonable case for the reverse could made. Consider: in
>order to represent a position on a chess board, you must allow for
>13 possible values for each square (empty, BP, WP, etc.). Only three
>values are required for Go -- empty, white stone, or black stone.
I'll venture to disagree with you here.
While Chess has a subtle and very important notion of territory and
influence (says I, who once played on a Chess team in high school as
a stand-in. Hey, at least I won my board) it's possible to write
Chess programs that will beat reasonably strong players without even
attempting to account for these concepts. Don't try this in a Go program.
Even with a comprehensive opening dictionary your program will stand no
chance on a full board against even weak players.
In both games, material advantage can be converted into a win barring
tactical disasters. The problem lies in identifying an advantage. In Chess,
piece-counting gives a serviceable first-order approximation of advantage
throughout the game. In Go, early in the game, nobody's found an equivalent.
Whatever it is, it's not simple.
I suspect that the strategic issues in both games are equally fascinating.
Not good enough at them to argue for or against that. And between strong
players the tactics are (again imho) a sort of background noise in both
games, not usually a matter for conscious thought. But in mid-level play,
the better tactical Chess player has a strong advantage; the better strategic
player has the advantage in Go. Put in more concrete terms: in Chess, a
sequence that nets you a piece is rarely a bad move; in Go, pursuit of any
tactical goal you can express in a single sentence is likely to be a bad move
early on -- you have to constantly reevaluate its worth as your opponent
responds or (shark music) doesn't.
Jim
--
Jim Hill
jth...@netcom.com.
Richard Harter
quantified; in chess it is not. In other words, there in go there is
a numeric measure of the the margin of victory.
A second difference, which is related to the first, is that handicapping
is feasible in go; I can give (or accept) komi or handicap stones.
Moreover, handicaps in go do not distort the structure of the game. In
chess handicaps (e.g. pawn and move) are crude, are only feasible between
players of substantially different levels of skill, and seriously impact
the structure of the game.
In these respects go is technically superior to chess.
--
Males are a breeding experiment run by | Richard Harter, SMDS Inc.
females -- a proving ground from which | Phone: 508-369-7398
females can cull winning genes. | SMDS Inc. PO Box 555
-- John Hartung | Concord MA 01742
Mark Chess
Maas) writes:
>I think any meaningful quantitative comparison of Chess and Go would
>have to find some way to eliminate draws. I propose a margin-of-two
>sudden-death match. Whenever one of the players has won two more games
>than the other, that ends the match, otherwise the players keep
>playing. I could imagine a Chess match like that might typically last
>several days between nearly matched opponents, and Chess would turn out
>to be much more tedious and exhausting than Go under such rules.
You didn't explain WHY you believe a Go match would finish more quickly
than a Chess match. If player A defeats player B an average of 2 out of 3
games at both Chess and Go, will not the matches be of equal duration?
>But now let's play the two games under such rules with slightly
>mismatched players. The more mismatched the two players are, the higher
>probability that the stronger player will indeed win the match. Suppose
>we define "one rank" as the difference of skill that results in 2/3
>chance of the stronger player winning a match and 1/3 chance of the
>weaker player winning a match. (That would be about one amateur rank,
>or three professional ranks, in Go. I don't know how many Chess
>"points" it'd be, I wonder if an experiment has EVER been attempted
>under these rules to calibrate Chess "points" against my definition of
>"one rank" difference in skill?)
Doesn't need to EVER have been attempted; the formula for calculating
rating already has done it. According to the formula, almost exactly 121
rating points divides players of which the higher rated defeats the lower
rated 2/3 of the time. Therefore, let's have some fun with your "one
rank" system. Let's assume Kasparov has a rating of 2800, and assume
further that 2800 is the floor, or bottom, or the 1st rank. The ranks of
the rest of us are as follows:
Rank/Rating
-----------
1 2800
2 2679
3 2558
4 2437
5 2316
6 2195
7 2074
8 1953
9 1832
10 1711
11 1590
12 1469
13 1348
14 1227
15 1106
16 985
17 864 etc.
Indeed, if Deep Thought 2 is rated in the high 2500's, the world's best
computer would be 3rd Rank, and the World Champion human 1st Rank (and
barely, at that). Most Experts at chess would be 7th Rank, and most
Masters would be 6th and 5th Ranks; Senior Masters would mostly be 4th
Rank, and nearly all Grandmasters would be 3rd Rank. Only the top 10 or
so in the world would merit 2nd Rank; and only Garry Kasparov would merit
1st Rank!
>Now the purpose of this: After both games have been calibrated, we then
>compare the best computer program in existance against the best human
>player and see what the discrepancy is. I would bet the best human Go
>player is about 20 ranks above the best Go program, while for Chess the
>difference would be less than 3 ranks. Anybody want to hazard a
>different prediction? Anybody want to actually do the experiment?
There's no experiment to do; the rating formula tells us. As far as I can
see, your analysis is correct thus far.
>The point is that mechanical calculations are quite sufficient to play
>Chess well enough to nearly match the best, whereas true intelligence
>is needed to play Go anywhere near well. Thus Go is a good test of true
>intelligence, but Chess isn't.
Now this I cannot agree with, yet. "Intelligence" must be defined. I.E.,
it could simply be that we have not yet discovered a good way of
programming Go; if in 20 years Go computers surpass 99% of Go players,
will that mean the computer is intelligent? No. I believe the elusive
key here is defining "intelligence," which is getting more and more
difficult as computers master and surpass humans at their own tasks.
It takes great intelligence to be a good chessplayer, a high degree of
reasoning ability. And it takes even more intelligence to program a
machine to do the same thing! But the machine isn't "intelligent"; it
"uses" the RESULTS of human intelligence in it's programming. Why, a
computer program is nothing more than the tangible results of great human
intelligence! A computer program "plays out" precisely what a human has
TOLD it to do!
The abstract nature of Go strategy and tactics has been difficult for
programmers to quantify or express in computer language. In that sense,
it takes more intelligence to program.
But that does not mean that Go takes more intelligence to play! It could
simply mean it's an un-computer friendly kind of intelligence! For
example, it takes some intelligence to write good poetry. But try to
write a computer program which can write good poetry, and nobody has yet!
Or write a good novel! That doesn't mean one has to be a super-genius to
write a good novel, just because a computer can't do it!
I am intrigued by Go's amateur "2/3" concept for ranks. You said that in
professional go the "2/3" concept contains 3 ranks? How often does the
higher-ranked of a one-rank-difference match win the game?
With the wonderful Elo chess rating system, we can successfully predict
the results of any match, knowing the players' ratings (I should say
"fairly accuratly predict!")
--Mark Kislingbury
Mark Chess
writes:
>One major difference between the two games is that victory in go is
>quantified; in chess it is not. In other words, there in go there is
>a numeric measure of the the margin of victory.
Nonetheless, a victory is a victory. In a war, one can count the dead to
ascertain a margin, but what is important is the ultimate victory. In
ping-pong the margin is quantified. In soccer, in football. But it
doesn't matter, because the game is played not to make a big margin of
victory, but only to win. In football, where a game is tied, given 1
second left on the 1 yard line, a team goes for the field goal, not the
touchdown. If a team has a 1-point lead, has the ball, and there's 1
minute left, they don't try to score, they try to run out the clock. Same
in basketball, with 1 minute left, with a 8-point lead, a team may well
play keep-away rather than try to score. The Brazilians won the world cup
after a 0-0 overtime, in penalty kicks over the Italians, the smallest of
victories. Yet they still are World Champs, exactly as if they won 10-0.
And they celebrated all the same. So I'm wondering why the margin of
victory is at all important, except in tie-break uses, perhaps.
Therefore the question: Is the margin of victory counted for tie-break
purposes in Go championships?
It's not counted in horse races. It's not counted in boxing matches.
It's not counted in chess. It's not counted in tennis. Let's look at
tennis. If Sampras wins at Wimbledon 0-6,0-6,7-6(7-5),7-6(10-8),7-6(7-5),
he won his sets by the barest of margins and lost his sets by the largest
of margins.... but only WINNING the set matters, regardless of score.
>A second difference, which is related to the first, is that handicapping
>is feasible in go; I can give (or accept) komi or handicap stones.
>Moreover, handicaps in go do not distort the structure of the game. In
>chess handicaps (e.g. pawn and move) are crude, are only feasible between
>players of substantially different levels of skill, and seriously impact
>the structure of the game.
I do not follow your logic here at all. Giving knight odds or rook odds
only takes one piece away from the game, and does not alter its
"structure" at all! Certainly would take one out of "book" openings! But
in go, one guy starts with more stones than the other guy, it's the same
thing. To call chess handicaps "crude" seems ridiculous to me. To me the
two games' handicapping possibilities are quite similar.
>In these respects go is technically superior to chess.
Talk about jumping to a conclusion without logical basis! "Technically
superior"? Definitions, please!
--Mark Kislingbury
Mark Chess
>One major difference between the two games is that victory in go is
>quantified; in chess it is not. In other words, there in go there is
>a numeric measure of the the margin of victory.
If chessplayers WANTED to, they could very easily determine what is a
"Margin of Victory." One possible method: The move number at which mate
is delivered. The lesser number of moves, the larger the margin of
victory.
A second method: The superiority in material value over the opponent's
material at the end of the game. This latter method would harm the nature
of the game, because it might be disadvantageous to deliver mate when one
is losing in material!
But can this problem not arise also in Go? At the last game of a match,
one player might reason, "I need a margin of victory of 10 stones in order
to win the match; therefore, I cannot play the usual strong moves which
would ensure my victory by 4 stones; I must try some tricky and risky
maneuvers which are my only chance of winning by 10 stones." In other
words, it is not enough for him to win the game, he must "win by 10."
You know, I thought the point of any game is to know "how does one win,"
and then the goal is "to win." That's why chess has no such foolish
"margin of victory" paraphernalia. Achieve goal X, and one wins. Fail to
achieve that goal, and one loses.
--Mark Kislingbury
Quinn Hubbard
mark...@aol.com (Mark Chess) writes:
> It takes great intelligence to be a good chessplayer,
Isn't this a typical misconception about chess? Aren't there many
strong players who outside of chess don't exhibit much intelligence?
Likewise, aren't there very intelligent people who do not excel at
chess?
Daniel J. Borzynski
> Maas) writes:
> >Now the purpose of this: After both games have been calibrated, we then
> >compare the best computer program in existance against the best human
> >player and see what the discrepancy is. I would bet the best human Go
> >player is about 20 ranks above the best Go program, while for Chess the
> >difference would be less than 3 ranks. Anybody want to hazard a
> >different prediction? Anybody want to actually do the experiment?
> >Chess well enough to nearly match the best, whereas true intelligence
> >is needed to play Go anywhere near well. Thus Go is a good test of true
> >intelligence, but Chess isn't.
I am not real sure where you may be posting from, but in the
United States, there has been FAR, FAR more effort dedicated to the
production of a world championship quality chess program than a world
championship Go program. Serious attempts to write a top level program
have made over at least the last 30 years, both in industry and in
academia and here and in Europe.
I would strongly suspect that had the same amount of time and
effort been dedicated to the development of a high level Go program, it
would have similiar results.
I do not deny that there have been serious attempts to write a
good Go program. I am just saying that to the best of my knowledge, the
bulk of the programming time devoted to both of these games has been for
chess, not Go.
It is a shame. Go is a fun but tough game and relatively few
people here play it.
Dan Borzynski
dj...@virginia.edu
Radford Neal
>... handicapping
>is feasible in go; I can give (or accept) komi or handicap stones.
>Moreover, handicaps in go do not distort the structure of the game. In
>chess handicaps (e.g. pawn and move) are crude, are only feasible between
>players of substantially different levels of skill, and seriously impact
>the structure of the game.
I've wondered why chess players don't give multiple move handicaps, much
as in go. I.e. white whould be allowed three moves, say, before black
moves. It seems to me that this would not fundamentally change the game,
though it would get rid of the whole opening book (perhaps not a bad thing).
(For the higher handicaps, some restrictions on the moves might be needed
to prevent immediate mate.)
Radford Neal
advice from a caterpillar
Radford Neal <rad...@cs.toronto.edu> wrote:
>I've wondered why chess players don't give multiple move handicaps, much
>as in go. I.e. white whould be allowed three moves, say, before black
>moves. It seems to me that this would not fundamentally change the game,
>though it would get rid of the whole opening book (perhaps not a bad thing).
>(For the higher handicaps, some restrictions on the moves might be needed
>to prevent immediate mate.)
Actually this is interesting... you could simply declare that the
free moves could not involve check or capture. Or you could limit
the free moves to pawns only..
Maybe some chess players might want to continue a discussion of this
Go related concept in rec.games.chess (follow-ups to..) -- I'm not
one to comment much since I gave up chess for Go years ago.
Justin
--
Justin Wells <rjw...@uwaterloo.ca, st...@sizone.pci.on.ca>
lol-la-pa-loo-za, n., slang, something outstanding of its kind.
loo-za-pa-lol-la, n., slang, someone out standing at lollapalooza.
advice from a caterpillar
Mark Chess <mark...@aol.com> wrote:
>In article <1994Aug7.0...@smds.com>, r...@smds.com (Richard Harter)
>writes:
>
>>One major difference between the two games is that victory in go is
>>quantified; in chess it is not. In other words, there in go there is
>>a numeric measure of the the margin of victory.
>
>Nonetheless, a victory is a victory. In a war, one can count the dead to
>ascertain a margin, but what is important is the ultimate victory. In
>ping-pong the margin is quantified.
This is chess-think and not very well related to the real world. Few
wars end in the absolute destruction of one side. In the Chinese
revolution one side ended up with mainland China, and the other
survived in Taiwan. In Bosnia it is unlikely that either side will
crush the other, but that the "winner" will be the one who comes away
with the largest slice of captured territory.
In that respect, war is a lot more like Go than it is like Chess.
>Therefore the question: Is the margin of victory counted for tie-break
>purposes in Go championships?
There is never a tie in Go. It isn't possible. Black is considered
to have a 5.5 point advantage for having the first move, and so White
is awarded an extra 5.5 points -- there is no way that you can have a
tie when one side has a whole number of points, and the other has a
whole number plus 1/2. Black must win by six points, or lose.
>I do not follow your logic here at all. Giving knight odds or rook odds
>only takes one piece away from the game, and does not alter its
>"structure" at all! Certainly would take one out of "book" openings! But
>in go, one guy starts with more stones than the other guy, it's the same
>thing. To call chess handicaps "crude" seems ridiculous to me. To me the
>two games' handicapping possibilities are quite similar.
Not at all. You obviously don't play Go, or not very well. A handicap
of 2-9 stones does not alter the structure of the game in that there is
no local position that can occur in a 9 stones game that cannot also
occur in an even game. This may seem a bit foreign to you since if
you don't play Go you won't realize that local positions are tactically
independent of one another in the opening of Go (although strategically
they are very inter-related).
Putting the first white stone down in a 9 stone game of Go is
more or less the same as invading a san-ren-sei in an even game.
I've played chess enough to know that when you start minus a piece
you have a situation on your hands that could never occur in a
normal chess game.
advice from a caterpillar
Daniel J. Borzynski <dj...@sonja.math.Virginia.EDU> wrote:
> I am not real sure where you may be posting from, but in the
>United States, there has been FAR, FAR more effort dedicated to the
>production of a world championship quality chess program than a world
>championship Go program. Serious attempts to write a top level program
>have made over at least the last 30 years, both in industry and in
>academia and here and in Europe.
Actually, despite all the effort I think most of the advancements in
chess programs were due to improvements in processing speed, and not
algorithmic breakthroughs. Early chess programs played chess much
better than current Go programs play Go.
Darse Billings
> Radford Neal
You are correct, Radford.
This has been mentioned time and time again, but chess players seem slow to
catch on... The best method of handicapping chess is to give extra *moves*,
not pieces.
The Japanese method of Go handicapping is to place a given number of stones
on predetermined locations (the star points). The analogous chess handicap
would be to give the weaker player a number of standard starting moves,
starting with 1. e4 2. d4 3. Nf3 4. Nc3 5. Bc4 6. Bf4 7. 0-0, and so on.
The Chinese method of Go handicapping is to allow the weaker player to
make their own choice of opening moves. This allows the player to obtain
positions that suit their style, and prevents opening preparation by the
stronger player (books have been written about playing against Japanese
handicaps). The analogous chess handicap would be to allow the weaker
player to make their own choice of opening moves, under the restriction
that no piece may be moved twice.
I have used these handicaps, and they work quite well. With a six move
handicap, the stronger player is faced with a very difficult position, and
must focus on defence to survive the early stages. Black is often forced
to give up small but permanent concessions, so White may hold the upper
hand right through to the ending.
Cheers, - Darse.
--
Go is better than Chess. Poker is more lucrative. Sex is more fun.
Darse Billings, 7 kyu; 2065 CFC; meaningless IRC sb/hand ratios:
(rayzor on IRC) Hold'em +0.22 ; HiLo Omaha +0.56
Darse Billings
>Lee Schumacher writes:
>>While go is computationaly much more complex than chess, it
>>is also more amenable to the pattern matching skills of human
>>beings.
>
> Are you basing your statement that Go is "computationally much
>more complex than chess" on the size of the game tree? Certainly,
>Go's tree is much larger, but increasing the size of a tree does not
>increase its complexity; it just makes it bigger. The structure is
>the same.
Sigh. 19x19 Go *is* computationally much more complex than 8x8 chess.
And increasing the size of the game tree *does* make it more complex.
With regard to complexity, the view that 19x19 Go is more difficult than
8x8 chess can easily be supported with results from theoretical computer
science and mathematics. I don't want to go into too much detail, but I
will try to correct some of the many misconceptions I have read during
this discussion.
> Maybe "more compute-intensive than chess" is the phrase
>everybody should be using in this thread. Certainly no one has
>shown that Go is more "complex" than chess. In fact, it seems to me
>that a reasonable case for the reverse could made. Consider: in
>order to represent a position on a chess board, you must allow for
>13 possible values for each square (empty, BP, WP, etc.). Only three
>values are required for Go -- empty, white stone, or black stone.
So the (very crude) first order estimate for the upper bound on 8x8
chess positions is 13^64 ~= 10^71. The (much less crude) first order
estimate for the upper bound on 19x19 Go positions is 3^361 ~= 10^172.
The difference is really really big. That's *two* "reallys". :-)
You can multiply the number of chess positions by the number of
particles in the observable universe, and still have a number *way*
smaller than the number of Go positions.
Chess has many additional restrictions which greatly reduce the number of
actual positions. There are typically two (and can be no more than ten)
pieces of any given type (but only one King), and no more than 32 pieces
in total; not to mention the vast number of positions not reachable from
the initial position...
True, the number of possible positions is not a good metric for the
difficultly of a game _by itself_, but it is *far* from irrelevant. A
second metric is the "decision complexity" for choosing good candidate
moves from a given position. While this notion is a relatively new
consideration to the field of strategic computer game playing, some
implications are well understood. Suffice it to say that chess and Go
both have a high decision complexity -- they are generally hard to play
well.
The board size is *extremely* relevant to the difficulty of any game
having sufficiently high decision complexity. Just as the Traveling
Salesman problem becomes much more difficult with increasing problem
size, Go and chess and checkers become super-exponentially more
difficult on larger boards. Go has been shown to be PSPACE-hard, which
means the generalized problem is in a class of problems with much
higher computational complexity than those in the NP-complete class.
This doesn't say anything about particular board sizes (so maybe 8x8
chess is more complex than 9x9 Go), but in general, all of these games
get a whole lot tougher as we increase the size of the board.
Here are the estimated number of positions for each type of game:
Estimated number of checkers positions: (DrP) ~= 10^20
Estimated number of chess positions: (ChP) ~= 10^44
Estimated number of Go positions: (GoP) ~= 10^170
By comparison, the estimated number of particles in the observable
Universe (OUP) is usually quoted at around 10^85. Other numbers are
sometimes asserted, but the values of DrP, ChP and GoP should be valid
to within a few orders of magnitude. The conclusion then, is that the
numbers very nearly follow a progression of squaring, as follows:
(GoP) ~= (OUP)^2 ~= (ChP)^4 ~= (DrP)^16.
If you take some time to absorb these numbers, you will come to the
following inescapable conclusion: Go is *much* bigger than chess.
(And since bigger is better... :-)
In fact, to say "Go is to chess what chess is to tic-tac-toe" would be
an insult to tic-tac-toe!
Someone raised the issue of illegal and unreachable positions in each
game, claiming that very few Go positions are legal. This is false.
The number of Go positions which contain groups having no liberties is
small, relative to the total number of positions. The fraction does
increase as the board becomes very full of stones, but the number of
dense positions is combinatorially dwarfed by the sparser positions.
For example, the number of positions with stones on every point
accounts for about 10^-61 (10^170/2^361) of all positions -- an almost
inconceivably tiny fraction. And even if 90% of all Go positions were
illegal (a ridiculous overestimate), the total number would still be on
the order of 10^169. We're dealing in terms of *magnitudes* here, and
quibbling about a few percent is meaningless when talking about these
huge numbers.
In any case, the fraction of illegal or unreachable positions would
seem to be much higher in chess than in Go, because of the more
restrictive rules and initial position of chess.
The fraction of positions which might actually arise in a game between
strong players is another matter entirely, and not at all easy to gauge.
But there is every reason to believe that this fraction is again much
smaller in chess, as evidenced by the more reduced branching factor and
shorter length of games.
In summary, both games have a high decision complexity, and a number
of positions combinatorially related to board size. It is therefore
unreasonable to expect a game played on 64 squares to be as deep and
computationally complex as a game played on 361.
Let me try to express this again: Go is *really* **really** big.
>Move generation for chess is orders of magnitude more complex than
>that for Go, since the representation for the Go board is very nearly
>a representation of all legal moves (a logical AND operation would
>generate all legal moves).
Duh? Representation has nothing to do with complexity. DT doesn't use
visualization when it generates chess moves at millions of positions per
second. It uses a representation which makes computation more efficient.
> Tree searching techniques are the same
>for Go and chess since the tree structures are identical.
The tree structures are *not* identical. Go has a much higher branching
factor than chess (sometimes called "bushy trees"), with no convenient
way of filtering good and bad moves. Move selection is much harder for
Go, which is one reason that conventional chess programming just doesn't
work very well for Go.
> The only
>significant operation left is the evaluation function, and since the
>evaluation of a chess position or a Go position can't be quantified
>with perfect accuracy, neither side can prove its case. All you can
>do is argue about it.
You don't need perfect quantification for a comparison -- all you need
are good qualitative measures. If the upper bound for one is less than
the the lower bound of the second, then the first must be less complex.
In so far as an evaluation function tries to determine which side is
most likely to win, the general task must be more difficult for the more
complex game, by the definition of complexity.
Chess zealots who want to argue that their game is better *might* try
claiming that generalized chess has a higher decision complexity than
generalized Go. I don't think that's true either, but at least there
is no concrete evidence to the contrary. In any case, it would be a
more interesting discussion than this silly back and forth sniping.
david carlton
> Sigh. 19x19 Go *is* computationally much more complex than 8x8
> chess. And increasing the size of the game tree *does* make it more
> complex.
No, it doesn't. It's easy to imagine a game with a larger game tree
than go which is nonetheless much much less complex than go in any
reasonable sense of the word 'complex'. And neither of those has any
obvious strong correlation to what I'm thinking of when I talk about
'good' games and 'bad games'.
david carlton
car...@husc.harvard.edu
Boy, am I glad it's only 1971...
John Tromp
> Someone raised the issue of illegal and unreachable positions in each
> game, claiming that very few Go positions are legal. This is false.
>
> The number of Go positions which contain groups having no liberties is
> small, relative to the total number of positions. The fraction does
> increase as the board becomes very full of stones, but the number of
> dense positions is combinatorially dwarfed by the sparser positions.
> For example, the number of positions with stones on every point
> accounts for about 10^-61 (10^170/2^361) of all positions -- an almost
> inconceivably tiny fraction. And even if 90% of all Go positions were
> illegal (a ridiculous overestimate), the total number would still be on
> the order of 10^169. We're dealing in terms of *magnitudes* here, and
> quibbling about a few percent is meaningless when talking about these
> huge numbers.
My intuition leads me to think that you could be significantly underestimating
the probability of illegal positions. I'm willing to make a bet that the 0.9
probability you state is a (ridiculous or not) *under*estimate. To settle this
bet, one would have to write a program generating random go positions and
checking for groups with 0 liberties. If such a group exists at least 1 out of
10 times, I win the bet.
Now, I know there are plenty of you go-programmers out there who must be
dying to try out a fun experiment like this:-)
(right, like you have nothing better to do:-)
So, go for it, and please share your results with us.
Maybe we can determine the magic probability to a digit or three...
Oh, and make your program general so
we can see how this probability changes with boardsize.
Let me provide a little stimulus by listing exact probabilities
for the 2 smallest cases:
board size probability of random position being legal
---------------------------------------------------------
1 1/3 = .333333333...
2 57/81 = .703703703...
Finding the exact probability for 3x3 is within reach but is too
much trouble to do manually...
Happy hacking!
regards,
%!PS % -John Tromp (tr...@math.uwaterloo.ca)
42 42 scale 7 9 translate .07 setlinewidth .5 setgray/c{arc clip fill
setgray}def 1 0 0 42 1 0 c 0 1 1{0 3 3 90 270 arc 0 0 6 0 -3 3 90 270
arcn 270 90 c -2 2 4{-6 moveto 0 12 rlineto}for -5 2 5{-3 exch moveto
9 0 rlineto}for stroke 0 0 3 1 1 0 c 180 rotate initclip}for showpage
Bill Taylor
|> One major difference between the two games is that victory in go is
|> quantified; in chess it is not. In other words, there in go there is
|> a numeric measure of the the margin of victory.
This leads to another idea, that has been discussed on r.g.g some time ago:-
the possibility of a "thick komi". i.e. a komi of (say) 5-8 points, with the
understanding that if black wins on the board by any such amount the game is
considered to be a tie. This could be useful in Swiss-style tournaments
where a few more ties (not *too* many) may be useful in separating those
otherwise on equal points; it could also be good for friendly games, where
most of us amateurs feel a little cheated if we lose by a mere 1/2 point, or
maybe even 2.5 points, or just lucky if we win by the same amount.
I'm surprised that the idea of a "thick komi" has never been taken seriously,
it seems a most natural and conveient one. It is totally impossible at chess.
This leads on to another thought, that surprisingly no-one has mentioned yet,
though some have veered toward the idea. Many have noted the overwhelmingly
irritating number of ties in chess, at least at the top levels, (though there
are notably far less at low levels). This is one of *the* biggest drawbacks
of chess, (though checkers is even more abysmal), and makes it the soccer of
the board game world. What we want is a game like rugby (well you'd expect a
Kiwi to make this point!), with only the very occasional draw. Go is like this
of course, at least with integer komi, and would be a little more so with the
thick komi mentioned.
As I say, others have made this point; but have not really explained what lies
behind it. And that is, that at chess (like soccer) it is FAR TOO EASY to play
for a draw; or rather, to play to avoid a loss. A strong attack can be contained
by a merely moderate defense; and this leads to boring, negative tactics and
strategy far too often. It is easy to sit back and "cruise", keeping options
open, avoiding mistakes, waiting for a chance to pounce; which all too often
never comes. Chess (and soccer) are far too often that way.
But in go, of course, such an option is never really on. Because victory is
still obtained even when the game is very balanced, the players must always be
striving for every last little advantage, the whole way through the game. The
emphasis is permanently on maintaining pressure, even attack, and there is no
real thought of "cruising" to victory, (unless one is already well ahead).
Even substantial leads in go can be lost by "cruising", chess style.
This is a very *major* difference between the two games, that leads to a whole
different "feeling" while playing them, and IMHO is a major factor in making
go the "better" game. (And this, even though there's nothing I like *better*
than cruising in chess! - sitting back and developing quietly and waiting to
win the endgame, which I usually can against my nearest rivals.)
-------------------------------------------------------------------------------
Bill Taylor w...@math.canterbury.ac.nz
-------------------------------------------------------------------------------
Give me liberties or give me death !
-------------------------------------------------------------------------------
David Forthoffer
: I think any meaningful quantitative comparison of Chess and Go would
: have to find some way to eliminate draws.
I think any meaningful comparison of Chess and Go *cannot* eliminate
draws, since draws are part of the rules of chess.
--
David Forthoffer (1k* 2260 USCF) NEC Technologies Printer Division
dav...@lpd.sj.nec.com 110 Rio Robles, San Jose CA 95134
"I'm not speaking for NEC unless I explicitly say so."
David Forthoffer
: One major difference between the two games is that victory in go is
: quantified; in chess it is not. In other words, there in go there is
: a numeric measure of the the margin of victory.
Who cares? Pros don't. I've see a pro resign a game when it was clear
he'd lose by 1.5 points. Pros only care whether they win or lose.
Same for me.
: A second difference, which is related to the first, is that handicapping
It's not related. It would be easy in chess to come up with some measure
of margin of victory, but it still wouldn't elminate draws.
: is feasible in go; I can give (or accept) komi or handicap stones.
: Moreover, handicaps in go do not distort the structure of the game. In
: chess handicaps (e.g. pawn and move) are crude, are only feasible between
: players of substantially different levels of skill, and seriously impact
: the structure of the game.
:
: In these respects go is technically superior to chess.
With respect to handicaps, go is superior to chess.
Mark Chess
(Quinn Hubbard) writes:
>> It takes great intelligence to be a good chessplayer,
>Isn't this a typical misconception about chess? Aren't there many
>strong players who outside of chess don't exhibit much intelligence?
>Likewise, aren't there very intelligent people who do not excel at
>chess?
No, I don't believe it's a misconception. Chess requires concise,
accurate, rational reasoning, a sign of intelligence. I think that if
someone is a strong chessplayer, by definition they are intelligent. Just
because when you look at them outside of chess and you don't see signs of
intelligence, it's certainly there; maybe the person is just quiet and
withdrawn.
People that are good at reason can and do apply it to other areas of life.
This holds true for mathematics, IQ tests, and other games requiring
logical thinking. They key behind intelligent thought IS rational
thinking, which employs the use of logic. I think all intelligent people
can excel (to various degrees) at chess; the key is, they may not LIKE
chess. I'm good at logic problems, but some I don't enjoy solving, and
others I do.
--Mark
Mark Chess
rjw...@undergrad.math.uwaterloo.ca (advice from a caterpillar) writes:
>Actually, despite all the effort I think most of the advancements in
>chess programs were due to improvements in processing speed, and not
>algorithmic breakthroughs. Early chess programs played chess much
>better than current Go programs play Go.
I thank you, Justin, for your correcting me on my misconceptions about Go.
I know very little about it, and I defer to your knowledge on that
subject. However, in Chess I have a great deal of knowledge both of the
game, its history, and computer chess.
And I beg to differ with your statement that most of the advances in chess
are due to improvements in processor speed. Nothing could be further from
the truth. (I would invite Feng, a programmer of Deep Thought, into the
discussion at this point and I would defer to his knowledge over mine.)
Although processor speed has helped a great deal, huge, huge leaps have
been made in translating quite abstract strategic principles into computer
language. It is very difficult to "explain" to a computer why one side
has a better position than the other. Simply counting material does not
do it! Simply counting piece mobility does not do it! We teach the
computer OUR human opinions of how to evaluate a position that it comes to
at the end of its tree; it has to take our word for it. Why, if you
merely teach a computer program the rules of chess, and tell it "Look as
far ahead as possible where you come out ahead in material while avoiding
being checkmated," believe me, this program would never surpass 1600
rating (just slightly above the rating of the average tournament
chessplayer.)
Take away every instruction in a chess program that tells it center
squares are more valuable, open files are valuable under these conditions,
king safety is important under these conditions, etc., and no matter HOW
fast a computer runs, even at 10 billions instructions per second (and
take away its opening book, since you seem to think that mere brute-force
searches can solve all problems) it will be destroyed by any expert or
master player, and probably even Class A players.
There is much literature to support my contention that
brute-force-search-alone programs can never succeed until the day that
they can calculate to the end of every chess game all the way to mate!
(which seems to be centuries away from current computer technology.)
Respectfully yours,
Mark
Jack Hahn
Fortunately I had nothing better to do so ...
It would appear that about 1.4% of 19x19 board positions are
illegal because of dead groups.
I randomly generated 10,000 board positions for board sizes 1 - 19. Here are
the results.
With board size 1, 3354/10000 of positions generated were legal
With board size 2, 7001/10000 of positions generated were legal
With board size 3, 6325/10000 of positions generated were legal
With board size 4, 5673/10000 of positions generated were legal
With board size 5, 4944/10000 of positions generated were legal
With board size 6, 4221/10000 of positions generated were legal
With board size 7, 3539/10000 of positions generated were legal
With board size 8, 2844/10000 of positions generated were legal
With board size 9, 2378/10000 of positions generated were legal
With board size 10, 1903/10000 of positions generated were legal
With board size 11, 1465/10000 of positions generated were legal
With board size 12, 1177/10000 of positions generated were legal
With board size 13, 872/10000 of positions generated were legal
With board size 14, 680/10000 of positions generated were legal
With board size 15, 480/10000 of positions generated were legal
With board size 16, 349/10000 of positions generated were legal
With board size 17, 251/10000 of positions generated were legal
With board size 18, 187/10000 of positions generated were legal
With board size 19, 139/10000 of positions generated were legal
Here's the program I used to generate this.
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
#define LONG_BITS 32
#define MAX_SIZE 30 /* Maximum board size */
#define EMPTY 3 /* We will make use of the fact that EMPTY == (WHITE | BLACK) */
#define WHITE 1
#define BLACK 2
char board[MAX_SIZE+2][MAX_SIZE+2];
char is_live[MAX_SIZE+2][MAX_SIZE+2];
unsigned long int seed;
/* Return 1 if board is legal, 0 otherwise */
static int check_legal(int board_size)
{
int i, j;
int all_alive;
int changed;
for (i = 1; i <= board_size; i++) {
for (j = 1; j <= board_size; j++) {
is_live[i][j] = board[i][j] == EMPTY;
}
}
do {
all_alive = 1;
changed = 0;
for (i = 1; i <= board_size; i++) {
for (j = 1; j <= board_size; j++) {
if (!is_live[i][j]) {
char color = board[i][j];
if ((is_live[i][j-1] && (board[i][j-1]&color)) ||
(is_live[i][j+1] && (board[i][j+1]&color)) ||
(is_live[i+1][j] && (board[i+1][j]&color)) ||
(is_live[i-1][j] && (board[i-1][j]&color))) {
changed = 1;
is_live[i][j] = 1;
} else {
all_alive = 0;
}
}
}
}
} while (changed && !all_alive);
return all_alive;
}
/* Randomly return 1, 2 or 3 */
static char rand_stone()
{
char result;
do {
seed = seed * 3141592621L + 1;
result = (seed >> (LONG_BITS-2)) & 3;
} while (result == 0);
return result;
}
/* Fill board randomly with stones */
static void randomize_board(int board_size)
{
int i, j;
for (i = 1; i <= board_size; i++) {
for (j = 1; j <= board_size; j++) {
board[i][j] = rand_stone();
}
}
}
static int one_try(int board_size)
{
randomize_board(board_size);
return check_legal(board_size);
}
main(int argc, char *argv[])
{
int board_size;
int count;
int i;
int total = 0;
seed = clock();
if (argc != 3) {
printf("Usage: go <board_size> <count>\n");
exit(1);
}
board_size = atoi(argv[1]);
count = atoi(argv[2]);
memset(is_live, sizeof(is_live), 0);
memset(board, sizeof(board), 0);
for (i=0; i<count; i++) {
total = total + one_try(board_size);
}
printf("With board size %d, %d/%d of positions generated were legal\n",
board_size, total, count);
exit(0);
}
Jack Hahn
Bill Taylor
|> One major difference between the two games is that victory in go is
|> quantified; in chess it is not. In other words, there in go there is
|> a numeric measure of the the margin of victory.
This leads to another idea, that has been discussed on r.g.g some time ago:-
advice from a caterpillar
Mark Chess <mark...@aol.com> wrote:
>No, I don't believe it's a misconception. Chess requires concise,
>accurate, rational reasoning, a sign of intelligence. I think that if
>someone is a strong chessplayer, by definition they are intelligent. Just
>because when you look at them outside of chess and you don't see signs of
>intelligence, it's certainly there; maybe the person is just quiet and
>withdrawn.
This is loopy... "intelligence" isn't a single variable which someone
either has or does not have. Human intelligence is a vast amoprhous
thing that can't accurately be described by one or two indexes (like
"good chess player", "does well on IQ tests", etc.).
One word for you: RAINMAN.
>They key behind intelligent thought IS rational
>thinking, which employs the use of logic.
Not! Perhaps the key behind intelligent thought is preceisely its
ability to grasp the irrational, the vaguely defined, and the imprecise.
With your definition of "intelligent" none of us are nearly as smart as
our computers.
By the way, do intelligent people "employ the use of" grammar?
advice from a caterpillar
Mark Chess <mark...@aol.com> wrote:
>rjw...@undergrad.math.uwaterloo.ca (advice from a caterpillar) writes:
>>algorithmic breakthroughs. Early chess programs played chess much
>>better than current Go programs play Go.
>merely teach a computer program the rules of chess, and tell it "Look as
>far ahead as possible where you come out ahead in material while avoiding
>being checkmated," believe me, this program would never surpass 1600
>rating (just slightly above the rating of the average tournament
>chessplayer.)
OK. So maybe there have been advances beyond this that are due to
something other than processor speed -- but it should be enough for
me to point out that to get a Go program to play as well as the average
tournament Go player would indeed be a colossal breakthrough.
Anyone who has played a fifty or a hundred games of Go should be able to
defeat any computer Go program that has yet been written.
That's what I meant by "early chess programs played chess much better
than the current best Go programs play Go."
The point is that brute force, in Go, won't even get you up to the
skill level of a human playing their first game. On the other hand,
computer chess programs get to *start* the heuristics at the 1600
level.
Bill Taylor
|> Fortunately I had nothing better to do so ...
:-) :-) :-) Good!
I couldn't get your program to work, but no matter, I trust your figures.
|> I randomly generated 10,000 board positions for board sizes 1 - 19. Here are
|> the results.
|>
|> With board size 1, 3354/10000 of positions generated were legal
|> With board size 2, 7001/10000 of positions generated were legal
... ... ...
|> With board size 19, 139/10000 of positions generated were legal
However I presume this is a typo, (or rather a thinko)...
|> It would appear that about 1.4% of 19x19 board positions are
|> illegal because of dead groups.
You mean 1.4% are *legal* ? (Still Darse Billing's guess was about OK.)
|> John Tromp (tr...@math.uwaterloo.ca) wrote:
|>
|> : Let me provide a little stimulus by listing exact probabilities
|> : for the 2 smallest cases:
|>
|> : board size probability of random position being legal
|> : ---------------------------------------------------------
|> : 1 1/3 = .333333333...
|> : 2 57/81 = .703703703...
Well I couldn't be bothered tackling the exact figures for 3x3, but here they
are for 3x2, for what it's worth. (Unless they're mistaken; no doubt I'll
soon be told...) I manually counted those with 3,4,5 stones, and added 64.
Board size: 3x2. Number of positions: 729. Number illegal: 236.
P(legal) = 493/729 = .6763 .
-------------------------------------------------------------------------------
Bill Taylor w...@math.canterbury.ac.nz
-------------------------------------------------------------------------------
There was this person 25 years ago; I look a little like he did, and have his
name, and some of his possessions, and many of his memories.
But he is a different person; and I absolutely disclaim any responsibility
for anything he may have done or said!
-------------------------------------------------------------------------------
John Tromp
> I couldn't get your program to work, but no matter, I trust your figures.
Hi Bill!
I couldn't resist writing a little program myself. Source included below.
Running a million samples for each square board size, I get the following
figures, which can reasonably be expected to be accurate to the given 3 digits.
Probability of random position being legal for given board size
1 .333
2 .703
3 .643
4 .564
5 .488
6 .416
7 .348
8 .288
9 .234
10 .187
11 .147
12 .113
13 .087
14 .065
15 .047
16 .035
17 .024
18 .017
19 .012
20 .008
21 .005
22 .003
23 .002
\
25 .001
\
29 .0001
\
33 .00001
\
39 .000001
So, only 1.2% of random 19x19 positions is legal.
> Well I couldn't be bothered tackling the exact figures for 3x3, but here they
> are for 3x2, for what it's worth. (Unless they're mistaken; no doubt I'll
> soon be told...) I manually counted those with 3,4,5 stones, and added 64.
>
> Board size: 3x2. Number of positions: 729. Number illegal: 236.
>
> P(legal) = 493/729 = .6763 .
With a million samples, I repeatedly compute legal(2,3) = 0.671,
i.e. I only see a variation in the 4th digit between different
1000000 sample runs. This suggest exactly 489 legal positions.
It seems safe to conclude the existence of a bug in
either your counting or in my program:)
Why add 64? The number of legal <3 stone positions seems to be 1+12+60=73?!
regards,
%!PS % -John Tromp (tr...@math.uwaterloo.ca)
42 42 scale 7 9 translate .07 setlinewidth .5 setgray/c{arc clip fill
setgray}def 1 0 0 42 1 0 c 0 1 1{0 3 3 90 270 arc 0 0 6 0 -3 3 90 270
arcn 270 90 c -2 2 4{-6 moveto 0 12 rlineto}for -5 2 5{-3 exch moveto
9 0 rlineto}for stroke 0 0 3 1 1 0 c 180 rotate initclip}for showpage
--------------program-to-compute-legality-probabilities--------------
main(argc,argv)
int argc;
char *argv[];
{
int sd,ht,wd,tr,sc,c,h,t,w,l[99],r[99],cl[99];
if (argc==1) {
printf ("usage: %s width [height] [trials]\n", argv[0]);
exit(0);
}
ht = atoi(argv[1]);
wd = argc > 2 ? atoi(argv[2]) : ht;
tr = argc > 3 ? atoi(argv[3]) : 1000;
srandom(getpid());
for (sc=t=0; t++<tr;) {
for (w=0; w<=wd; w++) {
cl[w] = 3;
l[w] = r[w] = w;
}
for (h=ht; h--;) {
for (w=1; w<=wd; w++) {
if (c = random() % 3) {
if (cl[w] == 3-c) {
if (r[w] == w) goto nt;
l[r[l[w]] = r[w]] = l[w];
l[w] = r[w] = w;
}
if (cl[w-1] == c && r[w-1] != w) {
l[r[l[w]]=r[w-1]] = l[w];
l[r[w-1] = w] = w-1;
}
if (!cl[w-1]) r[w] = l[r[w]] = 0;
} else {
r[l[w]] = l[r[w]] = r[w-1] = l[r[w-1]] = 0;
l[w] = r[w] = 0;
}
cl[w] = c;
}
}
for (w=1; w<=wd; w++) {
if (r[w] == w) goto nt;
l[r[l[w]] = r[w]] = l[w];
}
sc++;
nt: ;
}
printf("legal(%d,%d)=%.6f\n",wd,ht,sc/(float)tr);
}
advice from a caterpillar
Mike Thomas <tho...@agcs.com> wrote:
>This is just a lot of ignorant nonsense. The early chess programs were
>pathetically weak, often so severely flawed that they could not
>administer mate in a simple won game. Some of the early programs
>were almost comic in their efforts. I recall one that would sacrifice
>anything to avoid check and another that couldn't figure out how to
>deliver a back rank mate with king and rook. They would frequently
>go berserk and attempt illegal moves or just crash.
Your idea of what constitutes a decent chess playing program is biased
by the excellent play people have come to expect. The major point is
that, despite all the errors you mention, early chess playing programs
were far superior to current go playing programs.
>Mr. Wells is typical of the 'failed chessplayer' who takes up the
>game of go.
Screw the caraicatures. Or, if you want to play this game, "Mike
Thomas is typical of the failed debater. Having exhausted his
ability to make effective points, and feeling defensive, he takes
up the game of tossing insults in order to brow beat his interlocutor
into submission."
You had a relatively well reasoned argument until this. Now you just
look like a blithering idiot.
I happen to think chess is a fine game. I also happen to think that
the ability of a machine to play a game is no measure of the quality
of the game so far as human players are concerned. I'm just pointing
out the simple fact that the state of the art of computer science has
not and cannot produce a Go program that plays as effectively as
computer chess programs do. It will take some sort of advance in
computer science to get there.
Jonathan Cano
: jh...@crl.com (Jack Hahn) writes:
: :-) :-) :-) Good!
Well, I got 240 illegal positions for a 2x3 board Bill :^). I could
be wrong though.
I wrote a program to generate all possible Go positions for a NxM
board and then check each of these positions for illegal
configurations (i.e. groups with 0 liberties).
Below are my results so far. after 3x3 boards the runs begin to take a
long time :^). Below is the data I've generated so far and, for the
extremely bored, the program I used to generate the data (in case you
want to go bug hunting).
--Jonathan
P.S. I was suprised at the large number of illegal positions for
larger boards (4x4 etc...) but after doing some inspection of my
program in a debugger and looking at sample board positions I believe
that the data is correct.
=========================================================================
Notes:
I'm casting long longs to longs and then using printf() to display the
"legal", "illegal" and "total" counters so the actual numbers output
for these values will be wrong for large boards. The quotients should
be ok though.
"total" is the total number of board positions possible (total=3^(NxM)).
---------------------- legal go boards data ---------------------------------
Thu Aug 11 09:48:38 PDT 1994
total = 3
rows = 1, columns = 1
legal = 1, illegal = 2
illegal / total = 0.666667
legal / total = 0.333333
legal / illegal = 0.500000
Thu Aug 11 09:48:39 PDT 1994
***********
Wed Aug 10 19:03:52 PDT 1994
total = 9
rows = 1, columns = 2
legal = 5, illegal = 4
illegal / total = 0.444444
legal / total = 0.555556
legal / illegal = 1.250000
Wed Aug 10 19:03:52 PDT 1994
***********
Wed Aug 10 19:03:52 PDT 1994
total = 27
rows = 1, columns = 3
legal = 15, illegal = 12
illegal / total = 0.444444
legal / total = 0.555556
legal / illegal = 1.250000
Wed Aug 10 19:03:52 PDT 1994
***********
Wed Aug 10 19:03:52 PDT 1994
total = 81
rows = 1, columns = 4
legal = 41, illegal = 40
illegal / total = 0.493827
legal / total = 0.506173
legal / illegal = 1.025000
Wed Aug 10 19:03:52 PDT 1994
***********
Wed Aug 10 19:03:52 PDT 1994
total = 243
rows = 1, columns = 5
legal = 113, illegal = 130
illegal / total = 0.534979
legal / total = 0.465021
legal / illegal = 0.869231
Wed Aug 10 19:03:52 PDT 1994
***********
Wed Aug 10 19:03:52 PDT 1994
total = 729
rows = 1, columns = 6
legal = 313, illegal = 416
illegal / total = 0.570645
legal / total = 0.429355
legal / illegal = 0.752404
Wed Aug 10 19:03:52 PDT 1994
***********
Thu Aug 11 09:48:39 PDT 1994
total = 81
rows = 2, columns = 2
legal = 57, illegal = 24
illegal / total = 0.296296
legal / total = 0.703704
legal / illegal = 2.375000
Thu Aug 11 09:48:39 PDT 1994
***********
Wed Aug 10 19:03:52 PDT 1994
total = 729
rows = 2, columns = 3
legal = 489, illegal = 240
illegal / total = 0.329218
legal / total = 0.670782
legal / illegal = 2.037500
Wed Aug 10 19:03:52 PDT 1994
***********
Wed Aug 10 19:03:53 PDT 1994
total = 6561
rows = 2, columns = 4
legal = 4125, illegal = 2436
illegal / total = 0.371285
legal / total = 0.628715
legal / illegal = 1.693350
Wed Aug 10 19:03:53 PDT 1994
***********
Wed Aug 10 19:03:53 PDT 1994
total = 59049
rows = 2, columns = 5
legal = 35117, illegal = 23932
illegal / total = 0.405291
legal / total = 0.594709
legal / illegal = 1.467366
Wed Aug 10 19:03:53 PDT 1994
***********
Wed Aug 10 19:03:53 PDT 1994
total = 531441
rows = 2, columns = 6
legal = 299681, illegal = 231760
illegal / total = 0.436097
legal / total = 0.563903
legal / illegal = 1.293066
Wed Aug 10 19:03:57 PDT 1994
***********
Thu Aug 11 09:48:39 PDT 1994
total = 19683
rows = 3, columns = 3
legal = 12675, illegal = 7008
illegal / total = 0.356043
legal / total = 0.643957
legal / illegal = 1.808647
Thu Aug 11 09:48:39 PDT 1994
***********
Wed Aug 10 19:03:58 PDT 1994
total = 531441
rows = 3, columns = 4
legal = 321689, illegal = 209752
illegal / total = 0.394685
legal / total = 0.605315
legal / illegal = 1.533664
Wed Aug 10 19:04:02 PDT 1994
***********
Wed Aug 10 19:04:02 PDT 1994
total = 14348907
rows = 3, columns = 5
legal = 8180343, illegal = 6168564
illegal / total = 0.429898
legal / total = 0.570102
legal / illegal = 1.326134
Wed Aug 10 19:06:05 PDT 1994
***********
Wed Aug 10 19:06:05 PDT 1994
total = 387420489
rows = 3, columns = 6
legal = 208144601, illegal = 179275888
illegal / total = 0.462742
legal / total = 0.537258
legal / illegal = 1.161030
Wed Aug 10 20:08:49 PDT 1994
***********
Thu Aug 11 09:48:39 PDT 1994
total = 43046721
rows = 4, columns = 4
legal = 24318165, illegal = 18728556
illegal / total = 0.435075
legal / total = 0.564925
legal / illegal = 1.298454
Thu Aug 11 09:55:03 PDT 1994
***********
Wed Aug 10 20:15:35 PDT 1994
total = -808182895
rows = 4, columns = 5
legal = 1840058693, illegal = 1646725708
illegal / total = 0.472276
legal / total = 0.527724
legal / illegal = 1.117404
Thu Aug 11 06:22:30 PDT 1994
------------ stuff.c (the program the generated the data) -------------------
#include <stdio.h>
#include <assert.h>
#include <memory.h>
#include <limits.h>
#include <math.h>
#define DEBUG 0
#define TRUE 1
#define FALSE 0
#define ROWS -1
#define COLUMNS ROWS
#define MAXROWS 10
#define MAXCOLUMNS MAXROWS
#define EMPTY 0
#define BLACK 1
#define WHITE 2
#define BOARDER 3
#define BREATHING 1<<5
#define MARKED 1<<6
#define EMPTYCHAR '.'
#define BLACKCHAR '#'
#define WHITECHAR 'O'
#define BOARDERCHAR '='
typedef struct board_struct {
char b[MAXROWS][MAXCOLUMNS];
int rows, cols;
} Board;
unsigned long long myExp(unsigned long long b,int e);
void initBoard(Board *b);
void printBoard(Board b);
void incrementBoard(Board *b);
int hasBreath(Board *b,int i, int j);
int isLegalBoard(Board b);
Board b;
main(int argc, char *argv[])
{
unsigned long long i,limit;
unsigned long long legalcnt, illegalcnt, currentlegal;
if(argc != 3)
{
fprintf(stderr, "error: wrong number of parameters\n");
fprintf(stderr, "need <rows> <cols> parameters\n");
fflush(stderr);
exit(1);
}
if ((b.rows = atol(argv[1])) < 1)
{
fprintf(stderr, "error: 1st parameter less than 1 %d\n",b.rows);
fflush(stderr);
exit(1);
}
if ((b.cols = atol(argv[2])) < 1)
{
fprintf(stderr, "error: 2nd parameter less than 1 %d\n",b.rows);
fflush(stderr);
exit(1);
}
legalcnt = 1; /* count the empty board which we don't bother to */
/* test.*/
illegalcnt = 0;
initBoard(&b);
#if DEBUG
printBoard(b);
#endif
i=-1;
limit=myExp(3,b.rows*b.cols);
printf("total = %d\n",(long)limit);
printf("rows = %d, columns = %d\n\n",b.rows, b.cols);
printf("EMPTY = %d\n",EMPTY);
printf("BLACK = %d\n",BLACK);
printf("WHITE = %d\n",WHITE);
printf("i = %f\n",(float)i);
printf("log10(i)= %f \n",log10((float)i));
printf("log3(i)= %f \n",log10((float)i)/log10(3.0));
printf("sqrt(log3(i))= %f \n",sqrt(log10((float)i)/log10(3.0)));
limit=myExp(3,b.rows*b.cols);
for(i=1; i < limit; i++)
{
incrementBoard(&b);
#if DEBUG
printBoard(b);
#endif
((currentlegal = isLegalBoard(b)) == TRUE) ?
legalcnt++ : illegalcnt++;
#if DEBUG
fprintf(stdout," i = %d , legal= %d, illegal = %d, current legal=%s\n",
(long) i, (long)legalcnt, (long)illegalcnt, (currentlegal == TRUE)? "yes":"no" );
putc('\n',stdout);
#endif
}
printf("legal = %d, illegal = %d \n",(long)legalcnt, (long)illegalcnt);
printf("illegal / total = %f \n", ((float)illegalcnt)/limit);
printf(" legal / total = %f \n", ((float)legalcnt)/limit);
printf(" legal / illegal = %f \n", ((float)legalcnt)/illegalcnt);
}
void
printBoard(Board b)
{
int i,j;
for(i=0; i<b.rows+2; i++)
{
for(j=0;j<b.cols+2; j++)
{
switch(b.b[i][j]) {
case EMPTY:
putc(EMPTYCHAR,stdout);
break;
case BLACK:
putc(BLACKCHAR,stdout);
break;
case WHITE:
putc(WHITECHAR,stdout);
break;
case BOARDER:
putc(BOARDERCHAR,stdout);
break;
default:
assert(1);
break;
}
}
putc('\n',stdout); /* putc('\n',stdout); */
}
fflush(stdout);
}
void
initBoard(Board *b)
{
int i,j;
/* initialize top row */
for(i=0; i < b->cols+2; i++)
{
b->b[0][i]=BOARDER;
}
/* initialize bottom row */
for(i=0; i < b->cols+2; i++)
{
b->b[b->rows+1][i]=BOARDER;
}
/* initialize left row */
for(i=0; i < b->rows+2; i++)
{
b->b[i][0]=BOARDER;
}
/* initialize right row */
for(i=0; i < b->rows+1; i++)
{
b->b[i][b->cols+1]=BOARDER;
}
for(i=1; i< b->rows+1; i++)
{
for(j=1; j<b->cols+1; j++)
{
b->b[i][j]=EMPTY;
}
}
}
void
incrementBoard(Board *b)
{
int i,j, pos, limit;
pos = 0;
i= (pos / MAXCOLUMNS) +1;
j= (pos % MAXCOLUMNS) +1;
limit = b->rows * b->cols + 1;
while( ++(b->b[i][j]) > WHITE && (pos < limit))
{
b->b[i][j]=EMPTY;
pos++;
i= (pos / b->cols) +1;
j= (pos % b->cols) +1;
}
}
unsigned long long
myExp(unsigned long long b,int e)
{
int i;
unsigned long long result;
for(result=1,i=0; i<e;i++)
{
result*=b;
}
return result;
}
int
isLegalBoard(Board b)
{
int i,j;
int result=TRUE;
Board tmpb;
memcpy(&tmpb,&b, sizeof(tmpb));
for(i=1; i<b.rows+1 && result == TRUE; i++)
{
for(j=1; j<b.cols+1; j++)
{
if(tmpb.b[i][j] == BLACK || tmpb.b[i][j] == WHITE)
{
/* note tmpb[i][j] has not been marked BREATHING */
if(hasBreath(&tmpb,i,j) == FALSE)
{
result = FALSE;
break;
}
}
}
}
return result;
}
int
hasBreath(Board *b,int i, int j)
{
int result=FALSE;
/* check for neighboring breaths */
if (b->b[i][j-1] == EMPTY ||
b->b[i-1][j] == EMPTY ||
b->b[i][j+1] == EMPTY ||
b->b[i+1][j] == EMPTY ||
/* or neigbors that have been marked BREATHING */
(b->b[i][j-1] & BREATHING && b->b[i][j-1] & b->b[i][j]) ||
(b->b[i-1][j] & BREATHING && b->b[i-1][j] & b->b[i][j]) ||
(b->b[i][j+1] & BREATHING && b->b[i][j+1] & b->b[i][j]) ||
(b->b[i+1][j] & BREATHING && b->b[i+1][j] & b->b[i][j]) )
{
b->b[i][j] |= BREATHING;
result=TRUE;
}
else /*do a depth first search of our neigbors to see if they are */
/*connected to a stone with a breath. Stop when we find a */
/*stone with a breath and mark the stones in the path from us */
/*to the stone with the breath as BREATHING*/
{
b->b[i][j] |= MARKED;
if (b->b[i][j-1] == (b->b[i][j] ^ MARKED) && hasBreath(b,i,j-1) == TRUE)
{
b->b[i][j] |= BREATHING;
result=TRUE;
}
else if (b->b[i][j+1] == (b->b[i][j] ^ MARKED) && hasBreath(b,i,j+1) == TRUE)
{
b->b[i][j] |= BREATHING;
result=TRUE;
}
else if (b->b[i-1][j] == (b->b[i][j] ^ MARKED) && hasBreath(b,i-1,j) == TRUE)
{
b->b[i][j] |= BREATHING;
result=TRUE;
}
else if (b->b[i+1][j] == (b->b[i][j] ^ MARKED) && hasBreath(b,i+1,j) == TRUE)
{
b->b[i][j] |= BREATHING;
result=TRUE;
}
else
{
result = FALSE;
}
}
/* b->b[i][j] ^= MARKED; */
return result;
}
Bill Taylor
|> Hi Bill!
Hi John!
|> I couldn't resist writing a little program myself. Source included below.
Well, I couldn't get yours to work either! But at least I got further with
it. The other one didn't even compile; yours compiled and ran, but didn't seem
to produce any output! Must be something wrong with our unix/c here.
|> Running a million samples for each square board size, I get the following
Thanks for the figures.
|> which can reasonably be expected to be accurate to the given 3 digits.
Yep, seems about right. I notice they agree pretty much with the earlier ones,
allowing for those ones' lesser accuracy.
|> > P(legal) = 493/729 = .6763 .
|>
|> With a million samples, I repeatedly compute legal(2,3) = 0.671,
|> i.e. I only see a variation in the 4th digit between different
|> 1000000 sample runs.
Right again!
|> It seems safe to conclude the existence of a bug in
|> either your counting or in my program:)
Aaaaargh! I knew I'd get to hear about it. The mistake was mine. (sob)
|> Why add 64?
Sorry, I wasn't clear. I counted the *illegal* positions by hand, involving
3,4 & 5 stones. I added in 64 for the illegal positions involving 6 stones,
i.e. *all* such positions, all illegal. (I didn't bother to count these. :) )
|> This suggest exactly 489 legal positions.
Yep, your program's suggestion was quite right! Although I'd counted twice,
and got the same answer, I'd *still* left out a squad of 4 cases. After your
report, and thus knowing 4 (rather than 8) were probably missing, I soon
found them. For what it's worth,
the last 4 that eluded me for so . O .
long were this (and its iso-forms)... O X O
Bugger it! Fun though. So yes, P(legal) = 489/729. (for 2x3 boards)
Thanks for your work, John. Always like your articles.
You should post more often.
-------------------------------------------------------------------------------
Bill Taylor w...@math.canterbury.ac.nz
-------------------------------------------------------------------------------
Watch out for my definitive series of books on Prime Numbers.
Just coming into print now... volume I: "The Even Primes"
-------------------------------------------------------------------------------
John Tromp
> tr...@math.uwaterloo.ca (John Tromp) writes:
>
> |> It seems safe to conclude the existence of a bug in
> |> either your counting or in my program:)
>
> Aaaaargh! I knew I'd get to hear about it. The mistake was mine. (sob)
Well, not entirely. I discovered a bug in my program (posted earlier) too.
But the situations it mishandles are too rare to cause a noticable effect
on the numbers.
I include below a corrected version, as well as a variation that computes
an exact count of the number of legal go positions of a given size.
Jonathan Cano was kind enough to post another such program a few days ago,
allowing me to compare results (thanks, Jonathan!).
I'm happy to report that the results match perfectly. which
should give a high confidence that both Jonathan and my program are bug-free.
(given that the two programs use vastly different methods).
> Thanks for your work, John. Always like your articles.
Thanks Bill. And likewise!
regards,
%!PS % -John Tromp (tr...@math.uwaterloo.ca)
42 42 scale 7 9 translate .07 setlinewidth .5 setgray/c{arc clip fill
setgray}def 1 0 0 42 1 0 c 0 1 1{0 3 3 90 270 arc 0 0 6 0 -3 3 90 270
arcn 270 90 c -2 2 4{-6 moveto 0 12 rlineto}for -5 2 5{-3 exch moveto
9 0 rlineto}for stroke 0 0 3 1 1 0 c 180 rotate initclip}for showpage
---------estimate probability of a random go position being legal----------
int ht,wd,l[99],r[99],cl[99];
int legal() /* legality of random (ht,wd) go board */
{
int c,y,x;
for (x=0; x<=wd; x++)
cl[l[x] = r[x] = x] = 3;
for (y=ht; y--;) {
for (x=1; x<=wd; x++) {
if (c = random() % 3) {
if (cl[x] == 3-c) {
if (r[x] == x) return 0;
l[r[l[x]] = r[x]] = l[x];
l[x] = r[x] = x;
}
if (cl[x-1] == c && l[x]|r[x-1]) {
l[r[l[x]]=r[x-1]] = l[x];
l[r[x-1] = x] = x-1;
}
if (!cl[x-1]) r[x] = l[r[x]] = 0;
} else l[x] = r[x] = r[l[x]] = l[r[x]] = r[x-1] = l[r[x-1]] = 0;
cl[x] = c;
}
}
for (x=1; x<=wd; x++) {
if (r[x] == x) return 0;
l[r[l[x]] = r[x]] = l[x];
}
return 1;
}
main(argc,argv)
int argc;
char *argv[];
{
int tr,sc,t;
if (argc==1) {
printf ("usage: %s width [height] [trials]\n", argv[0]);
exit(0);
}
ht = atoi(argv[1]);
wd = argc > 2 ? atoi(argv[2]) : ht;
tr = argc > 3 ? atoi(argv[3]) : 1000;
srandom(getpid());
for (sc=t=0; t++<tr; sc += legal()) ;
printf("%.6f\n",sc/(float)tr);
}
-----------count number of legal go positions of given size----------------
int ht,wd,l[5],r[5],cl[5];
unsigned long legal(y,x)
{
int i,c,lx,rx,rlx,lrx,rx1,lrx1,bc;
unsigned long cnt;
if (x > wd) {
x = 1;
if (++y > ht) {
for (x=wd; x; x--)
for (i=x; i=l[i];)
if (i==x) return 0L;
return 1L;
}
}
bc=cl[x]; rlx=r[lx=l[x]]; lrx=l[rx=r[x]]; lrx1=l[rx1=r[x-1]];
cl[x] = l[x] = r[x] = r[l[x]] = l[r[x]] = r[x-1] = l[r[x-1]] = 0;
cnt = legal(y,x+1);
for (c = 1; ; c++) {
cl[x]=bc; r[l[x]=lx]=rlx; l[r[x]=rx]=lrx; l[r[x-1]=rx1]=lrx1;
if (c == 3) return cnt;
if (bc == 3-c) {
if (r[x] == x) continue;
l[r[l[x]] = r[x]] = l[x];
l[x] = r[x] = x;
}
if (cl[x-1] == c && l[x]|r[x-1]) {
l[r[l[x]]=r[x-1]] = l[x];
l[r[x-1] = x] = x-1;
}
if (!cl[x-1]) r[x] = l[r[x]] = 0;
cl[x] = c;
cnt += legal(y,x+1);
}
}
main(argc,argv)
int argc;
char *argv[];
{
int i;
unsigned long cnt,tot;
if (argc==1) {
printf ("usage: %s width [height]\n", argv[0]);
exit(0);
}
ht = wd = atoi(argv[1]);
if (argc > 2)
if ((i = atoi(argv[2])) < wd)
wd = i;
else ht = i;
if (wd > 4) {
printf ("minumum dimension %d too large\n", wd);
exit(0);
}
for (i=0; i<=wd; i++)
cl[l[i] = r[i] = i] = 3;
cnt = legal(1,1);
for (i=wd*ht,tot=3L; --i; tot *= 3L) ;
printf("%ld legal, %ld illegal, prob %.6f\n",cnt,tot-cnt,cnt/(float)tot);
}
---------------------------------end---------------------------------------
Darse Billings
>Darse Billings writes:
>>jwbr...@unix2.netaxs.com (John Brogan) writes:
>> >Lee Schumacher writes:
>> >>While go is computationaly much more complex than chess, it
>> >>is also more amenable to the pattern matching skills of human
>> >>beings.
>> > Are you basing your statement that Go is "computationally much
>> >more complex than chess" on the size of the game tree? Certainly,
>> >Go's tree is much larger, but increasing the size of a tree does not
>> >increase its complexity; it just makes it bigger. The structure is
>> >the same.
>>Sigh. 19x19 Go *is* computationally much more complex than 8x8 chess.
>>And increasing the size of the game tree *does* make it more complex.
> Sneeze. Here's a quick example to show that increasing the size
>of the game tree does *not* make it more complex.
> We'll call the game Stop and play it on a 101x101 board using
>White and Black stones. White moves first by placing a stone on any
>unoccupied square. Black does the same. Play alternates in this manner
>until all the squares have been filled. The winner is the one with the
>most stones on the board at the end of play.
> The game tree for Stop is much bigger than the one for Go. It is
>unimaginably bigger. In the vast universe of Stop, Go doesn't amount to
>a grain of sand, so if "increasing the size of the game tree *does* make
>it more complex" we would expect Stop to be incomprehensible to mere
>humans. But this is not the case.
Get a grip. Throughout the article, I emphasized that the game size is
important *provided* the game has sufficient decision complexity. Since
I was talking about Go, the statement is valid. For more information on
the concept of decision complexity, see the following article:
L V Allis, H J van den Herik, and I S Herschberg, "Which Games Will Survive?",
Heuristic Programming in Artificial Intelligence II -- the Games of the
Second Computer Olympiad}, (1990), 232-243.
"Stop" is a well known example of a game with zero decision complexity,
resulting in a trivial strategy. Go-Moku (connect five-in-a-row) is a
game with relatively low decision complexity, and is a win for the first
player (on a 15x15 board, and almost certainly true in general). Go and
chess are games with high decision complexity, so increasing the board
size has a super-exponential effect on the computational solvability
(and, we reasonably expect, the overall strategic difficulty) of the game.
>>With regard to complexity, the view that 19x19 Go is more difficult than
>>8x8 chess can easily be supported with results from theoretical computer
>>science and mathematics.
> Based on what, the size of the game tree? Is adding a column of
>5 numbers more complex than adding a column of 4 numbers? Making a task
>more compute-intensive does not necessarily make it more complex.
Based on the arguments I went on to give.
>>I don't want to go into too much detail,
>
> Understandable.
Clearly the small amount of detail I did give was too much for you
handle, even if your reading skills had been adequate.
>...[rest of stupid rebuttal laughingly ignored]
Ron_Ko...@transarc.com
cleaning just administered by Mr. Brogan! Incredible! By simply providing a
concrete example that matched all the criteria of his adversary's general
statements, he reduced the entire argument to self-contradiction and futility.
This must be the most amazing posting ever in the classic Chess/Go thread!
> From: jwbr...@unix1.netaxs.com (John Brogan)
>
>> Darse Billings writes:
>>
...
> Sneeze. Here's a quick example to show that increasing the size
> of the game tree does *not* make it more complex.
> We'll call the game Stop and play it on a 101x101 board using
...
Darse Billings
Roy_La...@mindlink.bc.ca (Roy Langston) writes:
>In article <325ucc$9...@scapa.cs.ualberta.ca>, da...@cs.ualberta.ca (Darse
>Billings) writes:
>>
>> Here are the estimated number of positions for each type of game:
>>
>> Estimated number of checkers positions: (DrP) ~= 10^20
>> Estimated number of chess positions: (ChP) ~= 10^44
>> Estimated number of Go positions: (GoP) ~= 10^170
>>
>> Someone raised the issue of illegal and unreachable positions in each
>> game, claiming that very few Go positions are legal. This is false.
>>
>> The number of Go positions which contain groups having no liberties is
>> small, relative to the total number of positions. The fraction does
>> increase as the board becomes very full of stones, but the number of
>> dense positions is combinatorially dwarfed by the sparser positions.
>> For example, the number of positions with stones on every point
>> accounts for about 10^-61 (10^170/2^361) of all positions -- an almost
>> inconceivably tiny fraction. And even if 90% of all Go positions were
>> illegal (a ridiculous overestimate), the total number would still be on
>> the order of 10^169. We're dealing in terms of *magnitudes* here, and
>> quibbling about a few percent is meaningless when talking about these
>> huge numbers.
>The last sentence above is probably true. I brought up the issue of
>liberty-less groups primarily in the interest of accuracy. Further to that
>end...
"In the interest of accuracy", you say? How noble.
>The 90% quoted above is actually a ridiculous underestimate. The greatest
>number of combinations is found when the numbers of White stones, Black
>stones and empty points are all roughly the same. These are fairly dense,
>endgame-type positions, and a very large fraction (>>99%) are illegal. It
>should be fairly easy to write a program that scatters equal numbers of
>Black, White, and empty points randomly across the board, and then checks
>for liberty-less groups. I'm betting almost all such positions are
>illegal, and that the proportion of illegal positions rises very rapidly as
>the board gets fuller. I would like to see the actual results of such an
>experiment, though.
Hmmmm... Given the evidence from the two independent programs, it seems
that both of our intuitions were wrong. But I was several orders of
magnitude closer than you were, so there! :-)
The 10^170 number of positions is the one most often quoted in the
literature, but I confess I did not take the time to compute the actual
fraction of illegal positions. If correct, 10^170 would imply about two
percent legal positions, give or take an order of magnitude, after
accounting for board symmetry.
Let's look at this question as a probability problem. Suppose each point
may have a White stone, Black stone, or be Empty with equal probability.
As a crude approximation, assume all points have four adjacent points,
having 81 (3^4) possible configurations. For a Black stone on such a
point, only one of the 81 possible surroundings is a capture, while 65
(3^4 - 2^4) have an Empty, making the stone legal. The remaining 15
cases have at least one adjacent Black stone, which adds more potential
liberties. Clearly, the probability that any given stone is legal is
very good, at least 65/81. On the other hand, *all* stones on the board
must meet this criteria, so we have to raise this base probability to
the power N, where N is the number of stones on the board (typically
around 240).
This kind of trade-off is exactly the type of combinatorial problem in
which intuition can be led astray, so we must tread carefully (much more
carefully than either of us did). An ultra-safe, but crude lower bound
on legal positions is (65/81)^240 ~= 10^-23.
But 65/81 ~= 80% is much too low, because 15 of the 16 remaining cases are
legal with high probability. Let's guess, conservatively, that a further
70% of extended stones are safe (because with three extra liberties we
have an immediate 19/27 ((3^3 - 2^3)/3^3) chance of hitting an Empty).
This changes our base probability to 65/81 + 0.70*(15/81) ~= 0.932.
Now our (still very safe) lower bound is 0.932^240 ~= 10^-9. So already
we have one in a billion positions that are legal (more than you thought),
and we're just getting warmed up...
If we want to be optimistic and say that all indeterminate positions
are alive, then a crude approximation for an *upper* bound would be
(80/81)^240 ~= 0.0507, or about 5% legal positions. Hmmm... my guess
was clearly too low. But given the generally favourable second order
effects on group safety, I would be willing to bet that the actual
number is (geometrically) closer to 0.05 than 0.000000001. Admittedly,
this is an easy bet after seeing the empirical evidence from the
computer programs. :-)
Since this is an interesting problem, let's do a more careful second order
approximation.
*** Math Mode On ***
All non-geeks may wish to skip this boring section, although I will try
to keep it "user friendly". :-)
On a 19x19 board, we have three types of intersections: 17x17 = 289
internal points, 17x4 = 68 edge points, and 4 corners.
case 1: corner stones
This case won't matter much for large boards, since there can only
be four corners. But we can show that our 70% guess for secondary
survival is clearly on the low side by looking at this case.
There are 3^2 = 9 corner situations, 5 of which contain an Empty and one
of which is a capture. Extending with one stone again leaves us with
two liberties, for a nice recurrence. Even if only the barest minimum
5/9 of those cases are safe, we have (5/9) + (5/9)*(3/9) ~= 0.741 chance
of survival. With the complete recurrence, it's over 80%, so we really
have been pessimistic in our earlier analysis. Two neighbouring stones
is even better, but let's just stick to our low estimate of 80% and say
that a corner stone has a (5/9) + 0.80*3/9 ~= 0.822 chance of being in a
legal group.
case 2: edge stones
An edge stone has 3^3 = 27 possible surroundings, 19 of which contain
an Empty and one of which is an illegal position.
One friendly neighbour may increase the group liberties by either three
(toward the middle) or two (along the edge). The edge extension doesn't
help as much, but we know that 80% is still a conservative estimate for
overall group safety. We can improve this by splitting the subcases, but
for simplicity let's just call it a (19/27) + 0.80*(7/27) ~= 0.911 chance
of goodness.
Two neighbours adds four extra chances of not being dead yet, so now we
are safe in at least (65/81) + 0.933*(4/81) + 0.984(11/81) ~= 0.982 of
these three cases, as described in the next section (internal points).
Having the whole family around gives us five more chances, being safe
more than (211/243) + 0.80*(5/243) + 0.982*(26/243) ~= 0.990 of the time.
Putting these together, we conclude that edge stones are safe in better
than (19/27) + ( (3*0.911 + 3*0.982 + 1*0.990) / 27) ~= 0.951 of cases.
case 3: internal points
As stated, 65 of 81 cases are immediately legal. Of the remaining 16
cases, the number of neighbouring stones of the same colour (Black) is
either zero (the capture case), one (4 cases), two (6 cases), three (4
cases), or all four (one case).
For indeterminate cases, we need a better guess for the chance of the
extended group being legal, since 80% is clearly too low. One stone
creates three new chances of life, and thus another 19/27 chance of
safety, suggesting a simple recurrence on three liberties for a lower
bound. Taking this recurrence to only two terms gives us an estimate of
(19/27) + (7/27)(19/27) ~= 0.886, and feeding that back into itself gives
(19/27) + 0.886*(7/27) ~= 0.933. This can be improved by solving the
simple recurrence and by splitting subcases, but let's just stop here.
With one extending stone, there are (usually) three new points adjacent
to the group. We could be close to an edge, but let's disregard this
minor glitch. This yields a 19/27 chance of group safety, seven
indeterminate cases, and one case where we are surrounded by White stones
(dead group). This gives us at least a (19/27) + 0.933*(7/27) ~= 0.946
chance of group safety with respect to the initial stone.
With two neighbouring stones, there can either be five or six new
group liberties, with the average being (2*5 + 6)/3 = 5.33. Following
the same pattern as above, we have 3^(16/3) ~= 350 cases, of which 310
are okay and 39 are indeterminate. We'll continue to use the 93.3%
approximation for unclear groups, although this is certainly an
underestimate given the increased number of liberties. The final
number comes out to be at least a 0.990 chance of group safety.
With three extending stones, there are always seven new group liberties,
so we have 3^7 = 2187 cases, of which 2059 are safe and 127 are nearly
safe. Even with the low estimates, we still get a 0.996 chance of
legality.
Lastly, with a clump of five stones there are eight new liberties, which
yields a ((3^8-2^8)/3^8) + 0.933*(2^8-1)/3^8 ~= 0.997 conservative
estimate on survival.
Putting all these numbers together in the proper proportion gives us
65/81 + ( (4*0.946 + 6*0.990 + 4*0.996 + 1*0.997) / 81) ~= 0.984,
or more than a 98% chance that a random internal stone is alive.
*** Math Mode Off *** (please forgive minor errors, as I
haven't had much coffee yet...)
Now we are ready to approximate the lower bound on legal positions for
any sized rectangular board. The actual number could be considerably
higher, because we have been conservative and because we have not taken
other factors into consideration which improve the chance of legality.
One such factor is that this fraction does not reflect the *overall*
average of legal positions. Denser positions than the ones we have
looked at cannot have many fewer positions (on an absolute scale),
because we are already down to a few percent. The equally vast number
of sparser positions, on the other hand, can have a significantly higher
fraction of legal positions, skewing the overall number upward.
On our assumed equi-probable 19x19 Go board, we will have stones on two
thirds of each type of intersection. If all of the points were internal
(as in torical Go), a lower bound would be 0.984^(361*2/3) ~= 0.0206, or
about two percent. To emphasize how important the base percentage is,
notice that 0.98 would give a frequency of 0.00773 -- almost a three
fold decrease just for rounding down the base percentage! It is not
much wonder that intuition can lead us astray...
For the actual Go board with edges and corners, we do somewhat worse,
because dead stones are more likely on the outside. Treating each type
of stone independently gives us an estimate of 0.984^(289*2/3) *
0.951^(68*2/3) * 0.822^(4*2/3) ~= 0.0447 * 0.1025 * 0.5929 ~= 0.00272,
which is lower than 361 internal points by a factor of ten.
Now that we can see just how sensitive the base percentage is, it is not
hard to imagine that a tertiary analysis could improve the expected
number of legal positions to over one percent of all positions. But at
this point I am prepared to accept the results of the computer programs,
which suggest between 1.2% and 1.4%. [Thank-you, gentlemen! -drb]
The consequence of all this is that many positions are illegal, but the
fraction is relatively small compared to the exponential growth in the
total number of positions with increasing board size. Go does not get
proportionally smaller as the board gets bigger -- it grows, by a lot.
Furthermore, we know without a doubt that Go (and chess and checkers
and Hex) will get a whole lot tougher *strategically* as the board size
increases (unless P=NP=PSPACE and the whole hierarchy of complexity
classes collapses).
>Another point: an extremely large fraction of all go positions are illegal
>because there are widely divergent numbers of Black and White stones, and
>no way to arrive at the position through legal play (assuming suicide to be
>illegal).
This is false. Be careful about distinguishing *illegal* positions from
*unreachable* positions, and further distinguishing those positions which
are merely *unlikely to occur in practice* . They are very different
concepts.
An example of an illegal chess position is one in which the player to
move is able to capture the King. Some examples of unreachable chess
positions include having 32 total pieces and doubled pawns; or eight
White pawns and three White knights (or two White bishops on dark
squares). An example of a position that is unlikely to occur in
practice might have one side with 16 pieces while the other is down to
a lone King (although I have seen such positions in elementary school
tournaments :-).
In Go, *all* legal positions are also reachable, because players have the
option to pass. In contrast, in chess many legal positions are not
reachable. One combinatorially significant factor affecting the number of
reachable chess positions is the severe restriction on the (simultaneous)
number of pieces of each type.
How we go about counting the number of "likely" positions is not at all
obvious. For Go, I suppose we could impose a nearly equal number of
stones of each type (eg. assume no stones are captured and no passes are
made, or that the number of stones of each type are the same within 10%,
etc). But notice that the analysis we have done has already made most
of these assumptions, and the positions that are "likely to occur" have
the same properties as those we've looked at. To say now that many of
those are "illegal" (meaning "unlikely") is a very weak statement, and
unfair in comparison to the relatively paltry number of chess positions.
It should be obvious that there are far more "likely" Go games than
"likely" (or even plausible) chess games. In Go, the branching factor
is much larger, there are more candidate moves per position, and the
games last much longer, on average.
>These considerations probably mean that GoP is around 10^160, and perhaps
>as low as 10^150 (still more than a googol of go positions for every chess
>position { :- O ). Again, I would like to see a mathematically credible
>estimate of the true number. I believe the number of legal chess positions
>has been estimated using fairly sophisticated criteria for legality.
There you go again, tossing around numbers like confetti. You casually
suggest differences of ten in the exponent -- factors of a billion or a
*billion* billions -- without having the slightest basis for removing
even a single digit!
You proudly proclaim to defend the "interest of accuracy", and then you
suggest a number which appears to be off by a multiplication factor of
*one hundred quintillion*? Shame on you!
With all the preceding analysis and the empirical evidence of the computer
programs, we still arrive at an estimated number of *legal* Go positions
close to the 10^170 value I have maintained all along. Perhaps there are
other factors not yet accounted for, and if so, I'd be more than pleased
to see a better analysis.
>> Go is *really* **really** big.
>Oh, yeah. Really ***really*** yeah.
Well, at least we agree on that. :-)
John Brogan
>jwbr...@unix2.netaxs.com (John Brogan) writes:
> >Lee Schumacher writes:
> >>While go is computationaly much more complex than chess, it
> >>is also more amenable to the pattern matching skills of human
> >>beings.
> >
> > Are you basing your statement that Go is "computationally much
> >more complex than chess" on the size of the game tree? Certainly,
> >Go's tree is much larger, but increasing the size of a tree does not
> >increase its complexity; it just makes it bigger. The structure is
> >the same.
>
>Sigh. 19x19 Go *is* computationally much more complex than 8x8 chess.
>And increasing the size of the game tree *does* make it more complex.
of the game tree does *not* make it more complex.
We'll call the game Stop and play it on a 101x101 board using
unoccupied square. Black does the same. Play alternates in this manner
until all the squares have been filled. The winner is the one with the
most stones on the board at the end of play.
The game tree for Stop is much bigger than the one for Go. It is
unimaginably bigger. In the vast universe of Stop, Go doesn't amount to
a grain of sand, so if "increasing the size of the game tree *does* make
it more complex" we would expect Stop to be incomprehensible to mere
humans. But this is not the case.
>8x8 chess can easily be supported with results from theoretical computer
>science and mathematics.
5 numbers more complex than adding a column of 4 numbers? Making a task
more compute-intensive does not necessarily make it more complex.
>but I will try to correct some of the many misconceptions I have read
>during this discussion.
> > Maybe "more compute-intensive than chess" is the phrase
> >everybody should be using in this thread. Certainly no one has
> >shown that Go is more "complex" than chess. In fact, it seems to me
> >that a reasonable case for the reverse could made. Consider: in
> >order to represent a position on a chess board, you must allow for
> >13 possible values for each square (empty, BP, WP, etc.). Only three
> >values are required for Go -- empty, white stone, or black stone.
>
>So the (very crude) first order estimate for the upper bound on 8x8
>chess positions is 13^64 ~= 10^71. The (much less crude) first order
>estimate for the upper bound on 19x19 Go positions is 3^361 ~= 10^172.
>
>The difference is really really big. That's *two* "reallys". :-)
to the number of possible Stop positions. The (more or less exact) first
order estimate for the upper bound on 101x101 Stop positions is 3^10201,
or roughly 10^4867. The difference between Stop and Go utterly dwarfs
that between Go and chess.
>You can multiply the number of chess positions by the number of
>particles in the observable universe, and still have a number *way*
>smaller than the number of Go positions.
position, and then multiply the number of Go positions by the total
number of particles in all those universes, and then multiply this again
by the number of Go positions, and, well, you get the picture.
>True, the number of possible positions is not a good metric for the
>difficultly of a game _by itself_, but it is *far* from irrelevant. A
>second metric is the "decision complexity" for choosing good candidate
>moves from a given position. While this notion is a relatively new
>consideration to the field of strategic computer game playing, some
>implications are well understood. Suffice it to say that chess and Go
>both have a high decision complexity -- they are generally hard to play
>well.
here, is much too vague a concept to be used to decide which of two games
is more "difficult" (which is itself fuzzy).
Let's add a rule to the game of Stop. Let's say that if either side
get's a horizontal row of 101 stones, he automatically loses. This
introduces strategy into the game, something that was missing before since
random play always led to a White win. Now, White cannot play randomly
and still expect to win all of his games.
Now, you may object that this new rule does not give Stop a "high
decision complexity," but without a rigorous definition of the term, your
objection would be meaningless. Suppose, though, that I agree with your
objection. I might then propose a new rule: vertical rows of 101 stones
also lose. You might then make the same objection. I might then propose
changing the 101-stone rules to 51-stone rules. We might eventually
decide to add 51-stone diagonals to the losing formations. We might
change
the 51-stone rules to 21-stone rules.
(I'll bet you would say that each of these new rules makes the game
more and more complex, wouldn't you? Did you also notice that each one
of these rules reduces the size of Stop's game tree?)
Does Stop have a "high decision complexity" yet? Any answer you give,
you must see by now, is subjective and arbitrary. The truth is that the
very concept of "decision complexity" is only a descriptional convenience
in the absence of a general algorithmic solution to a particular game. If
a general solution to n x n Go were known, the value of n would have no
effect on its "complexity," although it would have a great effect on the
practical problem of applying the algorithm to obtain a solution. In
other words, higher values of n would mean more computation. It is the
difference between adding 3 numbers and adding a billion numbers. Since
a general algorithm is known for doing this, adding a billion numbers does
not seem any more "complex" than adding 3 numbers.
[tree sizes for various games deleted for brevity]
>
>If you take some time to absorb these numbers, you will come to the
>following inescapable conclusion: Go is *much* bigger than chess.
conclusion. Are we reading the same newsgroups?
>In fact, to say "Go is to chess what chess is to tic-tac-toe" would be
>an insult to tic-tac-toe!
legal positions in each game, it wouldn't be correct.
>In summary, both games have a high decision complexity, and a number
>of positions combinatorially related to board size. It is therefore
>unreasonable to expect a game played on 64 squares to be as deep and
>computationally complex as a game played on 361.
>Let me try to express this again: Go is *really* **really** big.
>Move generation for chess is orders of magnitude more complex than
>that for Go, since the representation for the Go board is very nearly
>a representation of all legal moves (a logical AND operation would
>generate all legal moves).
>Duh? Representation has nothing to do with complexity. DT doesn't use
>visualization when it generates chess moves at millions of positions per
>second. It uses a representation which makes computation more efficient.
Move generation is the single most time-consuming operation in chess
programs. This is why many of the best chess computers, including DT,
have moved this function into hardware -- it just eats up too many clock
cycles.
Move generation in a Go program would be one of the very fastest
operations because it is so simple. One of the things that makes it
so simple is this: you can represent the Go board in such a way that a
single AND operation would generate all legal moves. There is no way to
do this in chess.
I don't know a simpler way to put it, Darse. If your response is
still along the lines of "Duh?", I don't think I can help you.
By the way, this doesn't just apply to computers. Human Go players,
from the time they first learn the game, never have any problem "seeing"
what moves are available. This is a huge stumbling block for chess
players, one that never completely goes away.
> > Tree searching techniques are the same
> >for Go and chess since the tree structures are identical.
>The tree structures are *not* identical. Go has a much higher branching
>factor than chess (sometimes called "bushy trees"), with no convenient
>way of filtering good and bad moves.
not identical because Go has a higher branching factor than chess is the
same as saying the structures are not identical from one move to the next
in a single game of chess, since each new position is likely to have a
different branching factor from that of its parent. But this is not true.
When I said "tree searching techniques are the same...", I was
referring to things like pruning techniques, killer heuristics, obviously
the basic minimax approach, maybe even something introduced (I think) by
FHH himself called singular extension heuristics.
An extremely simple, quick 'n dirty example of pruning:
1. White moves X, Black moves Y, White moves Z
2. White moves Z, Black moves Y, White moves X
Although these move sequences would represent two separate branches
in the game tree, the sub-trees beginning with White's second move are
absolutely identical, and since investigating both would be pointless,
one
can be "pruned." You'll notice that I didn't specify whether the game
was
Go or chess. That's because it doesn't matter. It works on the game trees
of *BOTH* games because their structures *are* identical.
********************** Bottom line **************************
It is utterly meaningless to say that Go is more "difficult" than
chess. Do you mean that it's more difficult to reach your objective,
i.e., defeat your opponent? Actually, it's more difficult to win in
chess than in Go, since the weaker side has more defensive resources in
chess than in Go. Go has no draws.
Perhaps you mean that it's more difficult to play Go "well" than it
is to play chess "well." No matter what you mean by "well," I'm sure
that's true for some people and not true for others. Depends on
individual
aptitudes.
The only other thing I can think of that you might mean is that it's
more difficult to play Go perfectly than it is to play chess perfectly.
I have no idea if this is true or not, but if it is, it's true in the same
sense that it's harder to throw a rock to the sun than to the moon. We
can't do either one, can we?
The last word, as far as I'm concerned, is yours, Darse. Wrap it up,
continue it forever, put up some more *really* *really* big numbers,
whatever. I don't know how it happened, but this is the longest message
I've ever posted anywhere by a country mile. I'm tired, and I want to
read for a while. And maybe change my name.
---
John Brogan
Brad Culter
John Brogan <jwbr...@unix1.netaxs.com> wrote:
>
> The last word, as far as I'm concerned, is yours, Darse. Wrap it up,
>continue it forever, put up some more *really* *really* big numbers,
>whatever. I don't know how it happened, but this is the longest message
>I've ever posted anywhere by a country mile. I'm tired, and I want to
>read for a while. And maybe change my name.
Well said, John. Thanks. Too bad it probably won't change
Darse's perspective, eh?
>
>---
>John Brogan
>
>
Boy Cosmonaut
>I happen to think chess is a fine game. I also happen to think that
>the ability of a machine to play a game is no measure of the quality
>of the game so far as human players are concerned. I'm just pointing
>out the simple fact that the state of the art of computer science has
>not and cannot produce a Go program that plays as effectively as
>computer chess programs do. It will take some sort of advance in
>computer science to get there.
I would suggest that the complexity of a game has meaning only when
the system that is making the decision of what move to make next is
taken into account. Thus, for a system that primarily performs brute-
force tree search (e.g. a Cray), chess requires much less computation
than go. For a system that can match spatial patterns very quickly
as well as perform some slow tree searching (e.g. a human), the two
games seem more or less computationally equivalent. Perhaps there
are other architectures for which go is *much* easier than chess.
(Ever tried to write a villanelle in APL?)
An interesting question: What size chessboard would produce the
same average number of legal moves/position as go? (Assuming that
with a 12x12 chessboard, for example, each side would have an extra
queen, rook, bishop, knight, and four extra pawns.)
Just my $0.02.
Matt
Darse Billings
>Never before have I seen somebody's clock cleaned as thoroughly as the
>cleaning just administered by Mr. Brogan! Incredible! By simply providing a
>concrete example that matched all the criteria of his adversary's general
>statements, he reduced the entire argument to self-contradiction and futility.
Then with all due respect, sir, you too missed the salient point, which
is that Go, and chess, are not trivial games. Evidently, I failed to
make this expressly clear. Please read the reference I gave on decision
complexity before you buy into his irrelevant diatribe.
His counter-argument is analogous to showing that the Traveling Salesman
problem is utterly simple, because the problem size doesn't matter when
you change the goal from finding the shortest circuit to buying souvenirs.
>This must be the most amazing posting ever in the classic Chess/Go thread!
Well, I was amazed too, but apparently for quite different reasons...
You can lead a person to knowledge, but you can't make them think.
Darse Billings
Look, I'm sorry if I sound over-bearing, but this happens to be a topic
that I have studied closely and know a fair amount about. It is quite
frustrating to hear these ad hominem rebuttals to some very sound science.
Try looking at it from my perspective. Suppose a novice chess player
tells you that it is advantageous to move your Queen out at the earliest
opportunity. How do you respond?
Well, if you care enough to comment at all, you will hopefully listen to
their point of view and then carefully explain why other considerations
are more important, making it generally unfavourable to expose the Queen
so early.
Now suppose the less experienced player tells you that you are full of
it, because an open Queen can make more threats and threats are good --
and they are adamant in this position. Do you change your opinions on
early Queen moves? How do you react to insults from others who have
heard this discussion? It isn't a very pleasant situation.
Perhaps the best you can do is to stop caring, and let them suffer with
their beliefs, as I shall now do. You cannot teach those who will not
listen.
John Hoggatt
A straightforward analysis shows that Go is much more complex than chess.
Either game is too difficult for humans to play properly.
I am a fairly strong chessplayer and fancy myself as a reasonably bright
person, but I've somehow never been able to learn Go. I will tell the
tale of the time I tried to learn, for what it is worth.
My friend E---- took it as a personal insult from the Universe that
I could always trash him at chess and bridge and poker and skat and ....
He therefore resolved to teach me to play Go and got me in front of a board,
despite my reluctance to get another game addiction started. He explained
the rules. They sounded simple enough. I then asked him for some quick
strategic pointers, to mitigate my inevitable dreadful drubbing. 'You want
me to explain joseki to you before you'll play a game?' he hooted. 'There's
no way to learn the game without playing it.' I managed to extort a promise
from him to explain what was happening as we went along, and he gave me
nine stones in odds. He told me that he wasn't a great player, but that
maximal odds were about right at this stage.
Since I had no real clue about what I should be doing, I just tried to
arrange my stones into attractive patterns. His comments took the form,
'That's not very good,' until we were fairly well into the game, when he
suddenly started saying, 'Jesus! I'm busted! How on Earth did this happen?'
I was unable to tell him. The board just looked as if a bunch of stones
had been dumped on it from a moderate height. We finished up and I did
in fact control more territory so I guess I won. We tried three times
more, with steadily decreasing odds from him, but about the same result.
So, I was 4-0 at Go, without the slightest understanding of how this
came about. If I were asked to explain today how territorial control is
reckoned up, I would have to hold a rule sheet and read it aloud. Certainly
I've forgotten E----'s explanation to me. Somehow, my victories did not
fill me with lust for battle and the urge for more -- my reaction was
more like total bafflement. E----, for some reason, lost the motivation
to make me learn Go, so the entire project languished.
Conclusions? I have none to offer. It is not possible that I really
was playing Go well in those games, since my play-selection process had
nothing to do with the rules of the game. My plays were, as I recall,
generated by a rather puerile aesthetic method. Is it credible that a
player can, after study of Go, actually become weaker than a completely
random opponent? [The idea that E---- was throwing those games would
not be entertained by anyone who saw how astonished and frustrated he
was at their course.] What actually was going on in those games?
-----------------
John Hoggatt, FIDE master -- or, kill me.
Hans Plensdorf
convert the devotees of that noble sport to baseball on the grounds
that the baseball, being only 1/8 the diameter of the soccer ball,
enjoys the possibility of landing in 10^42 locations on the field,
whereas the larger soccer ball is restricted to 10^14 locations. Even
accounting for the fact that many of the locations in which the
baseball lands during the course of the game are in foul ground and
out of play, we're talking about orders of magnitude here.
John Hoggatt
Mr. Plensdorf's posting is absolutely perfect of its kind. Bravo!
-----------------------
J. Hoggatt, FIDE master --or, kill me.
Brad Trusso
(John Hoggatt) writes:
> In article <32r7g7$k...@freenet3.scri.fsu.edu>, hpl...@freenet1.scri.fsu.edu
> (Hans Plensdorf) writes:
> |> that the baseball, being only 1/8 the diameter of the soccer ball,
> |> enjoys the possibility of landing in 10^42 locations on the field,
> |> whereas the larger soccer ball is restricted to 10^14 locations. Even
> |> out of play, we're talking about orders of magnitude here.
>
> Mr. Plensdorf's posting is absolutely perfect of its kind. Bravo!
While I sympathize with the intent, "absolutely perfect" mathematical
satire should be mathematically correct. For starters, a baseball is
about 1/4 the diameter of a soccer ball, and thus covers about 1/16
the area on the ground. If we are trying to compare non-overlapping
positions, we want the cross-sectional area. But whether we use 1/4,
1/8, or 1/16, we're still just speaking of roughly a single order of
magnitude. Thus if there are about 10^42 baseball locations, there
are more like 10^41 soccer locations, not 10^14.
(If we allow overlapping positions, such as a millimeter apart,
there are an infinity of such positions infinitessimally far apart.
Then the whole question is moot. If we limit ourselves to overlapping
positions at least some finite distance apart (say a millimeter), the
size of the ball is irrelevant. And the difference between a square
millimeter and the size of a baseball is only a couple orders of
magnitude.)
Of course the above assumes the two fields are about the same size.
Within an order of magnitude, they are. But that is nowhere near
10^42 times the cross-sectional area of a baseball. Very roughly (and
for magnitude calculations that is close enough), a baseball field is
300 feet by 300 feet, or 90,000 (10^5) square feet. (A soccer field
is about 300 by 100, 30,000 square feet.) A baseball's cross-section
is somewhere between one (10^0) square foot and 1/10 (10^-1) square
foot. So there are roughly 10^6 non-overlapping baseball positions,
not 10^42. We end up comparing 10^6 baseball positions to maybe 10^5
soccer positions, only about one order of magnitude. 10^42 go
positions versus 10^14 chess positions is a difference of 28 orders of
magnitude.
In summary, Mr. Plensdorf's otherwise clever post fell flat for me
for precisely the reason Darse made his original post; it completely
confuses differences of many orders of magnitude. Darse was right;
people have no intuitive understanding of such great differences.
- Brad Trusso (1 kyu AGA; about 1850 USCF when I gave up chess long ago)
Benjamin K Shisler
Some people thump bibles, others, insurance policies. You must excuse
certain go players who are a little hasty to condemn chess. It is
just that most of us are ex-chess players and feel that we have
"seen the light", that go is better than chess in every way and why
anyone would persist in such a petty game could only be because they
have not yet heard the Word of God. So we minister to the heathen
in the hopes that if just one soul is saved, that is worth offending
the entire remaining chess population.
Obviously that is a bad idea.
None-the-less, the fact remains that some chess players eventually
discover they prefer go. This is often after some initial resistance.
Others find go too different, hard, abstract or whatever and many
have difficulty just learning the absolute basics. Finding a good
teacher is virtually a must.
It is my sincere hope that chess players will give go a try. If you had
a bad experience already, try finding a better teacher. If you still
find go not worth the effort, THOU SHALT BURN IN ETERNAL HELLFIRE!!! :)
You have been warned,
--Rev. Ben Shisler :)
John Hoggatt
Obviously Mr. Trusso is looking at the Mr. Plensdorf's posting from a
different angle than I was. If it were mathematical satire, as Mr. Trusso
alleges, his point would be well taken, but clearly its intent is rather
_reductio ad absurdum_. Orders of magnitude are entirely irrelevant to
the real force of Mr. Plensdorf's implicit argument. The reduction to
absurdity remains, whatever numbers might be substituted. The go people's
posts to rec.games.chess, generally, have a humourless aspect which I
hope is not characteristic of the go community.
-------------------
J. Hoggatt, FIDE master I am not speaking for Pacific Bell.
Richard=Churchill%G...@bangate.compaq.com
Recognizing the presence and significance of Mr. Shisler's smiley
faces, I herewith offer my personal reaction to the ongoing debate
concerning the relative worths of chess and go. If I offend anyone,
to bad. This is personal opinion, and I am under no obligation to
agree with anyone else on this basis.
I have tried go, play it occasionally, and have been doing so about
thirty years. I have tried chess, play it frequently, and have been
doing so for about thirty years. Having learned both at roughly the
same time, neither had a dominant hold on me that had to be overcome
before acceptance of the other. I prefer chess. But this is purely a
matter of personal preference, and I recognize it as such.
The problem I have with so many go playersb who prosyletize (sp)
on behalf of their preferred game is not that I think they are "wrong,"
but that they seem so incapable of understanding and accepting a
difference in personal preference. I accept that their preferences
differ from mine. Fruther, many of them seem determined to prove to
the world that their preferred game is the "right" game, that it is in
some way qualitatively and objectively superior to chess, and that
this supposed superiority has some moral/ethical weight. I believe
this to be among the grossest of conceits.
Now, Mr. Shisler raises the point that some chess players discover
go, and become "converts." As converts, they go forth and seek to
conquer the world for their new faith. But does the fact that some
people make such a discovery and find go preferrable mean that
go is better than chess? No, it just means that they prefer go. If
there is an apparent lack of people who play go, then discover
chess, finding that they prefer chess, do not credit go with being
superior on this basis either. Rather, look at the culture. In this
and most "western" nations, individuals are far more likely to be
exposed to chess than to go, and hence more likely to learn to play
chess long before ever learning that their is a game called "go."
Consider the case of cultures in which go predominates over chess.
In both China and Japan, there are chess-like games which are
quite popular. Go has not irradicated these games, and likely
never will. Also, western chess is becoming more popular. I
suspect there is a debate those countries in which some of those
who have "discovered" chess try valiantly to convince go players
of the superiority of chess, while many go players wish such chess
players would kindly leave them alone to enjoy go. There are also
certainly those who discover chess, and never warm to it, deeply
offending or mystifying the earnest chess evangelists. I sympathize
with the go players, in such a circumstance, and believe they should
not be bothered by the boorish persons who insisting that they have
in some way made a serious mistake in preferring go.
Actually, the behaviour of the evangelical go players reminds me
of several people I have known, over the years. I will not call them
friends, as I generally tired of their company within a short period,
and spent years wishing they would leave me alone. These people
spent their lives "discovering" things, which they found utterly
enthralling, and immediately began pushing on others. They would
discover "the best" beer, cardgame, sport, or whatever, and simply
could not understand why anyone would continue to bother with the
old "inferior" alternatives. I would sometimes try one or another
item/activity so recommended ... after all, I could be missing some-
thing ... and even developed a preference for the new item/activity,
once in a while. Often, though, the "new" whatever was something
I bhad already tried, and discarded ... which could really offend their
sensibilities. In such cases, things would often deteriorate to a
point when I would say to such a person what I here repeat to the
more rabid evangelical go players. "I'm sorry, but I just don't agree.
Our personal preferrences differ. I recognize your right to disagree
with me, but as you will not recognize my right to disagree with you,
I am sick of your company. Please go away and leave me alone."
sincerely,
Richard
---------------------------------------------------------------------------------------------------------
The opinions expressed herein are mine, and do not reflect the
opinions of anyone else who does not explicitly choose to profess
agreement. If you don't agree with me, fine. You go play your
game in your corner, and I'll do likewise in my corner with my
game.
Brad Trusso
> Obviously Mr. Trusso is looking at the Mr. Plensdorf's posting from a
> different angle than I was. If it were mathematical satire, as Mr. Trusso
> alleges, his point would be well taken, but clearly its intent is rather
> _reductio ad absurdum_. Orders of magnitude are entirely irrelevant to
> the real force of Mr. Plensdorf's implicit argument. The reduction to
> absurdity remains, whatever numbers might be substituted. The go people's
> posts to rec.games.chess, generally, have a humourless aspect which I
> hope is not characteristic of the go community.
Yes, I agree that Mr. Plensdorf was cleverly making an important
point. If he had referred to 10^6 baseball positions and 10^5 soccer
positions, the mathematician in me wouldn't have been quite so
offended. 8^)
Even if there are ten times as many baseball positions, no one
believes that makes baseball ten times better than soccer. The
position where the ball lands is just a small part of the game. But
with chess and go, the changing positions of the pieces ARE the game.
The number of possibilities are a prime factor in how difficult it is
for a computer program to generate possible moves and evaluate the
resulting positions in any reasonable time. Some posts showed no
appreciation for the incredible combinatorial explosion go programs
face. I think it was computer go that Darse had in mind with his
post.
That said, the way humans play go and chess is another matter. People
have an amazing ability to lump together and dismiss vast numbers of
similar mediocre moves. The game revolves around finding that
relative handlful of good moves and trying to pick the best. People
can do that much better faster than go programs using the traditional
techniques that work so well with chess. Trying to figure out how to
get a computer to do what people do so easily can be fascinating.
There aren't 10^28 more good go moves to consider from a given
position. Even if there are ten times as many, that doesn't make go
ten times as complex or ten times better. You could argue that the
greater number of good moves means it is easier to find a move that's
"good enough" against all but a professional player.
Differences in magnitude are critical for computer go, but basically
irrelevant for people. What counts is how much you enjoy the challenge
of evaluating the trade-offs involved. I happen to prefer go. Your
mileage may differ. 8^)
- Brad Trusso
Ken Warkentyne
John Hoggatt <j4ho...@mccoy.srv.PacBell.COM> wrote:
>In article <BTRUSSO.94...@squarethru.ADS.COM>, btr...@squarethru.ADS.COM (Brad Trusso) writes:
>|> While I sympathize with the intent, "absolutely perfect" mathematical
deleted]
> The reduction to
>absurdity remains, whatever numbers might be substituted. The go people's
>posts to rec.games.chess, generally, have a humourless aspect which I
>hope is not characteristic of the go community.
But I thought Mr. Trusso was simply continuing the joke. Be careful,
the absence of smiley faces does not imply an absence of humour.
--
Ken Warkentyne - war...@ltisun.epfl.ch
Laboratoire de Teleinformatique, EPFL, Suisse.
Mr. E. Nowell
: Herr Shisler (sorry, I misplaced the address) wrote:
: Consider the case of cultures in which go predominates over chess.
It takes about ten years hard work to become very good at anything,
eg to reach Grandmaster level at chess. Almost all GMs have been
playing chess since early childhood.
Since very few Westerners learn of Go at an early age, very few
Westerners have the chance of reaching the Go equivalent of GM
level, since beyond childhood they don't have the time to devote
to intense study of something which is not of interest to them
professionally.
Eric Nowell
Richard=Churchill%G...@bangate.compaq.com
I fail to see how Mr. Nowell's comment relates in any way to the citation
from my posting. What does the theory that it takes x number of years
to achieve a particular level have to do with what I was describing, which
is a hypothesis that may help "us" understand why some go players so
earnestly and doggedly push go on those who are not interested, and
further implying that I commiserate with go players in cultures dominated
by go who may well encounter similar evangelical chess players.
Further, I wish to restate, in paraphrase, the closing statements of my
post. I have tried chess and go. I prefer chess. This is purely personal
preference. Now, LEAVE ME AND OTHERS WHO PREFER CHESS ALONE!
We are not interested, and you have over-worn your welcome!
Richard
----------------------------------------------------------------------------------------------------------------
The opinions expressed by me herein are mine, and not those of any
other party or parties who do not specifically and explicitly profess
agreement. If you don't like what I say, tough. This is my opinion,
and that is yours. We both have full and equal rights to our own
opinions.
Dave Ring
>have difficulty just learning the absolute basics. Finding a good
>teacher is virtually a must.
I disagree. Finding another beginner is an absolute must. Otherwise it
is too easy to get discouraged.
--
Dave Ring | If you would like to participate in the Internet
dwr...@tam2000.tamu.edu | FreeCell Project or find out what it is, email me.