If the search was depth first, and you seeded the search with some
well played games, then alpha beta pruning ought to result in some
truely enormous reductions in the search space.
___
computer-go mailing list
computer-go@computer-go.org
Guys, keep your eyes on the prize. If your only problem
is that you need to double your speed, all you have to do
is wait 1.5 years.
All this talk of optimizing speed by tweaking language xx to be
more like assembly language (or C) is almost completely a waste
of time.
Likewise, algoritmic
There's already a pretty satisfactory blokus server and a pretty active
community of players, at blokus.com.
If computer go people are looking for easier worlds to conquer (call
it educational training for the real challenge) there is no shortage
of candidate games. One that has an active
I wonder if MC programs shouldn't prune game branches when
sufficiently large captures occur. The loss/win might not
be strictly allocated to the right player, but it certainly
means that the current game has entered sillyspace.
___
computer-go mailing
At 11:10 AM 1/15/2007, Magnus Persson wrote:
Quoting Dave Dyer [EMAIL PROTECTED]:
I wonder if MC programs shouldn't prune game branches when
sufficiently large captures occur. The loss/win might not
be strictly allocated to the right player, but it certainly
means that the current game has
Here's an idea for scaling up, which should result in only factor
of 10 slower speed. To scale from 9x9 to 19x19, subdivide the
board into four, overlapping 10x10 boards. Run a standard 9x9
monte carlo up to the 90% full stage on each of the four boards,
then run a full board monte on the
At 02:59 PM 1/30/2007, [EMAIL PROTECTED] wrote:
I'm having difficulty picturing this, so I'll start with the most basic
questions.
Do you mean Monte Carlo by itself or Monte Carlo combined with tree search
(e.g. UCT)?
The idea isn't more than lightly toasted (less than half baked), but
Of course, everything depends on how you can deal with the boarders - how
about some monte-carlo-simulations over the possible boarder-configurations?
My thought is that one thing you could easily get from the rollouts
is a good estimate of the status of each string of stones currently
on the
The NNGS clone on boardspace.net is still running, but completely
idle. It would be a suitable place to test clients.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
I don't know, but from the description list of atoms, perhaps
numbers were represented as linked lists of bits (using the facilities
built in to support linked lists of anything).
I don't believe that any non-toy version of lisp ever used anything
as ineffecient as representing numbers as
My theory on pondering is that it's not very productive to
use it to just jump start the next global search.
In my conceptual model for a playing program, there are a lot
of facts that in fact are nothing of the kind - they're assertions
that you are willing to assume are true. I'm thinking of
I suggest that it would be more convenient for everyone
if various sizes of cgos all ran on the same server. If
you want to donate horsepower to the project, a good use
of the resource would be to run anchorman type clients.
___
computer-go mailing
At 03:12 PM 6/15/2007, steve uurtamo wrote:
my last $0.02 on this -- let me know when you've written a kernel in java, and
tell me how fast your operating system (written entirely in java) runs.
I could point out that lisp machines had no other language at the
core. The entire operating system
One of my favorite observations about Go is that expert play tends
to be on the edge of catastrophy.
By playing better moves on the average, you become more vulnerable
to the occasional misstep.
If a program is not very good, random better or worse moves do not have
much effect. If the
One of my favorite observations about Go is that expert play tends
to be on the edge of catastrophy.
By playing better moves on the average, you become more vulnerable
to the occasional misstep.
If a program is not very good, random better or worse moves do not have
much effect. If the
I think your table tennis analogy is not really applicable.
The rule changes in table tennis were presumably motivated
by the need to fix a real problem, and really changed the
game.
On the other hand, all the rules arguments in Go are really
only applicable to incredibly marginal, bordering
The only thing a computer can to is to model opponent's behavior, which may
deviate from the best play. What did I miss?
No, you didn't miss a thing. I look forward to meeting you
at a poker table, preferably with high stakes.
___
computer-go
How does this foul spamming programs? Does it prevent a spammer from
sending out a lot of email or just delay the receiving of it?
It doesn't delay per se, it rejects the incoming mail with a
try again later tag. The theory is that spambots which
act as their own mailers will not retry.
I built a similar database of 3x3 patterns found in professional games. The
results looked interesting, but I never found a way to use it in a way
that really contributed to the evaluation.
___
computer-go mailing list
computer-go@computer-go.org
Considering how monte carlo actually works, I think it's plausible
to argue that it works best where the distance to endgame is small.
For a 19x19 board, the playing speed may be only a factor of 4 worse,
but the effective learning speed for an opening position might be
exponentially worse. In
XML per se is not an improvement - it's just another way of wrapping
data in a parseable package. XML says nothing about the structure,
content, and semantics of the data. SGF does all that, it's very
Go-friendly, and there are already many tools that use it for Go.
However, I am in favor of changing the SGF format to allow coordinate encoding
using the standard coordinates system rather than the one created just for
SGF; i.e., a1 vs aa.
I routinely use sgf for non-go games and completely ignore the
standard set of tag names and contents. This works
At 04:03 PM 10/22/2007, Markus Enzenberger wrote:
On Mon October 22 2007 10:15, Don Dailey wrote:
almost impossible to write XML manually without bugs.
it also seems to be hard to write an SGF file without bugs.
I recently run a test on a collection of about 5000 SGF files
from various sources
the idea is: identify at least one stone from every unconditionally
living and every unconditionally dead group on the board, and
report them as dead or alive.
It can be done very fast, but the problem is that in a typical
endgame board under Japanese rules, the number of unconditionally
the idea is: identify at least one stone from every unconditionally
living and every unconditionally dead group on the board, and
report them as dead or alive.
It can be done very fast, but the problem is that in a typical
endgame board under Japanese rules, the number of unconditionally
At 05:22 PM 11/6/2007, Ray Tayek wrote:
At 03:50 PM 11/6/2007, you wrote:
... in a typical
endgame board under Japanese rules, the number of unconditionally
alive stones is zero.
maybe for pro games. for amatuer 1-kyu to 10-kyu games, i suspect that after
about 1/2 of the moves in the entire
At 05:22 PM 11/6/2007, Ray Tayek wrote:
At 03:50 PM 11/6/2007, you wrote:
... in a typical
endgame board under Japanese rules, the number of unconditionally
alive stones is zero.
maybe for pro games. for amatuer 1-kyu to 10-kyu games, i suspect that after
about 1/2 of the moves in the entire
Am I making *any* sense? If so, you may need some sort of psychiatric help,
or alternatively, you could do me the favor of explaining how to ask for what
I want or even how to actually get it. :)
Most computer applications use uniform randomness, but it sounds like
what you want is normally
It appears that the question of GC is not dependent on the problem
(eg. computer-Go) but on the language you use.
This really gets back to the core of the language question. The
kind of language you choose depends in part on the kind of program
you intend to write.
If you're writing a monte
I disagree with almost everything Donn wrote.
Thanks to Moore's law, it is somewhere between unusual and rare for
the execution speed penalty of the language to matter, and if it
matters today (some but not all languages are fast enough), it won't
matter when the program is finished.
Thought
Over the years I've had a dribble of requests for my collection
of scored games. The most recent request inspired me to stop
the water torture by just posting it for general use.
The collection contains 600 professional games with
an exact score, and machine-readable annotations for
which
A very minor nitpick: I notice that during the processing that you
appear to have removed all the RU properties[1], which are technically
mandatory and potentially useful.
These records were converted from other formats, and never had RU
properties.
I think that's somewhat contrived as well. I don't have that good idea
about all the populat computer go algorithsm, do you have example of
reasonably performing algorithm with these properties?
A standard alpha-beta driven search takes exponentially more time
with search depth, so an
At 02:30 PM 11/21/2007, Chris Fant wrote:
I found the shape library to be interesting. I never knew about that
before. It appears to be very old (stable since 1987, ...the poor
unfortunates who don't have a graphical interface). I was wondering
if you had any plans to build on this work and
Arguments about the quality of compiler optimizations vs. hand coding
are pointless, because programmers optimize programs in ways that compilers
are (correctly) forbidden to do; by changing the algorithm.
For example, if I happen to know x will always be an integer
from 0 to 359, I can
Not so - Microsoft's .NET framework has both networking and GUI support. The
Mono provides a Linux implementation. In fact, with Silverlight (and
Moonlight, for Mono), the .NET framework can be used within a modern web
browser (very similar to Java and Flash combined).
It remains to be seen
Not so - Microsoft's .NET framework has both networking and GUI support. The
Mono provides a Linux implementation. In fact, with Silverlight (and
Moonlight, for Mono), the .NET framework can be used within a modern web
browser (very similar to Java and Flash combined).
It remains to be seen
Do you believe GO is not NP
hard or that there is some intrinsic reason that a properly programmed
computer would not benefit from more resources?
You missed my point completely. As a programmer with finite
resources, especially time, if I spend a year squeezing extra
performance out of a
A standard alpha-beta driven search takes exponentially more time
with search depth, so an exponential increase in speed results in
a very small incremental improvement in seeing'. Improvements
in the quality of the evaluation at anything less than exponential
cost more effective at
Languages like SQL and Prolog don't specify algorithms, they describe
the desired result. I agree that the quality of compilers that turn these
specifications into algorithms can improve dramatically, and that
this kind of specification is a great way to increase the productivity
of programming
Languages like SQL and Prolog don't specify algorithms, they describe
the desired result. I agree that the quality of compilers that turn these
specifications into algorithms can improve dramatically, and that
this kind of specification is a great way to increase the productivity
of programming
... and I also found A Novel
Morphological Operator to Calculate Euler Number by Zhao Zhang, Randy
H. Moss and William V. Stoecker. Did you scan that article too?
That one is news to me.
___
computer-go mailing list
computer-go@computer-go.org
The problem with this is that below a few ply, the probabilities are
all effectively zero. All you're really doing is enshrining the
prior probabilities used to sort the first few levels.
In cases where the good moves are the obvious ones, you've found them
anyway. In other cases, you prune
The problem with this is that below a few ply, the probabilities are
all effectively zero. All you're really doing is enshrining the
prior probabilities used to sort the first few levels.
In cases where the good moves are the obvious ones, you've found them
anyway. In other cases, you prune
As any incomplete search, it can blunder, but why more than any other
incomplete search?
Not worse, just not a magic bullet.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
At 11:39 AM 12/6/2007, terry mcintyre wrote:
Any estimate of winning probability is only as good as the estimates of
whether particular games are actually won or lost.
I propose that monte carlo programs should produce a distribution of
quantitative outcomes rather than just a simple %win. It's
Here's a more likely scenario: Approaching endgame, there
are 10 resolved fights that remain to be played out. The
program estimates is won 5 of them and lost 5 of them,
each with 85% confidence. The sizes of the groups is
such that any single switch from won to lost will swing
the game. The
Arguing whether method A or method B rates a program more
correctly is really close to arguing how many angels can dance
on the head of a Pin. Ratings, at best, are based on mathematical
models with many simplifying assumptions. Ratings are not reality.
My program was written in lisp, so naturally I concur. I'm not
actively using lisp any more, but I will offer various dialects
of common lisp as the consensus choice of dialect.
My favorite implementation is lispworks. The personal edition is
free and ought to be adequate for research.
The
At 05:24 AM 12/12/2007, Don Dailey wrote:
I've looked into this a bit. My preference would be scheme and it's
my understanding that it may be a bit more efficient.
If you're worried about efficient use of the machine, stay away from lisp
and scheme. Despite the claims of it can be as fast as
At 05:24 AM 12/12/2007, Don Dailey wrote:
I've looked into this a bit. My preference would be scheme and it's
my understanding that it may be a bit more efficient.
If you're worried about efficient use of the machine, stay away from lisp
and scheme. Despite the claims of it can be as fast as
These are true, but not the underlying problem.
The biggest underlying reason is the multiple constraints on
memory management;
a) since the data is typed rather than the pointers, every chunk of memory
has to be self identifying, not just for the garbage collector, but also so
(plus a
My tsumego applet determines without a search that black can kill,
and white might live if he moves first.
http://www.andromeda.com/people/ddyer/go/shape/ShapeApplet.html
A table lookup is a little better than searching 162438 nodes :)
For example current version(not released) goes trought
The standard one is Benson's algorithm
http://senseis.xmp.net/?BensonsAlgorithmhttp://senseis.xmp.net/?BensonsAlgorithm
The standard caveat is that this algorithm alone is very weak - it
typically applies to zero stones on a position played out using
Japanese rules. But you have to start
The standard one is Benson's algorithm
http://senseis.xmp.net/?BensonsAlgorithmhttp://senseis.xmp.net/?BensonsAlgorithm
The standard caveat is that this algorithm alone is very weak - it
typically applies to zero stones on a position played out using
Japanese rules. But you have to start
There's a sort of hierarchy of life-and-death methods, for which
Benson's algorithm is the base.
My status database is next above that, but it is actually a lookup table
based on a problem solver, such as Wolfs or mine. The unique thing
about the database is that it could be dropped in to a
CGOS uses Chinese scoring with play-outs so that we can get fully
automated scoring with no chance of errors.
No chance of errors is vacuously true. Errors, if any, were made
in the playout leading to the final state. There can be score
differences compared to what would have been Japanese
It's interesting to look at a graphic plot of a traceroute
to see there the actual delays are. I use a program called
pingplotter for this, but there are many such programs.
Be warned though, that seeing a potential problem only leaves you
feeling helpless, since there is typically nothing you
At 11:44 AM 1/31/2008, David Doshay wrote:
That is correct.
It is my understanding that the Intel machines can compile to
a universal binary that will run on the G5 machines, but we
have not verified that. I trust that it works, but have no idea
if there is an efficiency hit.
Universal binaries
At 11:44 AM 1/31/2008, David Doshay wrote:
That is correct.
It is my understanding that the Intel machines can compile to
a universal binary that will run on the G5 machines, but we
have not verified that. I trust that it works, but have no idea
if there is an efficiency hit.
Universal binaries
To a first order approximation, would changing the komi change the
rankings? Presumably, programs are playing the same number of games
as black and white, so any unfair advantage or disadvantage black
has would balance out.
Komi only matters when there is only one game between a pair of
By the way, has anyone seen the Philip Morris commercials?
I believe they were forced into this as part of the extortion
by the state attorneys general. It's Penance for illegally
targeting young non-smokers with Joe Camel, and promoting their
products while denying that they were
The thing that really kills multiple platform programs are GUIs.
Unless your GUI is born expecting to be cross platform, you're
pretty much screwed.
___
computer-go mailing list
computer-go@computer-go.org
Of course C can be more or less platform independent if you take some care.
Purely for engine code, that's true. Standard windows has APIs
that are nearly compatible with xxux for command line initialization
and ordinary file and network operations.
If your program has ANY gui at all
1) Does anybody know of a good Java SGF parser out there?
I have one I've used for many types of games, including Go. I've used
it to represent large collections with no problems.
___
computer-go mailing list
computer-go@computer-go.org
1) Does anybody know of a good Java SGF parser out there?
I have one I've used for many types of games, including Go. I've used
it to represent large collections with no problems.
___
computer-go mailing list
computer-go@computer-go.org
I watched all the games, and I must say, mogo performed really badly
at the blitz games, and quite a bit better at the 1-hour game. I'd still
take any claims of dan level play with lots of salt.
My take-away from watching the match is that blitz performance wasn't
at all representative. A
I'm really very weak on networking so I'm not sure what I'm actually
reading or whether this fix needs to be applied on the server end or the
client end. Any ideas is this is relevant?
You also have the same problem, but with much less real information,
if the client end end of the connection
I'm really very weak on networking so I'm not sure what I'm actually
reading or whether this fix needs to be applied on the server end or the
client end. Any ideas is this is relevant?
You also have the same problem, but with much less real information,
if the client end end of the connection
I think the result
computer in hopelessly lost position resigns.
is much more satisfactory than
computer in hopelessly lost position wins by playing 100
additional pointless moves
I think a human who used this tactic in a tournament situation
might win the trophy, but would be unable to
I think the result
computer in hopelessly lost position resigns.
is much more satisfactory than
computer in hopelessly lost position wins by playing 100
additional pointless moves
I think a human who used this tactic in a tournament situation
might win the trophy, but would be unable to
This was typically to pick up my queen, change its colour, and
capture my rook with it.
Now there's a feature that would make a tournament interesting...
If this appeals to you, try Martian Chess or Shogi
___
computer-go mailing list
Japanese: bad.
I don't think this is the case at all. The Japanese rules
are just a human optimization, to avoid having to make the
last 100 meaningless moves, and still arrive at the correct
score with a minimum of extraneous manipulation.
The tortured details, while not elegant, rarely
The formalized rules are the tortured details I referred to. I've
played thousands of games of Go, and I've never even seen any of those
versions of the rules.
The Japanese rules I refer to are the informal procedures I use every
time I play, both to estimate the score during the game, and at
I suggest you add an identical RNG for testing purposes, which you
will know is identical in both implementations even if it is not
ideal. Run a test with a seeded random sequence which should
provide identical playouts.
___
computer-go mailing list
For those of you who use windows, I highly recommend tortoise cvs
and tortoise svn, which map access to whichever repository you prefer
into an incredibly useful and intuitive interface piggybacked on windows
explorer.
___
computer-go mailing list
For those of you who use windows, I highly recommend tortoise cvs
and tortoise svn, which map access to whichever repository you prefer
into an incredibly useful and intuitive interface piggybacked on windows
explorer.
___
computer-go mailing list
I think the question is largely meaningless, because few games have
been studied by humans (or human computer programmers) with the depth
and intensity that has been achieved for games like chess and go.
In general, games with many choices and no obvious strategies
are good for people and bad
Here's a chance to share an amusing and illustrative anecdote.
I was working on optimizing Goodbot, a program that plays Tantrix,
and because of the nature of the game, the only way to really qualify
an improvement is to run many test games against a standard opponent.
At one point, I was
Here's a chance to share an amusing and illustrative anecdote.
I was working on optimizing Goodbot, a program that plays Tantrix,
and because of the nature of the game, the only way to really qualify
an improvement is to run many test games against a standard opponent.
At one point, I was
That's impressive, especially considering the fairly long search path between
Go and igowin.
It happens. One day recently I was idling at boardspace.net, when
in the course a few minutes the site was overrun by about 30 guests,
all speaking German and wanting to play Hex. It turned out that
At 01:31 PM 11/26/2008, Denis fidaali wrote:
Speaking of hex ... I really think it would be a nice intermediary game before
tackling the complexity of go. Do you know of any good community (and protocol
equivalent to GTP) where i could start to look for submitting a bot ?
There are a couple of
At 01:52 AM 11/27/2008, Denis fidaali wrote:
...
But what really lacks (or i wasn't able to find anyway) is a strong community
like there is for go.
A CGOS equivalent.
A GTP equivalent.
A Gogui equivalent.
A Kgs equivalent.
I don't think there's a match between your goals and what
Permit me to play the skeptic here; I think you're going about it absolutely
backwards - unless you already have a strong algorithm which depends on 128 bit
rotations, and only lack an efficient hardware engine to run it on.
If your idea of fun is to really feel the bits squishing between your
I think general hardware limits are good, because they will permit
more teams to be competitive without altering the nature of the
competition.
___
computer-go mailing list
computer-go@computer-go.org
Lets look at it another way - no one would care what hardware
you choose to use, unless you win. So at the very least, you
ought to be able to use arbitrary hardware until it becomes
established that only that class of hardware can win.
___
There's already a havannah section on this game programming
forum: http://www.grappa.univ-lille3.fr/
-- which could use an influx of traffic.
___
computer-go mailing list
computer-go@computer-go.org
My theory is that the organizers of tournaments with remote participants
could appoint official observers, to observe the operators at the remote
end of connections. Not foolproof, but simple and doesn't interfere with
the conduct of the tournament.
At 12:59 AM 2/4/2009, David Fotland wrote:
What do you mean by operator at remote end? In my case, the program was
running on a cluster at Microsoft in some computer data center. There was
no operator at Microsoft. The cluster was operated from Beijing through a
remote desktop. The operator
While your goal is laudable, I'm afraid there is no such thing
as a simple tree search with a plug-in evaluator for Go. The
problem is that the move generator has to be very disciplined,
and the evaluator typically requires elaborate and expensive to
maintain data structures. It all tends to be
Do you mean that the evaluator might be used during move ordering somehow
and that generating the nodes to expand is tightly coupled with the static
evaluator?
That's the general idea.
No search program can afford to use a fan-out factor of 361. The information
about what to cut has to come
Do you mean that the evaluator might be used during move ordering somehow
and that generating the nodes to expand is tightly coupled with the static
evaluator?
That's the general idea.
No search program can afford to use a fan-out factor of 361. The information
about what to cut has to come
This is old and incomplete, but still is a starting point you might
find useful http://www.andromeda.com/people/ddyer/go/global-eval.html
General observations (from a weak player's point of view):
Go is played on a knife edge between life and death. The only evaluator
that matters is is
Donn, your email at d...@mit.edu is bouncing.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Highly recommended
http://www.youtube.com/watch?v=EjrvrH1bKIwfeature=PlayListp=2C02F6B33145E762index=0playnext=1Mathematics
and Go by Elwyn Berlekamp
___
computer-go mailing list
computer-go@computer-go.org
Storing an opening book for the first 10 moves requires
331477745148242200 nodes. Even with some reduction for symmetry,
I don't see that much memory becoming available anytime soon, and you still
have to evaluate them somehow.
Actually storing a tree, except for extremely limited
At 02:13 PM 5/12/2009, Michael Williams wrote:
Where does your 99% figure come from?
1/361 1%
by endgame there are still easily 100 empty spaces
on the board.
___
computer-go mailing list
computer-go@computer-go.org
At 02:13 PM 5/12/2009, Michael Williams wrote:
Where does your 99% figure come from?
1/361 1%
by endgame there are still easily 100 empty spaces
on the board.
___
computer-go mailing list
computer-go@computer-go.org
An essential feature of monte carlo is that it's search space is
random and extremely sparse, so consequently opportunity to re-use
nodes is also extremely sparse.
On the other hand, if the search close to the root is not sparse, my
previous arguments about the number of nodes and the number of
I assume Dave Dyer does not understand alpha beta pruning either, or he would
not assume the branching factor is 361.
The branch at the root is about (361-move number) - you have to consider
all top level moves. A/B only kicks in by lowering the average branching
factor at lower levels
1 - 100 of 149 matches
Mail list logo