"Anti-computer" abstract games
Pekka Karjalainen
I am curious about games that are considered very hard for computers. By that
I mean that it is considered very difficult or impossible to make a computer
program that can consistently play at or above the level of top human players.
Obviously a variant of checkers on a really huge board would be difficult from
a purely computational point of view. It would also be very difficult for
humans to beat, even just considering how long the games would take.
Specifically, if I would be interested in learning some new abstract games,
what should I look into if being able to beat the top computer programs were the
most important thing in the game? (It is not, but I am just asking)
How hard is it for a human to top the programs at shogi? How about amazons?
What is it about a game that makes it hard for computers to play well relative
to humans? Or the opposite, why is it that some games, while not nearly solved,
are already computer dominated at the top? I think othello would fall into the
second category as well as American checkers.
Is anyone keeping track of level of play in various abstract games relative to
humans? I know of Victor Allis's thesis, but beside it little else on the
subject.
Any comments? Thoughts?
Pekka Karjalainen
PS. Something recent on computer go:
http://www.msoworld.com/mindzine/news/orient/go/euro/mso4liao1.html
Tim Hunt
Well Go is the game that immediately springs to mind. I am, of course,
biassed, because go is the game I take most seriously, but it is a good
game and note too difficult to learn. If you want to learn then one way
to go about it is to download Igowin, which is a free 9x9 version of the
popular program Many Faces of Go. It is available at
http://www.britgo.org/gopcres/gopcres1.html
That is for windows PC. For Linux and assorted other platforms there is
GNU Go:
http://www.gnu.org/software/gnugo/gnugo.html
You can, of course, play online against other humans, and find lots of
articles about go on the web.
So why is go so difficult for computers? There are two answers. The most
common anwer is that since a go board is so large (19x19 = over 200
candidate moves in most positions) and the game lasts so long (around
240 moves, 120 by each player) it is very difficult to get anywhere with
look-ahead. This can't really be the answer since a game like go-moku
or renju (5 in a row played on a go board) has virtually the same
branching factor yet computers can play it very well.
The other and more severe problem with trying to get computers to play
go is that it is very difficult to analyse how good a given position is.
A human might look at the position and think "this area is probably
black territory, that area is probably going to be white, and this group
here is at risk of being attacked". Computers don't think like that
(yet). Since it is hard to have a good evaluation function, the fact
that it is difficult to do look-ahead to patch up the weaknesses in your
evaluation function becomes a real problem.
Now compare this to chess (about which I know less). The thing that
makes chess tractable is that there is an easy to compute evaluation
function that is not too bad. Namely add up all of the material. This is
not nearly enough to play good chess. Human players have much more
sophisticated positional judgement that this and take into account all
sorts of other featuers of the position, but the value of material is a
good start. There just isn't an equivalent of this in go. Modern chess
programs build in much more than just material into there evaluation
function, which makes them stronger, and then they use look-ahead to
improve the evaluation still further. And all this uses lots of
optimisations and pruning and so forth.
I think that there is another feature of chess that helps here, but I am
not really a good enough chess player to be sure. Chess is sort of one
big battle, and with rooks and bishops and queens having the ability of
dash all-over the board it is quite well-mixed. By contrast, in a game
of go you tend to have a fight in one part of the board, and then you go
and play in a different part for a while. Each of these battles is sort
of a local problem, but to evaluate the result you have to look at the
whole board. If the computer has failed to spot a problem with one part
of its position then all its evaluations are going to be nonsense.
I think that the other side of the coin is a game like Backgammon. I
would say that backgammon is a game consisting almost entirely of
positional judgement. You can play very well with no look-ahead at all.
And this is in fact how the best programs works. They have a superb
evaluation function.Of course, these days they also use 3-ply
look-ahead, but that is almost oer-kill. omputers were approaching the
best humans when they were doing just 1-ply lookahead.
So how do backgammon evaluation functions work. Well there were lots of
efforts to make them by hand. Then Gerald Tesauro had the idea of using
a nural net (and developen a good way of inputting the position and a
good training algorithm) and the standard of computer backgammon
suddenly jumped up. If positional judgement is so important in go, why
doesn't the same idea work there? This is a good question. I think that
the answer is that tactics are so important in go. In Backgammon, the
random throws of the dice mean that it is virtually impossible to
predeict exactly what is going to happen. Instead one must play the
averages. Neural nets seem to be good at evaluating averages like this,
and making very fine judgements between positions.
Tim.
--
Tim Hunt, PhD Student, Department of Applied Mathematics
and Theoretical Physics, Cambridge University, U.K.
Member of the Cambridge Go Club and 2 dan.
http://www.cam.ac.uk/CambUniv/Societies/cugos/
Torben AEgidius Mogensen
> I am curious about games that are considered very hard for
>computers. By that I mean that it is considered very difficult or
>impossible to make a computer program that can consistently play at
>or above the level of top human players.
> Obviously a variant of checkers on a really huge board would be
>difficult from a purely computational point of view. It would also
>be very difficult for humans to beat, even just considering how long
>the games would take.
> Specifically, if I would be interested in learning some new
>abstract games, what should I look into if being able to beat the top
>computer programs were the most important thing in the game? (It is
>not, but I am just asking)
> How hard is it for a human to top the programs at shogi? How about amazons?
> What is it about a game that makes it hard for computers to play
>well relative to humans? Or the opposite, why is it that some games,
>while not nearly solved, are already computer dominated at the top?
>I think othello would fall into the second category as well as
>American checkers.
Othello is indeed a very computer-friendly game, for the following
reasons:
1) The number of legal moves is fairly limited - typically below 10
on average.
2) The endgame is important and even more limited in number of legal
moves, which makes it possible for a computer to play a perfect
endgame 12-15 moves mefore the end.
3) A relatively large part of the board changes with every move,
which makes it hard for humans to keep track of what the board
looks like after a few moves - even if only on path is examinated.
Go, on the other hand, is considered hard for computers, as it has
essentially the opposite features:
1) The number of legal moves is huge - averaging above 50.
2) The endgame is fairly unimportant, so it doesn't help (much) to
play a perfect endgame.
3) Most moves change very little on the board, so it is possible for
a human to follow a single line of moves quite far.
Chess is somewhere in the middle:
1) The average number of legal moves is somewhere around 30 (at a
very loose estimate).
2) The endgame can be important, but many games are decided before
this. In any case, special instances of endgame can be played
perfectly by the computer (but these will also be trivial for a
competent human player).
3) A single move changes relatively little on the board.
I think the most important features of a computer-unfriendly and human
friendly game are:
1) The number of possible moves at any given time is large.
2) A single move will (on average) change very little on the board.
3) The game will usually be decided before a computer is able to play
a perfect endgame.
Increasing the number of moves can be done by having a large board (as
in Go) or by increasing the complexity of a single move. Examples:
- Othello can be made to have a larger number of legal moves per
turn if a simple modification is made: Instead of flipping over
all disks in a captured line, the player is given a choice of
which disks in the line are turned. Hence, a line of 4 captured
disks would yield 16 different possible outcomes.
- In Shogi, the number of possible moves is higher than in Chess, as
you can drop a captured piece almost anywhere on the board.
The proposed modification to Othello doesn't make it simpler for
humans, though. It just levels the field a bit by making brute-force
search less effective.
The (average) amount of change made by a single move is easy to
measure. It may, hoever, be hard to modify a game to decrease this.
Again, Othello is a good example: The nonlocal changes made by a
single move are quite central to the nature of the game. The proposed
choice of which disks to flip does decrease the change a bit, but not
enough to make a significant difference.
How often a game will be decided before the endgame becomes manageable
by a computer is harder to measure, but playing a number of games will
probably give you a feel of this.
Torben Mogensen (tor...@diku.dk)
Timothy Chow
Torben AEgidius Mogensen <tor...@diku.dk> wrote:
>Othello is indeed a very computer-friendly game, for the following
>reasons:
> moves, which makes it possible for a computer to play a perfect
> endgame 12-15 moves mefore the end.
Yes, this is extremely important.
> 3) A relatively large part of the board changes with every move,
This is just plain false. In a well-played game of Othello, few disks are
flipped on most moves, except in the endgame.
> which makes it hard for humans to keep track of what the board
> looks like after a few moves - even if only on path is examinated.
This part is somewhat true, but the difficulty is not with the fact that a
large part of the board changes with each move, but that consecutive moves
sometimes flip the same disk. Since accurate calculation requires you to
"see" the whole board a few moves into the future, a single mistake as to
whether a certain disk has been flipped two times or three times can destroy
the validity of the entire evaluation.
>Go, on the other hand, is considered hard for computers, as it has
>essentially the opposite features:
> 2) The endgame is fairly unimportant, so it doesn't help (much) to
> play a perfect endgame.
I don't play go, but is this really true? Surely two strong players of
approximately equal strength can keep the game relatively balanced for
most of the game, with endgame tactics deciding the game.
>Chess is somewhere in the middle:
> 2) The endgame can be important, but many games are decided before
> this. In any case, special instances of endgame can be played
> perfectly by the computer (but these will also be trivial for a
> competent human player).
This is mostly true, but the parenthetical comment is false. There are
plenty of five-piece endgames that can be played perfectly by computer
but which will baffle even grandmasters (unless they've specifically
studied the computer databases).
>I think the most important features of a computer-unfriendly and human
>friendly game are:
> 1) The number of possible moves at any given time is large.
This itself isn't a very good guide. In chess, King and Queen against
King is much easier to play than King and Rook against King, even though
the number of possible moves at each step is 50-100% larger.
What is needed is a game in which human pattern recognition is difficult
to codify. Go seems to meet this criterion, although I personally think
that a big reason for the weakness of current go programs is simply that
not as much effort has been poured into it, compared to computer chess.
If we spend as much time and other resources on computer go as we have
on computer chess, I bet that very strong programs will emerge.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
Tim Hunt
> >Go, on the other hand, is considered hard for computers, as it has
> >essentially the opposite features:
> > 2) The endgame is fairly unimportant, so it doesn't help (much) to
> > play a perfect endgame.
>
> I don't play go, but is this really true? Surely two strong players of
> approximately equal strength can keep the game relatively balanced for
> most of the game, with endgame tactics deciding the game.
Yes, it is not uncommon for professional games ot finish with one person
winning my only one or two points. In this case the endgame is very
important. But in games by weaker players there tend to be large
mistakes so most games are won by about 10 point margins. In this sort
of game the endgame is important for a different reason. The player who
is 10 points ahead would like to know for certain that if they stop
fighing and start playing endgame moves to consolidate their lead, then
they will win. In other words, to estimate the balance of territory in
the middle game you need to understand the endgame.
> What is needed is a game in which human pattern recognition is difficult
> to codify. Go seems to meet this criterion, although I personally think
> that a big reason for the weakness of current go programs is simply that
> not as much effort has been poured into it, compared to computer chess.
> If we spend as much time and other resources on computer go as we have
> on computer chess, I bet that very strong programs will emerge.
There are at least 3 top go programs, all being developed full time, and
competing in several tournaments each year. And a large market for a
strong go program in the far east. Until recently there was a prize of
about $1,000,000 for a program who could beat a trainee professional
(about the same strength as a top ammateur). People have been writing go
programs for at least 30 years. Dispite all this effort go programs are
still weaker than most club players. For go programs to reach the level
of the best humans requires more than lust lots of work at incremental
improvements. Ww still need to find the right basic approach.
Tim.
P.S. The following looks like an interesting review:
An Introduction to the Computer Go Field and Associated Internet
Resources
http://www2.psy.uq.edu.au/~jay/go/CS-TR-339.html
Ray Tayek
says...> >...
> >Go, on the other hand, is considered hard for computers, as it has
> >essentially the opposite features:
> > 2) The endgame is fairly unimportant, so it doesn't help (much) to
> > play a perfect endgame.
>
> I don't play go, but is this really true? Surely two strong players of
> approximately equal strength can keep the game relatively balanced for
> most of the game, with endgame tactics deciding the game.
it depends, if the game is close, it will be decided by engame (for the
pros, this is a few points, for amatuers, it's 5-? points.) but in many
cases (especially with amateurs) one or more large groups will be killed,
rendering the endgame irrelevant.
other than sheer size (its *real* big), one of the reasons that go is
hard is that it is good practice to leave things unsettled for as long as
possible. this makes it very hard for a program to evaluate anything.
hth
--
Ray (will hack java for food) http://home.earthlink.net/~rtayek/
orange county java users group http://www.ocjug.org/
want privacy? http://www.freedom.net/
hate spam? http://samspade.org/ssw/
David Rush
> People have been writing go
> programs for at least 30 years. Dispite all this effort go programs are
> still weaker than most club players.
No kidding. I was never a very good player (10 kyu was about my best)
but I have drastically slipped in the years since my club days - at
least partly from playing against computers. Not only do they play
badly, they don't even play in a 'good' style.
> For go programs to reach the level
> of the best humans requires more than lust lots of work at incremental
> improvements. Ww still need to find the right basic approach.
This is likely to reamin hard for a while, methinks. The combination
of low-level detail and high-level strategy involved in the game is
really quite daunting. I find chess to be an almost entirely tactical
when you compare it to go (and it goes without saying that chess has a
strong strategic component).
david rush
--
Lambda calculus -- Call us a mad club.
-- James A Crippen (on comp.lang.scheme)
Paolo Fasce
tc...@lsa.umich.edu (Timothy Chow) wrote:
The range of our projectiles---even ... the artillery---however great,
will never exceed four of those miles of which as many thousand
separate us from the center of the earth. ---Galileo, Dialogues
Concerning Two New Sciences
I'm quite sure that Galileo never pronounced that words...
.
.
.
.
.
.
You should write them in Italian. 8-)
--
Paolo Fasce
Gerry Quinn
>I think the most important features of a computer-unfriendly and human
>friendly game are:
>
> 1) The number of possible moves at any given time is large.
>
> 2) A single move will (on average) change very little on the board.
>
> 3) The game will usually be decided before a computer is able to play
> a perfect endgame.
>
Some of you may be interested in my game Zen based on Conway's Life. It
is probably somewhere in the middle regarding computer friendliness.
The computer plays well on a small board with a some lookahead but no
minimax so far.
I'd say it scores highly on 1 and 3 above, but the score on 2 varies
with board size.
The computer is helped because it is difficult to foresee the evolution
of unfamiliar patterns. Familiar patterns are quite common, though.
You can download a Windows version from my website. The free version
plays a full game but variants of the rules are restricted.
Gerry Quinn
--
http://bindweed.com
Puzzle / Strategy Games and Kaleidoscope for Windows
Download evaluation versions free, no time limits
New: Unique 2-player strategy game "Zen"
Stephen Tavener
analyse, but for games where a human has an edge over a computer. To
me, this speaks of:
1. A large branch factor (lots of plausible moves each turn)
2. Patterns that appear in the game that are easy for humans to spot,
but hard for the computer
Several folks have already mentioned Go, so I'll mention a few more
obscure games...
Octi - stacked pieces, recycling pieces, and moving prongs makes for a
lot of possibilities for a computer, but to a human, the game seems
quite intuitive.
ZERTZ - if you are not capturing, you drop a ball anywhere on the baord,
then remove a ring - about 3x30x15 = 1,350 moves each turn from a
typical position. Yet, a human can recognise potential patterns and
force sequences of up to 11 moves to make advantageous captures.
TAMSK - played with egg timers, with strict time limits per move, if a
computer program tries to minimax, it will lose its pieces :)
FIBONACCI - players can make up to 6 consecutive moves, and a group of
connected pieces have great mobility. I once estimated the number of
available moves at about 800 million per player turn!
TTFN,
Stephen
--
Stephen Tavener | There is no such thing
Games bought,sold,traded,played | as "just a cat"
http://www.scat.demon.co.uk/ | - Tanya Huff
MLHowe
Fibonacci? Thanks.
fizzycyst
Nick Wedd
<tjh...@damtp.cam.ac.uk> writes
[Go-playing programs]
>There are at least 3
More than 3. E.g. GoeMate, Go4++, Many Faces of Go, Go Intellect,
GoStar, Explorer, Indigo. (with apologies to those that I have missed)
>top go programs, all being developed full time, and
>competing in several tournaments each year. And a large market for a
>strong go program in the far east. Until recently
and this year. The November 2000 Ing Cup is likely to be the last.
> there was a prize of
>about $1,000,000 for a program who could beat a trainee professional
>(about the same strength as a top ammateur).
Indeed. This week, one of the top programs received a nine-stone
handicap from a six-year-old boy, and lost. See
http://www.msoworld.com/mindzine/news/orient/go/euro/mso4liao1.html
> People have been writing go
>programs for at least 30 years. Dispite all this effort go programs are
>still weaker than most club players. For go programs to reach the level
>of the best humans requires more than lust lots of work at incremental
>improvements. Ww still need to find the right basic approach.
Indeed. How is it that Tim and I can play Go much better than any
program? What is it that we can do, but a Go player much stronger than
either of us cannot code? I have no idea.
Nick
--
Nick Wedd ni...@maproom.co.uk
Stephen Tavener
<mlh...@aol.com> writes
>Do you know any URLs that link to rules or more infomation about Zertz and
>Fibonacci? Thanks.
There are reviews of both on my web site:
http://www.scat.demon.co.uk/reviews.html
The home page of GIPF/TAMSK/ZERTZ:
http://www.gipf.com/
There is a Fibonacci web site out there, but I can't find it at the
moment :(
TTFN,
Stephen
>
>
>fizzycyst
Torben AEgidius Mogensen
>Indeed. How is it that Tim and I can play Go much better than any
>program? What is it that we can do, but a Go player much stronger than
>either of us cannot code? I have no idea.
This comparison assumes game-playing programs work in a fashion
similar to human players, which is far from the case.
A computer has the advantage of being able to examine a large number
of configurations in little time, but it is bad at seeing patterns and
formulating long-term strategies. The latter is what most human
players do.
I once heard that even grand master Chess players examine a total of
less than 100 moves on each turn, whereas a program will examine
several hundreds of thousand (and perhaps millions) of moves. Each
position is, however, evaluated in a fairly naive way, which makes the
value of each examined position worth much less than a position
considered by a grand master (or any reasonably competent human
player).
If we consider Go, a similar thing applies. What makes it harder for a
computer is, partly, that the branching factor is much larger than in
Chess, so a smaller fraction of the remaining game can be examined by
the computer and partly that a naive evaluation of a single
configuration isn't likely to be accurate enough.
Hence, in Go, more emphasis has to be put on position evaluation than
in Chess, and this is much harder. And even though a lot of theory has
been developed for Go regarding live/death estimation etc., a lot of
what happens inside the head of a good Go player is at a subconscious
level, which makes it very hard to quantify and transfer to a computer
program. While the same is true for Chess, it isn't as important
because naive methods have been reasonably successful (when backed up
by massive computer power).
Torben Mogensen (tor...@diku.dk)
Pekka Karjalainen
Stephen Tavener <Ste...@scat.demon.co.uk> wrote:
>Several folks have already mentioned Go, so I'll mention a few more
>obscure games...
>
games. Also, thanks to the other contributors to this thread!
I noticed some discussion about Crazyhouse chess at a computer chess forum
recently. Apparently this game is also more difficult than orto-chess for
computers, for many of the same reasons that make shogi very difficult too.
Crazyhouse is chess augmented with the drop-rule from shogi. It is also
sometimes called drop-chess or chessgi, appropriately enough. If you are
interested, you can play it at some of the chess servers that are on the 'net.
You'll find more info with Google or other search engines.
Regards,
Pekka K.
djom...@my-deja.com
Another idea you might like to consider for anti computer games: a
local sample or game fragment.
If you take a sample of a chess board of say three squares by three
squares and you see black takes white's queen for the cost of a bishop
then you can conclude, quite often correctly that black has gained a
large advantage.
If in a game of Go you take a sample of the board of say five lines by
five lines then the pattern of play you see on those interesections, in
isolation tells you nearly nothing of the relative advantages to the
two players. Even if you see white capture a black group, you still
cannot know whether white or black should rejoice. Go is a very
nonlinear game. The meaning of any stones strongly depends on their
context, which changes throughout the game.
Do you think the idea of local samples could help in characterising an
anti- computer game?
Regards David Milne.
>
Sent via Deja.com http://www.deja.com/
Before you buy.
camradood
rules ( 2 dice), and the number of positions is very small compared to Go,
so it is very easy for a program to use relatively simple algorithms to work
out best postion.
"Tim Hunt" <tjh...@damtp.cam.ac.uk> wrote in message
news:39A1369D...@damtp.cam.ac.uk...
Douglas Zare
> Plus the fact that backgammon relies on a very simple set of probability
> rules ( 2 dice), and the number of positions is very small compared to Go,
> so it is very easy for a program to use relatively simple algorithms to work
> out best postion.
The dice give you an additional branching factor of 21 per ply, so the
probability rules for go are simpler. There are about 2^64 positions in
backgammon (sans cube) compared to about 2^500 in go, I'm guessing, but I don't
see what advantage that gives. Barring underpromotion in chess would not make
it a substantially simpler game, but it would decrease the number of legal
positions, I would guess by a square root. Incidentally, there are often
thousands of ways to play 1-1 or 2-2 in backgammon, and computers do not have
the speed to consider all of them.
I get the feeling that computers could easily be trained to play decently on a
longer backgammon board (than the current 24), but that they would do miserably
on larger go boards.
Danny Kleinman tried to use increasingly complicated rules for his backgammon
algorithm. That didn't work nearly as well (even ignoring the cube), and I
think that the reason was more than that DK was not an expert backgammon
player. Some comments on this are made in his _Vision Laughs at Counting_ book.
Following relatively simple algorithms is not the strength of computers in
complicated games.
> "Tim Hunt" <tjh...@damtp.cam.ac.uk> wrote in message
> news:39A1369D...@damtp.cam.ac.uk...
> > I think that the other side of the coin is a game like Backgammon. I
> > would say that backgammon is a game consisting almost entirely of
> > positional judgement. You can play very well with no look-ahead at all.
> > And this is in fact how the best programs works. They have a superb
> > evaluation function.Of course, these days they also use 3-ply
> > look-ahead, but that is almost oer-kill. omputers were approaching the
> > best humans when they were doing just 1-ply lookahead.
Not really, despite the reports in Tesauro's "Temporal Difference Learning of
Backgammon Strategy," _Machine Learning_ 1992. With longer sessions I'm
confident that all three world-class players would have won at least 60-40
rather than the 18-13, 2-6, and 4-9 results. One difficulty with discussing
this is that both computer play and human play have improved, the latter as a
result of the former (and computer rollouts rather than evaluations), and the
former primarily through faster computers. Now humans play better than
computers in some positions, and computers play better than humans in some
positions, and 1-ply computers would be pounded by .2 ppg in money play or at
least 54-46 in 1-point matches (more if the humans adopted well-known anti-bot
tactics).
> > So how do backgammon evaluation functions work. Well there were lots of
> > efforts to make them by hand. Then Gerald Tesauro had the idea of using
> > a nural net (and developen a good way of inputting the position and a
> > good training algorithm) and the standard of computer backgammon
> > suddenly jumped up. If positional judgement is so important in go, why
> > doesn't the same idea work there? This is a good question. I think that
> > the answer is that tactics are so important in go. In Backgammon, the
> > random throws of the dice mean that it is virtually impossible to
> > predeict exactly what is going to happen. Instead one must play the
> > averages. Neural nets seem to be good at evaluating averages like this,
> > and making very fine judgements between positions.
In my experience, computers do quite well with the short-run tactical side of
backgammon. Humans with fortitude can try to estimate chances 2 moves ahead in
simple positions, but computers can compute most variations 3 moves ahead.
That's necessary for computers to approach world-class rather than just expert
play, since the 1-ply evaluations are not accurate enough, but make errors in
both directions.
Computers are bad at technical plays (e.g., non-contact positions) and playing
and evaluating backgames. I believe they are bad at evaluating positions with
primes in general. They are still terrible at rolling a prime home and shaking
loose a second checker after hitting the first in a deep anchor game. They do
not have a sense of the "timing" of a game, which is usually opposite the race
but is much more complicated. Computers are good at making fine judgements
between similar positions in backgammon, but only gross judgements about
dissimilar positions. They are very good at blitzes, causing a major
reevaluation of that aspect of the game.
Though it is not as easy to tabulate a material score as in chess, the hard
moves are often spaced out by a lot of easy moves during which the relative
strength of the position is easy to evaluate on a rough level.
If one naively attempts to implement a neural net on go, there just won't be
enough features it could find. Try to describe "connected" or "2-eye" in terms
of the locations of pieces; it just doesn't work. Although a sufficiently large
net much larger than practicable would theoretically work, to spoonfeed a net
simplified ideas of go probably limits the depth of the net's play. I wonder
how badly computers would play if they used no library of joseki whatsoever, as
a human 10-kyu might.
Douglas Zare
Timothy Chow
In article <39AC10CC...@math.columbia.edu>,
Douglas Zare <za...@math.columbia.edu> wrote:
>I get the feeling that computers could easily be trained to play
>decently on a longer backgammon board (than the current 24), but that
>they would do miserably on larger go boards.
I heard once that even top human go players don't do so well on a 21x21
board. Is this true?
What about 9x9 go? Do computers fare better (relative to people) on a
smaller board?
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
Gianni Cottogni
>OK, you are looking not for games that are hard for a computer to
>analyse, but for games where a human has an edge over a computer. To
>me, this speaks of:
>
>1. A large branch factor (lots of plausible moves each turn)
>2. Patterns that appear in the game that are easy for humans to spot,
>but hard for the computer
>
>obscure games...
Hi Stephen,
I would add to your list TWIXT. And perhaps ABALONE: its branch
factor is very high and Zillions plays Abalone like a moron, even with 3
minutes for move.
bye,
Gianni Cottogni
ja...@iol.it
VENARI LAVARI
LUDERE RIDERE
OCCEST VIVERE
Bruno Wolff III
>
>I would add to your list TWIXT. And perhaps ABALONE: its branch
>factor is very high and Zillions plays Abalone like a moron, even with 3
>minutes for move.
A lot of the options in Twixt are obviously bad. Also unlike Go things are
more local. While you do have to worry about ladders running into pieces
already placed far away, there is no equivalent to groups getting killed.
I suspect that huerstics could be developed to evaluate local groups and
to determine how nearby local groups are connected. With this, some very narrow
but deep lookahead for ladders and some broad but shallow look ahead at
moves with potential, computers would play this game better than the current
best human players.
Nick Wedd
<br...@cerberus.csd.uwm.edu> writes
>I suspect that huerstics could be developed to evaluate local groups and
>to determine how nearby local groups are connected. With this, some very narrow
>but deep lookahead for ladders and some broad but shallow look ahead at
>moves with potential, computers would play this game better than the current
>best human players.
Programs already do all these things, and play Go far worse than
moderate amateurs.
Bruno Wolff III
But the interconnections in Go are a lot more complicated than those in Twixt.
In a lot of cases a local Twixt position is going to be roughly equivalent
to a line of connections between two pegs. This is something that can be
dealt with.
Ray Tayek
says...
> [Note: crossposted from rec.games.abstract to rec.games.go]
>
> In article <39AC10CC...@math.columbia.edu>,
> Douglas Zare <za...@math.columbia.edu> wrote:
> >decently on a longer backgammon board (than the current 24), but that
> >they would do miserably on larger go boards.
>
> board. Is this true?
>
> What about 9x9 go? Do computers fare better (relative to people) on a
> smaller board?
>
i believe that the go board is 19x19 because the territory in the corners
and sides is about the same as the territory in the middle. smaller
boards are all about corners. the pros in japan did do some research on
larger boards, but i don't know the results ( think is was that it was
not clear how to play).
the numbers are still nasty on even a 9x9 but you could probably make
some smart program that learned. there is a free 9x9 go program at
http://www.smart-games.com/ - the author is probably a good candidate to
answer this question. also, there is a computer go mailing list at
compu...@lists.uoregon.edu.
tim2...@my-deja.com
Nick Wedd <Ni...@maproom.co.uk> wrote:
> In article <39A15445...@damtp.cam.ac.uk>, Tim Hunt
> <tjh...@damtp.cam.ac.uk> writes
> Indeed. How is it that Tim and I can play Go much better than any
> program? What is it that we can do, but a Go player much stronger
> than either of us cannot code? I have no idea.
Computer programming is hard work and takes lots of time. The
programmer may simply not have the resources to implement all the ideas
that occur to him or her.
Tim
Bruno Wolff III
>
>I do not see the logic behind classifying TwixT as so much simpler. In
>an interesting TwixT game, I cannot see how you can think of a 'line
>connection' between the pegs. Try the same with Hex, and I think the
>computer programs (that humans beat easily) would beat you, easily!
Hex is very similar to Twixt. I expect that in hex you can also treat
local groups as effectively lines in many cases. I would expect Hex
and Twixt programs to be stronger than Go programs, because the games
are simpler than Go.
For some more ideas on why local groups can't be handled as easily in Go
consider:
In Go pieces can be captured. In Hex pieces stay on the board the whole
game. In Twixt they only come off if the person who originally placed them
decides to remove them.
In Go the exact details of a local position is often going to be important
when considering connections to other local groups. In Hex and Twixt this
is not going to be the case. If Twixt and Hex generally only the ends of
a local group are going to be relevant.
In Go the number of pieces involved is important. In Twixt and Hex only
connection is relevant.