HDTenEightyP/NetNews huggingface dataset:
From: jfbuss@maytag.uwaterloo.ca (Jonathan Buss)
Subject: Re: complexity of go
Organization: University of Waterloo
Date: Fri, 11 Sep 1992 17:41:29 GMT

In article <1992Sep9.210426.4107@hpcvusn.cv.hp.com> mark@.cv.hp.com writes:
>In article <BuBt97.6z5@watdragon.uwaterloo.ca>, jfbuss@maytag.uwaterloo.ca (Jonathan Buss) writes:
>  ...
>> In technical jargon, go is "exponential-time hard".  Roughly speaking,
>> that means that to make the game twice as hard to analyze, it is only
>> necessary to add a small amount to the board size.  ...
>
>While the number of legal board positions goes up exponentially as the
>board size increases, it does not follow that the difficulty in analyzing
>the game follows the same progression.

Absolutely correct.  That there are an exponentially growing number of
board positions does not imply that the complexity of analysis grows
exponentially.  Even so, the complexity of evaluating a given position
as a win or loss for black (or white) *does* grow exponentially.  The
proof was discovered by J. M. Robson; unfortunately, I don't know the
precise reference.  A weaker result was proved in D. Lichtenstein and
M. Sipser, "Go is PSPACE-hard", Journal of the Association of
Computing Machinery,, vol 27, 1980, pp 393-401.

Persons interested only in playing go don't really care -- none of us
is perfect anyway.  But the mathematically inclined may find the proof
interesting.

Jonathan Buss
From: cgay@sisters.cs.uoregon.edu (Carl L. Gay)
Newsgroups: rec.games.go
Subject: How does byo-yomi work on IGS?
Date: 16 Sep 92 01:55:45 GMT
Reply-To: cgay@cs.uoregon.edu
Organization: University of Oregon Computer and Information Sciences Dept.


I've looked around in the various go archive sites, and in the help
file mentioned in the IGS logon screen and I can't find anything that
explains exactly how byo-yomi works.  Could someone explain it to me?

Thanks!
-Carl

<censored>
From: rohm@bucrf17.bu.edu (Ryan Rohm)
Newsgroups: rec.games.go
Subject: Re: complexity of go
Date: 9 Sep 92 19:37:00 GMT
Reply-To: rohm@bucrf17.bu.edu (Ryan Rohm)
Followup-To: rec.games.go
Organization: Boston University


I'm not sure what the ultimate point of this discussion is, since it doesn't
seem to have much bearing on whether one prefers Chess to go or vice versa, 
or whether either is worthwhile, etc.  But for what it is worth, one should
make the best comparison possible.  

It has already been pointed out that one can adjust the complexity of go,
as measured by the total number of positions, by changing the size of the
board, and have a recognizably similar game. This is less true of Chess.  
One should then compare Chess to go when go is played on a board yielding
a similar number of total positions as Chess.  

I think the size of that board is 9x9; at least, the correct size is not
wildly different from that.  If you are not interested in how I get that 
figure, skip ahead to %%%%%%%% End of boring math.

%%%%%%%%%%%%%%%%Beginning of boring math
To order of magnitude I propose that the total number of go positions is 
not too different from 3**(n*n), where n is the side-length of the board. 
That is, each spot on the board can be White, Black, or empty, and the 
constraints of being able to reach such a position do not change the estimate
substantially (so exponent could be n^2 or n^2 - c*n, hardly matters).

(Because players can `pass out` the game at any point, any legal position
is a possible final position, however illogical).

As for Chess, let us place the pieces first, then the pawns.  I argue that
for order of magnitude, we ignore captures, since the entropy of a piece of 
the board is one, while on the board it is of order 60; all of the positions 
with captured pieces put together is then probably down by an order of 
magnitude.  For the pawns, unless pieces are captured (with concommitant loss 
of entropy), they are restricted to their original file;  I then guesstimate
a factor of 4 for each pawn, so the total becomes 64**16 times 4**16, or
2**128.  

Setting 3**(n^2) = 2**128, we find n = sqrt(128*ln2/ln3) = 9.

