rec.games.strategic
Darse Billings
of strategy -- which is quite distinct from the more general class of
games in rec.games.board.
Personally, I am interested in computer game playing of strategic games,
and the forum provided by rec.games.strategic should prove both
interesting and useful.
There is a very definite need for such a newsgroup, and it is long
overdue. Here is a starting list of the games which might be discussed:
Awari, Chase, 8x8 Checkers, 10x10 Draughts, Chinese Chess, Connect
Four, Dominoes, Hex, Go-Moku, Renju, Reversi (Othello), Nine Men's
Morris, Nim, Qubic (4x4x4 Tic-Tac-Toe), Scrabble, Shogi
This does not preclude discussion of those games already having
specific newsgroups:
Backgammon, Bridge, Chess, Go
rec.games.board is too diluted by other games to be usable by those of
us interested in purely strategic games. Note that such games may not
be played on a board at all. For example, Awari and other games
contested in the Computer Games Olympiad are not really defined in terms
of the board they use. Nim is another example.
Nor are all interesting strategic games necessarily deterministic.
Backgammon, dominoes, and many card games, such as bridge, hearts, and
poker, have elements of randomness and hidden information, but the
strategic elements of such games may deserve a special place for discussion.
The confusion surrounding the distinction between groups is easily
handled by posting a charter of the intentions of the newsgroup at
regular intervals (say monthly).
If you support the formation of this new newsgroup, send your ideas and
contributions to Neil Bowers (ne...@scs.leeds.ac.uk). If you see a call
for votes, please take the time to cast your YES vote. Thank-you.
--
- Darse Billings, 2100 CM, 7 kyu.
Go is better than Chess. Poker is more lucrative. Sex is more fun.
gar...@cs.monash.edu.au
>I would very much like to see a newsgroup devoted exclusively to games
>of strategy -- which is quite distinct from the more general class of
>games in rec.games.board.
Excellent idea. Let's get the CFV happening RSN!
>There is a very definite need for such a newsgroup, and it is long
>overdue. Here is a starting list of the games which might be discussed:
>Awari, Chase, 8x8 Checkers, 10x10 Draughts, Chinese Chess, Connect
>Four, Dominoes, Hex, Go-Moku, Renju, Reversi (Othello), Nine Men's
>Morris, Nim, Qubic (4x4x4 Tic-Tac-Toe), Scrabble, Shogi
There is a class of games you do not consider that would fit perfectly
into such a group: bargaining games! Primitive Politics, Coalitions,
Coalections, Log Rolling, Agendas. These are games where the strategic
questions are perhaps the most difficult of all, and where success
depends upon one's skill as a political negotiator, not to mention
the regard in which you are held by other players (not entirely out of
your control of course).
And then, of course, there is the ultimate meta-game - Nomic, in which
each move consists of a proposal to change the rules, which is then voted
on. (The winner that player who succeeds in either satisfying the winning
condition (whatever that might be at the time) or by creating a paradox so that
the game is unable to continue). Strategy in Nomic is almost too complicated
to think about!
>If you support the formation of this new newsgroup, send your ideas and
>contributions to Neil Bowers (ne...@scs.leeds.ac.uk). If you see a call
>for votes, please take the time to cast your YES vote. Thank-you.
>--
I'll second that!
*******************************************************************************
* __ ___ ___ \ / ___ | * "We have no choice. We must believe in free *
*|__ | |__ \ / |__ | * will." *
*___| | |___ \/ |___ o * Isaac Bashevis Singer *
*gar...@bruce.cs.monash.edu.au* *
*******************************************************************************
Noam Elkies
>Awari, Chase, 8x8 Checkers, 10x10 Draughts, Chinese Chess, Connect
>Four, Dominoes, Hex, Go-Moku, Renju, Reversi (Othello), Nine Men's
>Morris, Nim, Qubic (4x4x4 Tic-Tac-Toe), Scrabble, Shogi
I've heard of most of these except Awari and Chase (and may need
a refresher course on Renju). Are these games simply enough defined
that you can post the specs to rec.games.chess?
Note that Dominoes falls under the nondeterministic category as well,
though that's no reason to exclude it from your list.
Nine Men's Morris!? Surely *that* is completely solved by now?
There are only about 18 billion possible positions modulo the
8 board symmetries.
--Noam D. Elkies (elk...@zariski.harvard.edu)
Dept. of Mathematics, Harvard University
Gym Z. Quirk
news.announce.newusers or news.answers be consulted before taking this
much further?
Furthermore, when I think of 'strategic' games, I tend to think of
'strategic level military simulations'. But that's just my twisted
mind.
--
Capt. Gym Z. Quirk (Known to some as Taki Kogoma) qu...@pioneer.unm.edu
I'll get a life when someone demonstrates that it would be superior to
what I have now...
Darse Billings
>In article <darse.714354066@silver-vly> da...@cs.UAlberta.CA (Darse Billings) writes:
>>Awari, Chase, 8x8 Checkers, 10x10 Draughts, Chinese Chess, Connect
>>Four, Dominoes, Hex, Go-Moku, Renju, Reversi (Othello), Nine Men's
>>Morris, Nim, Qubic (4x4x4 Tic-Tac-Toe), Scrabble, Shogi
>I've heard of most of these except Awari and Chase (and may need
>a refresher course on Renju). Are these games simply enough defined
>that you can post the specs to rec.games.chess?
Awari is one of a family of games, called Mancala, which has more than
1000 variants. Awari is common in Africa, and is nicely described in
articles [1] and [2].
Very briefly: There are two rows of six pits, each pit having four stones:
f e d c b a player 1
-----------------
| |4|4|4|4|4|4| |
| |-----------| |
| |4|4|4|4|4|4| |
-----------------
A B C D E F player 2
A move consists of taking all the stones from a pit, and sowing them one
at a time clockwise into the other pits. Stones are captured whenever
the last stone sown fills that pit to a total of two or three stones.
The goal is to capture more stones than your opponent (ie. 25 stones).
If your opponent has no move (ie. all of the pits on her side are empty),
then you capture all of the remaining stones.
There are a few other special case rules, so I recommend reading one or
both of the following articles.
[1] "Awari Tournament Report", in _Heuristic Programming in Artificial
Intelligence -- The First Computer Olympiad_, D.N.L. Levy and D.F. Beal
(editors), Ellis Horwood Limited, 1989, pp 17-20.
[2] L.V. Allis, M. van der Meulen, and H.J. van den Herik, "Databases in
Awari", in _Heuristic Programming in Artificial Intelligence 2 -- The Second
Computer Olympiad", Ellis Horwood Limited , 1990, pp 73-86.
-----
Chase (TM) is a chess-like game played on a hexagonal board, using two
colours of six-sided dice for men. The range of mobility of the men is
defined by the value on each die, and certain moves allow you to change
those values during the game. Thus the nature of the playing pieces may
vary, and this must be taken into account when computing moves and
strategies.
>Note that Dominoes falls under the nondeterministic category as well,
>though that's no reason to exclude it from your list.
Yes. The list is comprised of games with relatively simple rules and
materials, but that are strategically very rich. This is perhaps the
most important distinguishing feature from the complex board games such
as Advanced Squad Leader and the plethora of other fine Avalon Hill
games discussed in rec.games.board.
>Nine Men's Morris!? Surely *that* is completely solved by now?
>There are only about 18 billion possible positions modulo the
>8 board symmetries.
Well, not to my knowledge. Umm, I count 3^24 = 282429536481 or about
10^12 board positions without symmetries -- am I missing something?
I'm not sure if anyone has fully investigated and capitalized on board
symmetries, as was done for Qubic. But there has been some interesting
work on database construction toward the goal of solving the game. See
[3] for more information.
Connect Four and Qubic have been solved, but this certainly does not mean
that they are not worth discussing (in fact the stories of how they were
solved are very interesting). For more on this, see my earlier posting
in response to a question about checkers (subject: "Checkers match").
[3] R. Gasser, "Applying Retrograde Analysis to Nine Men's Morris",
in _Heuristic Programming in Artificial Intelligence 2 -- The Second
Computer Olympiad", Ellis Horwood Limited , 1990, pp 161-173.
Follow-ups to rec.games.chess and rec.games.board only, please. (And
to rec.games.strategic, when it is created :^)
Greg Lindahl
>There is a class of games you do not consider that would fit perfectly
>into such a group: bargaining games!
Isn't Diplomacy a bargaining strategy game? Isn't Diplomacy routinely
discussed on rec.games.board? Sounds like you'd be totally welcome to
use rec.games.board for these discussions, as was suggested the last
20 times this topic came up. It's not like rec.games.board has a high
volume to discourage you.
Followups to news.groups, which is the "right place" for discussions
about new groups.
N Bowers
>Might I suggest that the 'How to create a newsgroup' posting in
>news.announce.newusers or news.answers be consulted before taking this
>much further?
I have already done this. An RFD will be posted in the near future,
at which point discussion will be directed to news.groups, which
as someone else has already pointed out, is the correct place to
continue this discussion.
If anyone has suggestions or ideas relating to this, please mail
them to me: ne...@scs.leeds.ac.uk
Neil
Markus Stumptner
> Furthermore, when I think of 'strategic' games, I tend to think of
> 'strategic level military simulations'.
This argument was ruled invalid already earlier in the discussion
(i.e., before it included rec.games.board), because you can't prove
that 99% of Usenet readers think like you do.
--
Markus Stumptner m...@vexpert.dbai.tuwien.ac.at
University of Technology Vienna vexpert!m...@relay.eu.net
Paniglg. 16, A-1040 Vienna, Austria ...mcsun!vexpert!mst
Noam Elkies
da...@cs.UAlberta.CA (Darse Billings) writes:
>elk...@ramanujan.harvard.edu (Noam Elkies) writes:
>
>>Nine Men's Morris!? Surely *that* is completely solved by now?
>>There are only about 18 billion possible positions modulo the
>>8 board symmetries.
>
>Well, not to my knowledge. Umm, I count 3^24 = 282429536481 or about
>10^12 board positions without symmetries -- am I missing something?
For one thing, that's only about quarter of 10^12. For another thing,
that counts all ways of making each of the 24 points White, Black, or
empty; but not all of them are legal positions, since there is the
constraint that the total numbers of White and Black men not
exceed 9. [At least in the version of the game I know: begin by
alternately placing 9 men of both colors on the board; then alternately
move along the lines, removing an opponent's piece of your choice
whenever a monochromatic 3-point line is achieved --- so one never
has more than 9 men of the same color on the board.] Given the numbers
w,b of White and Black men, the number of possible positions is
(24-choose-w)([24-w]-choose-b)=24!/(w!b!(24-w-b)!); summing this over
100 possible values of (w,b) from (0,0) to (9,9) gives 143122694691.
I then divided this number by 8, but in Nine Men's Morris there is
the additional symmetry of exchanging the inner and outer ring, so
I should have divided by 16 to get about 9 billion positions. [The
number of positions symmetrical under any one of these symmetries is
negligible so just dividing by 16 gives a very good approximation.]
This is about the same as the number of positions in a 6-piece chess
endgame without repeated pieces; such endgames are tractable, albeit
barely, by current technology (L.Stiller).
Michael Urban
proprietary games (Monopoly, Diplomacy, etc.) and non-proprietary
games (Xiang-Qi, Shogi, Mancala, etc.).
A separate group for the latter might be appropriate (although I
personally favor starting up a mailing list as a trial balloon
before creating yet another newsgroup). The question becomes,
how do you name the group? `strategic' is too general, but
`non-proprietary', `PD', or `traditional' do not communicate much.
Mike
Mike Urban
Paul James
Before we consider making a new group rec.games.strategic, can someone
tell me which games discussed in rec.games.board are NOT strategic. It
seems to be that 95% at least are. Creating a new group would just
confuse the issue. The group at present is not too large and forcing
people to read two groups instead of one when one does not take too
much bandwidth is silly.
================================================================================
Paul James ____________________
pr...@ecs.soton.ac.uk / __________________O
kra...@mail.soton.ac.uk / /|________________
/ /_/________________O
"Beware the many tentacled one." /_____________________
|______________________O
OS-9 User Group
>
>Before we consider making a new group rec.games.strategic, can someone
>tell me which games discussed in rec.games.board are NOT strategic. It
>seems to be that 95% at least are. Creating a new group would just
>confuse the issue. The group at present is not too large and forcing
>people to read two groups instead of one when one does not take too
>much bandwidth is silly.
Perhaps the group is not too large if you like war games. But for
those of us who have no interest in them...
It doesn't seem silly to me. It would be a great relief. My killfile
is becoming rapidly unmanageable. You are ignoring the context of
strategic. Perhaps a better name would be something like:
rec.games.board.abstract.strategic.like.shogi.go-moku.pente.checkers.etc
But it really is unpleasant to have to type that every time you want to
move to the newsgroup. So, given the context of "strategic", and that
there would be a mandate posted to the group defining it's subject,
95% of the games in rec.games.board would be inappropriate in
rec.games.strategic.
What you are quibbling about here is whether the precise name
"rec.games.strategic" is appropriate. Don't attempt to blur this
minor but valid point with the larger issue of whether or not the
newsgroup itself is needed (whatever the name finally is).
You can't be so naive as to imagine that the majority of games discussed
in rec.games.board would be at all interesting to most people who play
games like checkers or shogi. To be sure there are people who are
interested in both, just as there are people who subscribe to both
comp.theory and comp.ai -- but it is largely two completely separate
groups with little in common. Anyway this is a point that need not
be debated, since it is clear from the large number of posts: shogi,
checkers, othello, go-moku, pente, draughts, etc., players are not
interested in reading rec.games.board.
.
Ross Ridge
>I would very much like to see a newsgroup devoted exclusively to games
>of strategy -- which is quite distinct from the more general class of
>games in rec.games.board.
>
>Personally, I am interested in computer game playing of strategic games,
>and the forum provided by rec.games.strategic should prove both
>interesting and useful.
>
>There is a very definite need for such a newsgroup, and it is long
>overdue. Here is a starting list of the games which might be discussed:
>
>Awari, Chase, 8x8 Checkers, 10x10 Draughts, Chinese Chess, Connect
>Four, Dominoes, Hex, Go-Moku, Renju, Reversi (Othello), Nine Men's
>Morris, Nim, Qubic (4x4x4 Tic-Tac-Toe), Scrabble, Shogi
And here's a list of games that actually will be discussed:
Diplomacy, Risk, World in Flames, Third Reich, Civilization,
BattleTech, Empire in Arms, Squad Leader, 1830, Titan, ...
Ross Ridge
--
Ross Ridge - The Great HTMU l/ //
[OO][oo]
ro...@zooid.guild.org /()\/()/
uunet.ca!zooid!ross db //
Gym Z. Quirk
>From article <v__n=0...@lynx.unm.edu>, by qu...@pioneer.unm.edu (Gym Z. Quirk):
>> Furthermore, when I think of 'strategic' games, I tend to think of
>> 'strategic level military simulations'.
>
>This argument was ruled invalid already earlier in the discussion
>(i.e., before it included rec.games.board), because you can't prove
>that 99% of Usenet readers think like you do.
Well, if you had included the next sentence of my post, you wouldn't
have had to make the above statement.
For the records I'll re-include it here.
> (But that's just my twisted little mind.)
Also, how should I be expected to know what occured before this
discussion reached rec.games.board when I first encountered it on
rec.games.board?
>Markus Stumptner m...@vexpert.dbai.tuwien.ac.at
>University of Technology Vienna vexpert!m...@relay.eu.net
>Paniglg. 16, A-1040 Vienna, Austria ...mcsun!vexpert!mst
Ravindra Shantaram Kane
Eric Schiller
every two years featuring many of these games. The first will be
in London next summer (I'll be handling the press so there will
be plenty of info)and in 1995 negotiations are underway for a site
in the midwest.
I'll post more info as it becomes available, but if you want to
be on a direct e-mail list, send me a note.
Eric Schiller
Nici Schraudolph
>Awari is one of a family of games, called Mancala, which has more than
>1000 variants. Awari is common in Africa, and is nicely described in
>articles [1] and [2].
Also known as: Kalah, Kalaha, Owari, Owerri, "African Bean Game", etc.
--
Nicol N. Schraudolph, CSE Dept. |
Univ. of California, San Diego |
La Jolla, CA 92093-0114, U.S.A. |
nici%cs@ucsd.{edu,bitnet,uucp} | (this mind intentionally left blank)
David H. Thornley
>[I'd like a newsgroup for games of strategy.]
>
>There is a very definite need for such a newsgroup, and it is long
>overdue. Here is a starting list of the games which might be discussed:
>
>Awari, Chase, 8x8 Checkers, 10x10 Draughts, Chinese Chess, Connect
>Four, Dominoes, Hex, Go-Moku, Renju, Reversi (Othello), Nine Men's
>Morris, Nim, Qubic (4x4x4 Tic-Tac-Toe), Scrabble, Shogi
>
but I think rec.games.strategic will attract such games as Advanced Third
Reich and World in Flames like candles attract moths. Remember, it's not
what *you* think of as a game of strategy, it's what the weregamers think
of as strategy. Even if 99% of the people on the net think Go Moku is a
typical game of strategy, at least 95% of the wargamers will think it's
effectively rec.games.war. Unless you want to be continually posting and
emailing "Take it to rec.games.board", with partial success, *don't* use
this name. It's asking for trouble.
I would propose rec.games.abstract as an alternative title, since none of
the games you mentioned are representations of anything in the real world.
This will keep us wargamers off the group, and let you discuss Shogi and
various versions of Checkers as much as you want.
Followups, of course, to news.groups.
DHT
Antti Karttunen
>
>Awari, Chase, 8x8 Checkers, 10x10 Draughts, Chinese Chess, Connect
>Four, Dominoes, Hex, Go-Moku, Renju, Reversi (Othello), Nine Men's
>Morris, Nim, Qubic (4x4x4 Tic-Tac-Toe), Scrabble, Shogi
What about Alquerque, Ashtapada, Halatafl, Freystafl, Hnefatafl,
Tablut, Seega, Ludus Latrunculorum, Tablan, Hasami Shogi, Pallanguli,
Chisolo?
(Sorry, couldn't resist. These are from "Board and table games from
many civilizations", by R.C. Bell, M.B., F.R.C.S, published by
Oxford University Press, 1960).
Now that I have found this thread I can continue to crosspost my drivel to
these various newsgroups...
Questions I have wondered:
1) What is the most complex (human invented) game 'computationally'?
Go???
2) What will happen when computers finally beat all human beings in
Chess? Will there be less interest in Chess after that, or more?
Or will there be a migration to Shogi or Go?
>
> - Darse Billings, 2100 CM, 7 kyu.
>
>Go is better than Chess. Poker is more lucrative. Sex is more fun.
Not kyuu, dan nor grandmaster, just an eternal beginner inherently interested
about all kind of strategic games...
--
Antti Karttunen -- アンッティ カルットゥネン (et{ty|t|n)
kar...@mits.mdata.fi -- Apatheist, although not particularly proud of it.
RING, DAVID WAYNE
>1) What is the most complex (human invented) game 'computationally'?
>Go???
I will assume things which require dexterity and hand eye coordination are
called 'sports'.
Go will be the last major game to have a computer world champion. The best
programs in the world are still rated as beginners. It is concievable that
a 'deep thought' could beat the best players within our lifetime, but it
would require a totally different algorithm than Deep Thought's 'brute force'
approach (since there are ~300 possible moves, and the best players look
~70 moves deep, that's 300^70 = 10^175 positions to consider. At 10^12
positions per second, that would take 10^140 ages of the universe to
compute 1 move! )
Dave Ring 5kyu
dwr...@zeus.tamu.edu
Markus Stumptner
> Perhaps the group is not too large if you like war games. But for
> those of us who have no interest in them...
No, the group is not large in absolute terms.
> You can't be so naive as to imagine that the majority of games discussed
> in rec.games.board would be at all interesting to most people who play
> games like checkers or shogi.
That's not the question, the question is whether the traffic on
rec.games.board is so large as to make it impossible for them to
discuss these games, which I do not believe. Rather, the situation is
that traffic on these games is currently low, which speaks against a
new newsgroup. Face it, most newsgroups cover some larger area. I
see people here discussing railroad and family games without flames or
problems. The fact that the majority of posts in the newsgroups I
read is of no interest of me is not surprising, this holds in comp.ai,
comp.databases.theory, rec.arts.movies, rec.arts.sf.written,
alt.folklore.computers. But that fact does not warrant creation of
new subgroups.
> shogi,
> checkers, othello, go-moku, pente, draughts, etc., players are not
> interested in reading rec.games.board.
Exactly, because there are almost no posts on rec.games.board
concerning these games, but it's up to them to change that.
As for the name of the proposed new group (if it comes to pass), this
is NOT a minor point; a group that is supposed to separate specific
topics also needs a specific title. A badly chosen name leads to
confusion, hurting not only the readers of the original group (who
lose postings) but also those of the new one, who again have to deal
with (to them) uninteresting topics. Choosing a confusing name is
self-defeating.
--
Tom O Breton
> 1) What is the most complex (human invented) game 'computationally'?
> Go???
A book I've read (_Board games of The World_? I think) rates only Kriegspiel
in its' "most complex" category.
Kriegspiel is "invisible chess" played on 3 parallel boards and is indeed
difficult.
In their next-most-difficult category are both Chess and Go. I believe Chess
is considered slightly more complex, no doubt because of its' significantly
more complex rules.
Of course, this is only well-accepted games. In theory, there is no upper
limit to the complexity a game can have.
Imagine something along the lines of 3000 simultaneous games of Chess on a
41267 x 37636 board (Last surviving king wins) Bishops sailing across several
hundred spaces to capture accidentally exposed queens... Discovered check
from pieces that haven't been moved for years, half a mile away...
> 2) What will happen when computers finally beat all human beings in
> Chess? Will there be less interest in Chess after that, or more?
> Or will there be a migration to Shogi or Go?
"When"? }:) As it stands, all the human beings unbeatable by computers
could fit into a small room. (And their names usually seem to be of the form
Ka*ov ) There are already programs that beat 99.999999% of us, and *common*
programs that beat anyone who doesn't play chess religiously.
If computers beat every human being, Chess will become a hobby -- a
difficult-to-detect change, to be sure! };)
It has already happened quite a few years ago with checkers, and there was no
perceiveable change in the game.
Tom
--
Having decimated the hapless peasants, the Tom spreads its huge, scaly wings
and soars into the wild sky... up... up... out of sight...
Arthur C. Adams
rec.games.board.classic
rec.games.board.strategic
rec.games.board.family
Classic would cover games like chess, go, checkers, shogi and other games
that are, well, classic.
Strategic would cover war games, plus railroad games, stock games, Talisman
style stuff, etc.
Family would stick to Monopoly, Scrabble and other similar games.
--
The world is not analog. The world is digital,
with an incredible number of bits.
Arthur C. Adams (not the comic-book artist) <fnord>
E-Mail aca...@afterlife.ncsc.mil
OS-9 User Group
>As for the name of the proposed new group (if it comes to pass), this
>is NOT a minor point; a group that is supposed to separate specific
>topics also needs a specific title. A badly chosen name leads to
>confusion, hurting not only the readers of the original group (who
>lose postings) but also those of the new one, who again have to deal
>with (to them) uninteresting topics. Choosing a confusing name is
>self-defeating.
I guess this is the real problem with rec.games.board
rec.games.board is NOT. Instead of being a newsgroup devoted just
generally to board games, it is a newsgroup which is practically
dedicated to a specific type of war/railroad/stock game that is NOT
what most people think of when they think of "board game" (it may
be what the players of these game think of when they think "board
game", but it is not what i, or most people, think of -- i think
about games like monopoly, scrabble, shogi, checkers, etc.).
The real problem is that "rec.games.board" is actually
"rec.games.war" in disguise.
My favourite suggestion to date is still to just create a rec.games.war
and leave rec.games.board for everyone else (scrabble, shogi, etc.)
There currently isn't a general newsgroup for board games which don't
have their own specific group -- rec.games.board is SUPPOSED to fill
this spot, but it doesn't.
When someone looking for posts on Pente hits the newsgroup lists, they
probably go straight into rec.games.board -- and after reading about 25
messages decide they're in the wrong place. Usually posts on pente end
up going into rec.games.go --
Hence one can only conclude that rec.games.board is inappropriately
named. It should be called "rec.games.war" or "rec.games.board.war"
Justin Wells
sizone!jus...@ee.ryerson.ca .
David Doshay
of possible games.
Thus for Go the number is close to 361! (361 x 360 x 359 x .... x 3 x 2). You
could say it is smaller by 4! or maybe 8! because of symmetery in the board,
but dividing 361! by 8! hardly changes the result. Of course it could be a
bit larger because of ko and replay into large previously captured areas, but
that would not change the overall number by much. So, 361! is about 10^924.
Use Simpson's rule to approximate the factorial if this round number is not
good enough for you.
Counting down, there are about:
10^60 elementary particles in the universe ( about 48!, just less
than Go on a 7x7 board )
10^45 games of chess ( about 38! )
10^22 games of checkers ( about 23! )
wish I knew for bridge. Anybody know?
So, Go is tougher than the others. Of course you can multiply the complexity of
any game by playing with the rules, but the size of the gap between Go and the
others means that MUCH modification of the traditional rules would be required to
even approach Go. Of course in Go all we have to do is play a slightly larger
board, say 21x21, to increase the complexity to 441!, or something like
10^1167. Hey, that is only a whole unverse worth of elementary particles TIMES
the number of Go games on a regular board. How nice that it is so easy to
greatly increase the computational complexity of the game, just in line with
the very simple rules.
Note that these numbers are not the same as the mistakenly calculated 300^70
posted earlier. That number should perhaps be 300! / 70!, something like 10^640.
David dos...@soma.arc.nasa.gov
The thought police insist I tell you:
my thoughts, not NASA's
Secret Mud
>dwr...@zeus.tamu.edu (RING, DAVID WAYNE) writes:
>
>>kar...@mits.mdata.fi (Antti Karttunen) writes...
>>>1) What is the most complex (human invented) game 'computationally'?
>>>Go???
>>
Does this have to be cross-posted to so many groups?
Neil Bowers
> I think you need to define the term 'strategic' a little better.
>You say that rec.games.board is too diluted for those of us interested
>in 'purely strategic' games, yet nowhere in your list of examples did I
>see mention made of strategic-level wargames and economic/socio-political
>games.
The word strategic obviously meant different things to different categories
of game players, so it was dropped from the proposal.
I have posted an RFD for rec.games.abstract to news.announce.newgroups.
It should be appearing here RSN.
Further discussion directed to news.groups
-neilb
Nathan Hess
dos...@ursa.arc.nasa.gov (David Doshay) wrote:
>The computational complexity of a game is normally taken to be the number
>of possible games.
This has almost no relation whatsoever to normal measures of computational
complexity, which talk about FAMILIES of games (e.g. Go on NxN boards).
NxN Go and Hex were easily proved to be at least PSPACE-hard; NxN Chess has
also been proved PSPACE-hard (with some difficulty, and making up of rules).
Last year there were rumors that NxN Go had been shown to be EXPTIME-complete
through a devious construction involving massive numbers of kos, but I haven't
seen the proof so I can't comment further. It's certainly clear that, due to
kos extending the length of the game, it is not trivial to prove that Go is
even *in* PSPACE (it would not be if the maximum length of a game was not
bounded by a polynomial in the board size). Hex is clearly in PSPACE, and
thus is PSPACE-complete. The same is true for Chess if the extended draw rule
is that after a number of moves equal to the boardsize the game is drawn.
The difficulty with even THESE criteria, rigorous as they are, is shown by the
case of Bridg-It. NxN Bridg-It is PSPACE-complete, if you consider it to be
the problem of solving arbitrary full-board problems. However, NxN Bridg-It
is also solveable in linear time and space (or perhaps O(Nlog(N)) time if memory
accesses take logarithmic time in the address size), if considered as the
problem of playing a full game starting from an empty board, due to a trivial
pairing strategy. So the fact that arbitrary board situations can be extremely
difficult to solve means NOTHING about the complexity of playing a game from
an empty board. Go could be extremely easy. If you don't believe me, just
consider Go with Black getting 5 points of komi and being allowed to play
mirror Go.
>for Go the number is close to 361! ... You could say it is smaller by 4! or
>maybe 8! because of symmetery in the board
The board symmetry reduces it by something like 8, not nearly 4! or 8!. The
first move is less than 8 because not all points have 8-fold symmetry - some
have only 4-fold (and one has only 1-fold). On the other hand, a few moves
still have some symmetry after the first move (e.g. 3-3, 3-10, 10-10), which
pushes it up a little (less than a factor of 2); but these are precisely the
moves which had less than 8-fold symmetry in the first place. Since all games
eventually become asymmetric, this means that all these factors must work out
to give an exactly 8-fold reduction when taken together.
Move sequence reconvergence of k moves could lead to a division by k!, if you
count positions with the same stones but different histories as the same (it
might NOT make sense to do so under the generalized ko rule, for example). In
that case, after 20 moves you would have something over 361! / (341!*20!) or
"361 choose 20" positions (the excess is due to capturing sequences where order
matters). The peak of this is around k=180, for which "361 choose 180" / 8
gives a lower bound to the number of possible positions even factoring out
board symmetry. However, this is less than 361! by a factor of 181!*180!*8,
which is not what I would call "close".
I find such trivial approaches as counting games or positions to be rather
pointless. There are real, VITAL questions here which are much deeper and
more important. My own hot button at the moment:
(1) Laura Yedwab showed in her MIT master's thesis that a certain
endgame subset of Go was PSPACE-complete, or more accurately,
that such a subset PLUS one simple game that she was not able
to embed in a Go situation were PSPACE-complete.
(2) PSPACE-complete problems are generally considered to be a quantum
level of difficulty harder than NP-complete problems, which are
already too hard to solve easily. So we should expect that Yedwab's
game would be extremely difficult.
(3) However, she also showed that there is an approximation strategy
that gets within a fixed amount of the optimum, and is trivial to
compute, for arbitrarily large games. In fact, the more complex
the game, the better (proportionally) the strategy does.
Now, the above is not a paradox - we know that for some hard problems, it is
only hard to get the exact answer, but getting within (say) 5% may be easy.
However, most results of this nature are for NP-complete problems. It is a
little surprising to find a PSPACE-hard analog, and leads to speculation that
game-theoretic approaches to PSPACE-hard problems might (as a side benefit)
yield excellent approximate algorithms for some of the classic NP-complete
problems as well. I would welcome more research in this area, but don't have
much time for it myself right now. PhD candidates in CS theory take note ...
Howard A. Landman
lan...@xpoint.com
Huw Roberts
:
: If computers beat every human being, Chess will become a hobby -- a
: difficult-to-detect change, to be sure! };)
:
: It has already happened quite a few years ago with checkers, and there was no
: perceiveable change in the game.
champion might dispute this with you. There is, in fact, a tournament in
progress at this very moment between him and a program called Chinook.
Before this contest I think the record was 1 win to Tinsley and 17 draws.
In this tournament I have heard that it is one all with umpteen draws.
Checkers may be dominated by computers but it certainly isn't won.
On the subject of complexity I think there is a discussion going on in
another group on this subject at the moment (I'm sorry, I don't know which
group). The idea is that beginners at a game are called (say) level 1. Anyone
who can beat a level 1 player 75% of the time or more is level 2. Anyone
who can beat the worst level 2 player 75% of the time or more is a level 3,
and so on. The complexity of the game is given by the number of levels
between the world champion and the beginner.
Noughts and Crosses is probably a level 1.
Checkers is (I understand) about a level 3.
Chess comes out around 9 or 10.
Go is (from memory) about 40.
Bridge, Kriegspiel and other similar games can be eliminated from this
discussion because they don't have perfect information and aren't zero sum
(this is a joke). I think bridge is interesting but I suspect a good
program ought to win at bridge before it wins at Go (just a gut feeling but
I'll try to justify it if anyone's interested).
Huw
--
Huw Roberts (h...@siesoft.co.uk) Siemens Nixdorf Information Systems Ltd.
+44 344 850982 Oldbury, Bracknell, Berks. RG12 4FZ England
Ixanian Nichols
Darse;
I think you need to define the term 'strategic' a little better.
You say that rec.games.board is too diluted for those of us interested
in 'purely strategic' games, yet nowhere in your list of examples did I
see mention made of strategic-level wargames and economic/socio-political
games. I, and probably a great many others, are going to consider such
games as A3R, Diplomacy, Civilization, 1830, Axis and Allies, Risk,
Supremecy, and any number of wargames and conflict simulations to fit
the description 'purely strategic'. And you can't argue that they should
go to rec.games.board because they have boards, since so, too, do Chess,
Go, Pente, Shogi, Reversi, Tic-Tac-Toe, and virtually all games with the
word 'Checkers' in the name, to name just a few.
If what you want is a newsgroup that just allows discussion of
the games you, personally, are interested in, you're going to have to
moderate it. I understand what kind of game you're attempting to single
out, and I'll bet a lot of others do, too. I think the name you are
looking for is something more like:
rec.games.abstract.strategy.not.involving.simulation.of.reality
My suggestion: leave the net alone. Start a mailing alias.
They work just as well (or better), and can be moderated to virtually
any extent the owner desires.
- Ix
s9874203
>Forwarded message for Howard, who doesn't have USENET access:
>
>
>
>consider Go with Black getting 5 points of komi and being allowed to play
>mirror Go.
>
But black will collape eventually if he exactly mirrors white's play
assuming the first black stone is at tengen. I don't understand your
point, Howard.
bn 2k
RING, DAVID WAYNE
>Note that these numbers are not the same as the mistakenly calculated 300^70
>posted earlier. That number should perhaps be 300! / 70!, something like 10^640.
300^70 is correct. I can't imagine what 300!/70! might refer to. Perhaps you
mean 300!/230! which is within the accuracy of the calculation anyway.
Dave Ring
dwr...@zeus.tamu.edu
Kenneth S A Oksanen
h...@siesoft.co.uk (Huw Roberts) writes:
>[..] The idea is that beginners at a game are called (say) level 1. Anyone
>who can beat a level 1 player 75% of the time or more is level 2. Anyone
>who can beat the worst level 2 player 75% of the time or more is a level 3,
>and so on. The complexity of the game is given by the number of levels
>between the world champion and the beginner.
>Noughts and Crosses is probably a level 1.
>Checkers is (I understand) about a level 3.
>Chess comes out around 9 or 10.
>Go is (from memory) about 40.
The relative amount of draws to wins and losses distorts this kind of
analysis of game complexity too much. Neither can this analysis be
extended from chess or go to rarely or non-competitively played games
since there simply might not exist players which would know to game
as well as Kasparov knows chess.
--
; (c) 1991 by Kenneth Oksanen, <ce...@cs.hut.fi>, +358-0-4513377 or -555017
((lambda (a) (a a ((lambda (a) (lambda () (set! a (+ 1 a)))) 2))) (lambda
(a b) ((lambda (c) (newline) (write c) (a a ((lambda (b) (lambda () (b b)))
(lambda (a) ((lambda (b) (if (= (modulo b c) 0) (a a) b)) (b)))))) (b))))
John Rickard
: The computational complexity of a game is normally taken to be the number
: of possible games.
:
: Thus for Go the number is close to 361! (361 x 360 x 359 x .... x 3 x 2). You
: could say it is smaller by 4! or maybe 8! because of symmetery in the board,
: but dividing 361! by 8! hardly changes the result. Of course it could be a
: bit larger because of ko and replay into large previously captured areas, but
: that would not change the overall number by much. So, 361! is about 10^924.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In fact, it changes it enormously. I can show that there are more
than 10^(10^10) possible games (with no repeating of a board position
allowed in a game). You can work out that this must involve games
with thousands of millions of moves, with a lot of recapturing. (In
fact my proof involves a position with 60 kos on the board.)
(I agree with other posters who have argued that the number of
possible games says very little about a game.)
-- John Rickard
jba...@desire.wright.edu
Although I have never played go, it sounds to me that we are talking
about two seperate things. Without meaning to start an arguement, I'd
say chess is more a more complex game, while go might be (I've never played
remember) a more difficult game. I have somewhat arbitrarily choosen
these words but it seems that go has simplier moves and rules but has
more total postions and games.
As far as ranking the overall skill level of a game, I have no clue.
Would a chess International Grand Master do well at Go after playing a
few times? Would a Go (I don't know the rank name) Master do well at
Chess?
P.S. I have beaten a chess master. Of course this was at a Rennaisance
Festival and he was playing 20 boards! :)
--
Jim Batka | Always remember ... | Buckaroo
Modemman | No matter where you go, there you are! | Bonzai
--------------+--------------------------------------------+--------------
| Work Email: BAT...@CCMAIL.DAYTON.SAIC.COM | Elvis is
| Home Email: JBA...@DESIRE.WRIGHT.EDU | DEAD!
--------------+--------------------------------------------+--------------
| 64 years is 33,661,440 minutes ... and a | Beatles:
| minute is a LONG time [Includes Leap Days]!| Yellow Submarine
Siva Chelliah
>In article <darse.714354066@silver-vly> da...@cs.UAlberta.CA (Darse Billings) writes:
>>
>>
[ stuff deleted ]
>
>2) What will happen when computers finally beat all human beings in
>Chess? Will there be less interest in Chess after that, or more?
>Or will there be a migration to Shogi or Go?
I do not think so. Why should we quit playing chess? Unless the computer
finds an easy way to win in chess, it will still be a very difficult game
to play for humans; it will still be difficult to remember all possible wining
positions; it will still be a facinating game ...
But... if the computer finds, say, first 10 moves for white which leads to
a winning position, then people will loose interest in chess.
My $0.02 worth.
Siva (si...@bally.com), Bally Systems, Reno, NV 89502
>--
>Antti Karttunen -- $B%"%s%C%F%#!!%+%k%C%H%%%M%s(J (et{ty|t|n)
Michael Dobbins
>Although I have never played go, it sounds to me that we are talking
>about two seperate things. Without meaning to start an arguement, I'd
>say chess is more a more complex game, while go might be (I've never played
>remember) a more difficult game. I have somewhat arbitrarily choosen
>these words but it seems that go has simplier moves and rules but has
>more total postions and games.
You have never played go? Have you looked at the underlying principles
for a digital computer? 2 state memory (0 or 1) plus 2 or 3 logic gates
(nand, nor, not). Simple rules which can create vast levels of
complexity. We can even use the computer programs that play chess and
go to measure relative complexity. Which is a more complex program, one
which plays chess and beats a top world level chess player or one which
plays go and beates a top world level go player. I beleive we have a
handle on the chess program. The go program is still a dream.
If you have never played go, how can we take your opinion about go
seriously? Play and study go seriously for about a year and then come
back and tell us what you think about the complexity of go.
Mike, 7kyu (a chess player who quit playing chess when I
discovered go)
jba...@desire.wright.edu
> In article <1992Aug28....@desire.wright.edu> jba...@desire.wright.edu writes:
>>Although I have never played go, it sounds to me that we are talking
>>about two seperate things. Without meaning to start an arguement, I'd
Guess I did anyway :).
>>say chess is more a more complex game, while go might be (I've never played
>>remember) a more difficult game. I have somewhat arbitrarily choosen
>>these words but it seems that go has simplier moves and rules but has
>>more total postions and games.
My definition of 'complexity' is the level of difficulty for a human player
to learn to play. This means knowing all of the possible moves, pieces,
etc. My definition of 'difficulty' is the measure of effort required
to become a proficient player.
>
> You have never played go? Have you looked at the underlying principles
> for a digital computer? 2 state memory (0 or 1) plus 2 or 3 logic gates
> (nand, nor, not). Simple rules which can create vast levels of
> complexity. We can even use the computer programs that play chess and
> go to measure relative complexity. Which is a more complex program, one
> which plays chess and beats a top world level chess player or one which
> plays go and beates a top world level go player. I beleive we have a
> handle on the chess program. The go program is still a dream.
>
I never meant to denigrate Go and I offered my perspective as a
(relatively speaking) objective outside observer.
> If you have never played go, how can we take your opinion about go
> seriously? Play and study go seriously for about a year and then come
> back and tell us what you think about the complexity of go.
>
I obviously am not the person to ask for intricate game strategies!
However, I think you should chill a little bit. I did NOT say Go was
any of the following: Boring, Easy, Stupid, or Simple. In fact, I
think a game that is easy for a novice to learn to play, BUT difficutl
to master is probably better then one that requires a master to play
at ALL.
Therefore, I gave GO a compliment by saying it wasn't as complex as chess.
Anyway, I'd love to take you up on the offer to learn Go, except I have
other things to take care of right now (my pregnant wife, my 2 yr old
daughter, my job, my master's thesis, my house, etc., etc., ad nausium).
> Mike, 7kyu (a chess player who quit playing chess when I
> discovered go)
--
Jim Batka | Always remember ... | Buckaroo
Modemman | No matter where you go, there you are! | Bonzai
--------------+--------------------------------------------+--------------
It is very | Work Email: BAT...@CCMAIL.DAYTON.SAIC.COM | Elvis is
often easier | Home Email: JBA...@DESIRE.WRIGHT.EDU | DEAD!
to get per- +--------------------------------------------+--------------
mission then | 64 years is 33,661,440 minutes ... and a | Beatles:
forgiveness! | minute is a LONG time [Includes Leap Days]!| Yellow Submarine
Ron_Ko...@transarc.com
world-class chess machine, but that a go machine is still a dream. For some
reason he fails to mention that there's probably been on the order of $1 spent
on computational go for every $1000 spent on chess. I assume that he simply
overlooked this.
Now I'm not saying that chess has greater computational complexity than go
or vice-versa. I'm just observing that nobody knows this right now, and
suggesting that we all refrain from premature judgement or dogmatic
assertions in the absence of compelling research. Go has a far greater
search space when counted naively, but it also has lots of regularities that
chess doesn't have. It may turn out the game is susceptible to a completely
different kind of algorithmic approach, e.g., heavy pattern-matching. We
don't know.
Ron Kownacki
rON.
>"Mike, 7kyu" correctly points out that we are close to getting a handle on a
>world-class chess machine, but that a go machine is still a dream. For some
>reason he fails to mention that there's probably been on the order of $1 spent
>on computational go for every $1000 spent on chess. I assume that he simply
>overlooked this.
This is very true and a very significant fact. Though its been estimated that
if the same amount of time/money had been spent on Go as it has on Chess
that the Go programs would still not be near the level of Go professionals.
(see below for justification, not argumentation :)
>Now I'm not saying that chess has greater computational complexity than go
>or vice-versa. I'm just observing that nobody knows this right now, and
>suggesting that we all refrain from premature judgement or dogmatic
>assertions in the absence of compelling research. Go has a far greater
>search space when counted naively, but it also has lots of regularities that
>chess doesn't have. It may turn out the game is susceptible to a completely
>different kind of algorithmic approach, e.g., heavy pattern-matching. We
>don't know.
Some of us that program Go do know, though :)
The big difference (and this is what makes programming Chess and programming
Go so different) is their strategies. Programming a computer to play a game
of Go is a simple task. Programming a computer to play a game of Chess is a bit
more difficult, but still quite simple. Wheres the difference?
In Chess, strategies are more 'tactical'. In Go, strategy is more conceptual.
What does this mean? Well, in Chess, if you opened with (and I don't know the
proper names of these, I'm only in here to watch for news of the Fischer
match :) a Caro-Kann opening and I defended with an Alkheine and you jumped to
a Kings Gambit Over Easy, Declined, etc. I would know how and where to respond-
what lines are 'good' and what are 'not good'. In the endgame, as well, there
are 'standard' strategies for situations- K vs KRP, for instance. From my
point of view, these strategical decisions, especially in the opening, are
fairly straightforward- a player with better knowledge/reading abilities has
an edge over a player who doesn't know the Kings Gambit Over Easy, Declined
line of play. Not to say (at all!) that intuition doesn't play a big role in
Chess- why does a player like Karpov (ok, besides the fact that he's the best
in the world :) usually beat the best computer players? Flexibility- he is
able to adjust his style of play, and subsequent strategies to the situation
at hand. This is a conceptual thing that computers are only now beginning to
get a grasp on.
In Go- strategies are more 'conceptual'- When to play tenuki (someplace else)
in a local situation- what tesuji (localized strategic play) will yield
influence on a distant part of the board, etc. A sense of timing, flow,
'momentum' as it were, is vital in playing go- not as much in Chess, where
games can be decided quickly or drawn frequently, and keeping the 'offense'
can shift every turn. Go games last many more moves over a larger area, so
that 'flow' is more important.
Proof? Well, chess lends itself with its strategies to brute-force (the
favourite argument of Go programmers, it seems :) searches of reasonably
limited size- strategy pools can be formed and decisions made based then
on this look-ahead. Go, unfourtunately, can't do that. While there is a lot
of 'this is good, this is not' moves in Go, there is a big jump between, say,
saying 'you can't play here because it fills in a eye' or 'you put yourself
in atari (danger of being captured)' and 'this move reduces your eye potential'
or 'you reduce your liberties, if White plays at point B surrounding your
group'. The point? Right now, computer 'thinking' fits a Chess model really
really well. Future technologies (like Neural Nets, for an instance), will
be more useable by Go programmers.
In 10 years or so, when the current Chess people are tired of trying to produce
a bigger beast to beat up on the big beast that beats up on the World Champion,
they'll turn to Go. Go is becoming more popular (though it is still reasonably
obscure 'man- you guys are good at pente!'), and will get more focus in the
programming world.
r.
(of course, all this is my own opinion, take it as you will :)
OS-9 User Group
RE: computer go vs. computer chess -- difficulty in coding
Chess programmers have another major advantage over Go programmers.
At any given point they can do a simple board evaluation: count the
men left on the board, weighting them appropriate (9 for queen, etc.)
and compare the totals.
On the other hand.. how do you evaluate a position on the Go board?
Especially during the opening stages of the game? If you ask a
professional "Who has the better position here?" they will say things
like "The territory black has created isn't nearly as valuable as this
thick white wall." Or "Even though this white area is secure for now,
there is a bad taste to it which will cost white the game." How do you
evaluate that with a computer?
Not only does the brute force approach fall apart due to extensive
possibilities in Go, but once you have read to the bottom ply, there
is no good way to decide if what you end up with is a good or bad
result. Whereas in chess a fast and incredibly simple little
algorithm can answer this with a simple sum and compare algorithm.
.
Justin, 6 kyu
Ralf Stephan
^^^^^
I think this is nice a habit. We chess players should also sign with
our rating (no sarcasm!!).
--ralf, 1700 (non-USCF)
The Technicolour Throw-up
> Questions I have wondered:
>
> 1) What is the most complex (human invented) game 'computationally'?
> Go???
Another possibility that I just remembered is the "save-go" game that someone
described in the go group last year. I have a deep seated suspicion that its
too complicated for humans to play. Its possible to come with versions of
intermediate complexity - in fact one can create an infinite hierarchy with
ordinary Go being in the 0th position and save-go in the infinitieth
position. All the intervening ones (position 1, 2, 3 etc) would all be more
complicated than ordinary Go. I don't immediately see why one couldn't have
save-chess, save-shogi etc.
--
Just my two rubber ningis worth.
Name: Michael Chisnall (chis...@cosc.canterbury.ac.nz)
I'm not a .signature virus and nor do I play one on tv.
Aggelos Keromyths
It's something that i think is missing ,along with a rec.games.wargames...
Aggelos
Tim Philip
Excellent idea!!!
Tim, 1900 (non-USCF).