Oops!  We must put the Kings out of check and the Bishops on opposite colors;
that's a factor of 1/2 for each Bishop, and (estimating half of the squares
in check), another 1/2 for each King (overestimate, since it is only
multiple check that matters).  Then n = sqrt(124*ln2/ln3) = 9.
(I did that on purpose to show that the estimate is `robust').

%%%%%%%% End of boring math.

Although I am a piker at Chess and go both, I wager that go on a 9x9 board
is not as strategically rich, computationally complex, or otherwise really
cool as Chess;  this indicates that the number of positions is not such a 
good statistic.  When making a comparison between games with the same number
of positions, one can then try to see what else may be different (the 
topology of the game tree?).  And 9x9 go doesn't seem to be much harder than
chess for a computer, since it is largely tactical.

(Flames and disputes over arithmetic to /dev/null, please...)

rrohm (USCF 1200, 13kyu  :))
Newsgroups: rec.games.go
From: dwr2560@zeus.tamu.edu (RING, DAVID WAYNE)
Subject: Re: complexity of go
News-Software: VAX/VMS VNEWS 1.41    
Organization: Texas A&M University, Academic Computing Services
Date: Wed, 9 Sep 1992 02:21:00 GMT

mark@.cv.hp.com writes...
>While I am not disagreeing with the contention that go is more complex than
>chess, I do not believe that comparing the relative abilities of go programs
>verses chess programs makes much of a case for this claim.  The primary
>reason for this is that a LOT more effort has gone into producing computer
>chess programs than go programs.

No. I have played around 100 games of go, and I can trounce the best go program
in the world. How long ago could anyone have said the same about chess?

>               Chess is a game that caters to the strengths of a
>computer.

Right. Chess is primarily a game of calculation, with a little judgement. Go
is a game of judgement with a little calculation. Computers are excellent at
calculation and horrible at judgement.

Dave Ring
dwr2560@zeus.tamu.edu
From: jamieson@terapin.com (David Jamieson)
Newsgroups: rec.games.go
Subject: help with ftp
Date: 6 Sep 92 00:04:16 PST
Organization: BBS

TO: gatekeeper.dec.com
FROM: jamieson@terapin.com
SUBJECT: FTP HELP
help
HELP
Please send information concerning the use of ftp mail servers.  Am I
expressing that correctly? I would like information about ftping by
mail.  I understand I can use FTP through your facility.  I have specific
files to request at Univ of Washington.  I'm an IBM PC user.  What
software must I use to de-encode? 
 
Thanks. David Jamieson
Newsgroups: rec.games.go
From: jim@rand.org (Jim Gillogly)
Newsgroups: rec.games.go
Subject: Re: `GOG' Go Playing System now available from Free ICOT Software
Date: 11 Sep 92 05:10:07 GMT
Organization: Banzai Institute

If you're looking for software you can run, rather than ideas to incorporate
in your program, you should note that the GOG software assumes you have:

	PSI machine
	SIMPOS operating system
	ESP language

I don't... too bad.
-- 
	Jim Gillogly
	jim@rand.org
Xref: sparky rec.games.go:1830 rec.games.board:8550 rec.games.chess:6995
From: nickh@CS.CMU.EDU (Nick Haines)
Newsgroups: rec.games.go,rec.games.board,rec.games.chess
Subject: Re: Complexity - Ideas
Date: 7 Sep 92 20:46:55 GMT
	<1992Sep7.113727.15187@odin.diku.dk>
	<NICKH.92Sep7145835@VOILA.VENARI.CS.CMU.EDU>
Organization: School of Computer Science, Carnegie Mellon University
Originator: nickh@VOILA.VENARI.CS.CMU.EDU

In article <NICKH.92Sep7145835@VOILA.VENARI.CS.CMU.EDU>, I mistakenly wrote:

   A more efficient representation is to specify the piece on each
   square, giving 64^12 positions (12 different pieces: white and
   black rook, knight, bishop, queen, king, pawn) of which many are
   impossible (exactly one king of each colour, only 16 pieces of each
   colour). 64^12 ~= 10^21.

Of course the key number here is not 64^12 but 12^64 (~10^69).

It is better to specify the positions of the two kings and then give
the other squares in order (reducing the requirement to 64*63*(10^62)
(= 4e65). I reguesstimate the number of possible positions as 10^60.
(of which maybe 10^20 are possible without cooperation between the two
sides).  Sorry 'bout that.

   Nick
Xref: sparky rec.games.go:1838 rec.games.board:8608 rec.games.chess:7047
From: phs@imag.fr (Philippe Schnoebelen)
Newsgroups: rec.games.go,rec.games.board,rec.games.chess
Subject: PD Checkers program
Date: 8 Sep 92 20:15:02 GMT
Organization: Institut Imag, Grenoble, France

Anybody knows where I can find a public domain checkers program ? Something
Unix-based, similar to the chess(6) software.

I'm looking for the regular checkers game, on a 10x10 board with backward
captures allowed. Not the 8x8 version that is common in the States.

I'm a total beginner, so playing strength is not the issue.

I'll summarize if there is enough interest.

--Philippe
--
Philippe SCHNOEBELEN,  LIFIA,  46 Av Felix VIALLET,  38000 Grenoble,  FRANCE
						     email: phs@lifia.imag.fr
"Algebraic symbols are used when you do not know what you are talking about."
From: mark@sys6626.bison.mb.ca (Mark Essenburg)
Newsgroups: rec.games.go
Subject: complexity of go
Date: Sun, 06 Sep 92 02:43:25 CST
Organization: system 6626 BBS, Winnipeg MB

I love this conversation.

How complex is go.  Especially when compared to chess.  Neat question.  
The answer is quite obvious, I think.  Go is far more complex.  The 
gentleman who pointed out that computers (even home desktop units) can 
play a decent game of chess.  But what is the highest rating of a 
computer Go game?  12 kyu?  11?  Is there even a dan level computer game? 
 
The game of go has more freedom of movement and possible combinations 
that the Earth has atoms!  

Also, you can't give your chess opponant a handicap and have a decent 
game.   It just doesn't work.  A better chess player will always beat a 
poorer chess player.  But I can play a game with a 3 kyu player and at 9 
stones have a tie game!  In chess, impossible.  With go, we both have a 
good time.

If you want to know how complex Go is, go the the Nihon Ki-in and ask 
anybody.

My view.

mark

;--- (Mark Essenburg) a user of sys6626, running waffle 1.64
;E-mail: mark@sys6626.bison.mb.ca
;system 6626: 63 point west drive, winnipeg manitoba canada R3T 5G8
From: pirate@daimi.aau.dk (Thomas Jurgensen)
Newsgroups: rec.games.go
Subject: Re: IshiStd<-->SmartGo Filter?
Keywords: filter convert smartgo
Date: 15 Sep 92 16:24:36 GMT
Organization: DAIMI: Computer Science Department, Aarhus University, Denmark

jamieson@netcom.com (Davie Jamieson) writes:

>Is anyone aware of filters that will (at least partially) convert Ishi
>Standard Format to Smart Go Format and vice-versa?  Many Faces of Go has
>strong graphics, yet mgt is a better reader, so converting between the
>two formats is desirable, depending on one's use.

> 
Although I haven't written a filter between these two standard formats,
I have written a program which converts Ishi Standard format to
LaTeX-format, so that one can printout a file from Goscribe (or mgt)
by using LaTeX. I am wondering if anyone out there has written
such a converter, because I else am going give it a shot.

So if you know someone who has written such a filter(or is doing it),
please inform me too.

Bye,                             Thomas Juergensen 
                       email:    pirate@daimi.aau.dk
From: adrian@milton.u.washington.edu (Adrian Mariano)
Newsgroups: rec.games.go
Subject: Re: Tong Yang Securities Cup'91
Date: 9 Sep 92 23:06:13 GMT
Organization: University of Washington

In <88363@netnews.upenn.edu> jin@sol1.lrsm.upenn.edu (Xuegen Jin -Luzzi) writes:

>sent them to milton.u.washinton.edu ftp site (its filename is 
>tongyang91.sh.Z). So, please get those games from there, if you are 

The full filename is public/go/pro/tongyang91.sh.Z
From: jlzhong@vision.csl.uiuc.edu (Jialin Zhong)
Newsgroups: rec.games.go
Subject: A Temporary Fix of Hanging Telenet Processing of Client Programs of igs
Date: 15 Sep 92 21:37:38 GMT
Organization: Center for Reliable and High-Performance Computing, University of Illinois at Urbana-Champaign
NNTP-Posting-Host: vision.csl.uiuc.edu


We noticed that when you exit xigs unproperly, there may be a hanging telnet
process which causes trouble for igs server and eats a lot cpu time on your
local machine. To rectify this problem at present, we can add the following
lines to your .logout file if you use csh. So when you logout, the hanging
telnet process will be killed automatically. This is not a real fix but
you can use it as a safe procedure. You should still try to use the proper
way to exit xigs or other client programs. If you are using other shells,
I guess you can do similar things.

The following fix is by courtesy of shylock.

# remove go related processed

set goproclist = `/bin/ps -aux | grep "128.32.201.46" | awk '{print $2}'`
foreach i ($goproclist)
        /bin/kill -9 $i
end

Cheers,

Jialin "A Bad, Fake NR on igs" Zhong
--
Jialin Zhong			|     /  l      l	   l   l
1614 Beckman Institute		|    / l-l-l   -l-l l--l  -l- -l-
Urbana, IL 61801		|   /l l-l-l   /  l l--l  /l\ /l\
jlzhong@uirvld.csl.uiuc.edu	|  / l   l    /  \l	 / l X l \
From: hoffman@cmf.nrl.navy.mil (Eric Hoffman)
Newsgroups: rec.games.go
Subject: Game Complexity
Date: 9 Sep 92 23:24:43 GMT
Distribution: rec.games.go
Organization: Connection Machine Facility, NRL


I for one would like to make a note of protest concerning the use of 
board state information content as a measure of game complexity.

What makes a particular board position complex is not the information 
that it requires to store, but the potential stategic and tactical
ramifications.

The information content involved could be as high as the amount 
required to store all the games both players have ever played or
watched, as well as their general analysis, all the moves trees they
have ever played out in their minds, and all the strategies they have
ever conceived, and the results of them.  

As overblown as that last sentence was, I consider it an understatement.
Newsgroups: rec.games.go
Subject: Meijin game 1 result
From: ioffe@chen.bgu.ac.il (Alex Ioffe)
Date: Thu, 10 Sep 1992 22:13:54 GMT
Organization: Ben Gurion University, Beer Sheva, Israel




After 161 move white (Otake Hideo) resigned


Newsgroups: rec.games.go,rec.games.board,rec.games.chess
From: nates@ll.mit.edu ( Nate Smith)
Subject: Re: Complexity - Ideas
Organization: MIT Lincoln Laboratory
Date: Tue, 8 Sep 92 19:23:42 GMT

In article <NICKH.92Sep7145835@VOILA.VENARI.CS.CMU.EDU> nickh@CS.CMU.EDU (Nick Haines) writes:
>In article <1992Sep7.113727.15187@odin.diku.dk> torbenm@diku.dk (Torben AEgidius Mogensen) writes:
>
>   The first has roughly 65^32 ~ 10^ 58 possibilities (65 possible places
>   of 32) pieces. Not all of these are possible though (pawns can't go
>   backwards, bishops can only be at one colour etc). A rough estimate of
>   legal positions is 10^50.
>
>But all the (say) white pawns are equivalent, as are all the black
>rooks. And either player can have up to ten knights (say): a promoted
>pawn can become any piece. A more efficient representation is to
>specify the piece on each square, giving 12^64 positions (12 different
>pieces: white and black rook, knight, bishop, queen, king, pawn) of
>which many are impossible (exactly one king of each colour, only 16
>pieces of each colour).  ...[...]... 
     a square could be empty, so 13^64, but not all are possible...as
     you guys have pointed out....
>Nick

this reminds me of the old computer problem:  how many bits does it take
to completely store a chess position?  remember that whether or not each
side can castle and what pawns are capturable by en-passant need to be kept
along with the usual image.  gee, i used to know the answer...bits = 29?
so then you get 2^29.  naw, maybe it was something else.  for go you need
to keep the number of captured stones and the state of each ko....hmmmm.

- nate, 14kyu
From: jansteen@cwi.nl (Jan van der Steen)
Newsgroups: rec.games.go
Subject: Re: Meijin Sen live on IGS
Keywords: Meijin, IGS
Date: 8 Sep 92 13:23:11 GMT

hansm@cs.kun.nl (Hans Mulder) writes:

>In <7239@charon.cwi.nl> jansteen@cwi.nl (Jan van der Steen) writes:
>>		**************************************
>>		*                                    *
>>		*          Meijin Sen 1992           *
>>		*                                    *
>>		*   Live on the Internet Go Server   *
>>		*                                    *
>>		**************************************
>>
>>			Kobayashi Koichi, Meijin
>>			        vs
>>			  Otake Hideo, 9th dan
>>
>>		   9th September 08:00 - 16:00 (GMT)
>>		  10th September 08:00 - 16:00 (GMT)

>Errhm, Jan, aren't you off by 1 hour?

Ehhhh, I think you're right Hans :).

All those time zones are very confusing. I spend many hours on the Go
server mapping local time on remote time...

But, since these times are important, here they are again (corrected):


                 9th September 07:00 - 15:00 (GMT)
                10th September 07:00 - 15:00 (GMT)


Sorry for the inconvenience, and thanks,

Jan van der Steen

-- 
    -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
     Jan van der Steen                 jansteen@cwi.nl
     Centre for Mathematics and Computer Science (CWI)
     Kruislaan 413, 1098 SJ Amsterdam, The Netherlands
From: jhc@m2lll.uucp (James H. Coombs)
Subject: Re: complexity of go
Reply-To: jhc@iris.brown.edu.UUCP (James H. Coombs)
Organization: IRIS - Brown University
Date: Thu, 10 Sep 1992 03:53:37 GMT

In article <95620@bu.edu> rohm@bucrf17.bu.edu (Ryan Rohm) writes:

>I'm not sure what the ultimate point of this discussion is, since it doesn't
>seem to have much bearing on whether one prefers Chess to go or vice versa, 
>or whether either is worthwhile, etc.  But for what it is worth, one should
>make the best comparison possible.  

I am prepared to consider Go as more complicated than chess.  In fact,
after a first attempt against igo, I found that chess seemed very
simple.  Of course, that was my first game of go, and, even more
important, I lost both the go and the chess games.

So, from a personal point of view, what occurs to me everytime I think
of Go as more complicated, richer, whatever (and, crucially, superior),
I then notice that I cannot beat my chess computers.  So, not having
mastered this simpler game, why would I want to scratch the surface of
yet another game?

And then, I wonder, what is the point of the complexity comparison?  I
probably missed the point, which may well have been technical
originally but seemed to come down to a struggle over superiority.
Well, the point is to have fun, to distract oneself from the mundane,
etc.  Does complexity serve that purpose?  Perhaps.  Most people seem
to prefer simple games with lots of action.

Well, enough.  I haven't heard anything that convinces me that Go is
superior to chess.  And I haven't played enough Go to judge for
myself.  I do know that I am very reluctant to buy another 100 books
and spend 1000s of hours studying.

--Jim
From: mark@hpcvxmsr.cv.hp.com (Mark Rowe)
Newsgroups: rec.games.go
Subject: Re: complexity of go
Date: 9 Sep 92 00:11:54 GMT
Reply-To: mark@.cv.hp.com
Organization: UDT-CV (ITO)

In article <3aeoqB5w164w@sys6626.bison.mb.ca>, mark@sys6626.bison.mb.ca (Mark Essenburg) writes:
> How complex is go.  Especially when compared to chess.  Neat question.  
> The answer is quite obvious, I think.  Go is far more complex.  The 
> gentleman who pointed out that computers (even home desktop units) can 
> play a decent game of chess.  But what is the highest rating of a 
> computer Go game?  12 kyu?  11?  Is there even a dan level computer game? 

While I am not disagreeing with the contention that go is more complex than
chess, I do not believe that comparing the relative abilities of go programs
verses chess programs makes much of a case for this claim.  The primary
reason for this is that a LOT more effort has gone into producing computer
chess programs than go programs.

However, the above is a pretty uninteresting claim.  So in the interest of
generating some interesting discussion let me make a somewhat more
provocative claim.  Chess is a game that caters to the strengths of a
computer.  In particular, the value of a position is heavily dependent on
the number of what pieces are on the board and what pieces are immediately
or immenently threatened with capture.  This is very easily evaluated by a
computer, as are the successive positions resutling from a pruned tree
search.  The value of a position in Go on the other hand is much more
dependent on overall patterns.  A computer is much better at tree searches,
counting, and arithmetic than a human is; however, a human is much better
at pattern recognition than a computer.  I don't believe that this in
itself means that pattern recognition is a complex task.

Furthermore, much of the complexity of both Go and Chess results from the
scale of the game which is somewhat arbitrary.  If the game is too complex
play it on a smaller board; if it is too simple play it on a larger board.
Go, by virtue of the uniformity of its pieces, is much easier to scale than
chess, but one can imagine chess being played with twice as many pieces on
a 16x16 board (or any increment such as a 12x12 board with 4 rooks and 4
bishops per side).

I haven't seen any discussion of how the complexity of Go is affected by the
size of board.  Is a 19x19 game twice as complex as a 9x9 game?  Four times?
Sixteen times?  Does whatever scale you use also apply for 13x13 or 25x25
games?  Just how complex would a 99x99 game be?  (probably not much more
complex than a 25x25).

Mark Rowe             email: mark@hpcvlx.cv.hp.com
Hewlett Packard       voice: (503) 750-3246
Corvallis, OR         FAX:   (503) 750-3788
Newsgroups: rec.games.go,rec.games.board,rec.games.chess
From: nickh@CS.CMU.EDU (Nick Haines)
Subject: Re: Complexity - Ideas
Originator: nickh@VOILA.VENARI.CS.CMU.EDU
Organization: School of Computer Science, Carnegie Mellon University
	<1992Sep7.113727.15187@odin.diku.dk>
Date: Mon, 7 Sep 1992 19:58:35 GMT

In article <1992Sep7.113727.15187@odin.diku.dk> torbenm@diku.dk (Torben AEgidius Mogensen) writes:

[...]

   In Chess the position can either be descibed as the position of each
   piece as a square number or "off board" or by listing the moves
   required from the initial position to reach the present prosition.

   The first has roughly 65^32 ~ 10^ 58 possibilities (65 possible places
   of 32) pieces. Not all of these are possible though (pawns can't go
   backwards, bishops can only be at one colour etc). A rough estimate of
   legal positions is 10^50.

But all the (say) white pawns are equivalent, as are all the black
rooks. And either player can have up to ten knights (say): a promoted
pawn can become any piece. A more efficient representation is to
specify the piece on each square, giving 64^12 positions (12 different
pieces: white and black rook, knight, bishop, queen, king, pawn) of
which many are impossible (exactly one king of each colour, only 16
pieces of each colour). 64^12 ~= 10^21. I guesstimate the number of
possible positions as 10^18.

Nick
Newsgroups: rec.games.go
From: gjm11@cus.cam.ac.uk (G.J. McCaughan)
Subject: Re: NEW RPG GAME. FULLY TESTED. $25
Organization: U of Cambridge, England
Date: Sun, 13 Sep 1992 02:54:44 GMT

In article <18tunrINNl4n@usenet.INS.CWRU.Edu>, ar354@cleveland.Freenet.Edu (Jason Perusek) writes:

> [long advertisement for a role-playing game he wants us to buy from him]

What on earth is this doing in rec.games.go?

-- 
Gareth McCaughan     Dept. of Pure Mathematics & Mathematical Statistics,
gjm11@cus.cam.ac.uk  Cambridge University, England.    [Research student]
Newsgroups: rec.games.go
From: matsa@tdb.uu.se (Mats Andersson)
Subject: PCIGC via Telnet
Organization: Dept. of Scientific Computing, Uppsala Univ.
Date: Mon, 14 Sep 1992 12:05:34 GMT

  The PCIGC might be gorgeous once You can run it. I can't, though, due too
the simple reason that my telnetting is no done over a serial port, i.e.
COM#. Is there anyone considering that problem?


Newsgroups: rec.games.go