Re: [Computer-go] Paper “Complexity of Go” by Robson

[John Tromp]

 at the bottom of my Go page http://tromp.github.io/go.html, which also
 contains an sgf link.
 Direct link to image: http://tromp.github.io/img/WO5lives.png

Enlarging the board to 29x29 allows for a much better final (I hope)
look, close to my first attempt.

-John
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Paper “Complexity of Go” by Robson

[John Tromp]

> The hunt for the simplest possible ko gadget continues...

Latest attempt at the usual place:

>>> at the bottom of my Go page http://tromp.github.io/go.html, which also
>>> contains an sgf link.
>>> Direct link to image: http://tromp.github.io/img/WO5lives.png

Unfortunately not as pretty as the previous arrow.
But let's get it correct before getting it pretty...
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Paper “Complexity of Go” by Robson

[John Tromp]

> Hopefully fixed now.

Nope. Still no good. White can play O13, M11, or Q11 instead of recapturing ko.

The hunt for the simplest possible ko gadget continues...
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Paper “Complexity of Go” by Robson

[John Tromp]

>>> Direct link to image: http://tromp.github.io/img/WO5lives.png

Might be useful for go event organizers in need of arrow signs...

regards,
-John
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Paper “Complexity of Go” by Robson

[John Tromp]

>> I have attempted to reduce this y || (x && z) problem to the minimum
>> number of stones
>> at the bottom of my Go page http://tromp.github.io/go.html, which also
>> contains an sgf link.
>> Direct link to image: http://tromp.github.io/img/WO5lives.png
>
> Unfortunately, my ko gadgets don't work properly.
> Black can connect 2 of her stones (eg. at P12) to break the ko for White.
> Back to the drawing board...

Hopefully fixed now. Please let me know if you find any problems with
the optimizations...

regards,
-John
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Paper “Complexity of Go” by Robson

[John Tromp]

> I have attempted to reduce this y || (x && z) problem to the minimum
> number of stones
> at the bottom of my Go page http://tromp.github.io/go.html, which also
> contains an sgf link.
> Direct link to image: http://tromp.github.io/img/WO5lives.png

Unfortunately, my ko gadgets don't work properly.
Black can connect 2 of her stones (eg. at P12) to break the ko for White.
Back to the drawing board...

regards,
-John
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Paper “Complexity of Go” by Robson

[John Tromp]

> If we call the three kos x,y,z from top to bottom, then a succesfull
> White ladder amounts to
> (x || y) && (y || z). Which is equivalent to y || (x && z).
> So with y currently false, and White unable to flip it, White should
> take the bottom ko to make z true.
> Black can the make x false, but that allows White to make y true,
> after which she can successfully escape
> in a ladder.

I have attempted to reduce this y || (x && z) problem to the minimum
number of stones
at the bottom of my Go page http://tromp.github.io/go.html, which also
contains an sgf link.
Direct link to image: http://tromp.github.io/img/WO5lives.png

regards,
-John
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Paper “Complexity of Go” by Robson

[John Tromp]

On Tue, Jun 19, 2018 at 3:55 PM, Marcel Crasmaru  wrote:
> "what is the computational difficulty of Capture GO?" then as far as I know
> no one proved anything yet. Capture GO might be in P but to prove this
> doesn't look like an easy task. I personally think it is either
>
> (1) in P but very hard to prove it, or
> (2) at least NP hard because, empirically, you may still create few
> convoluted ladders that don't capture stones and interact to each
> other in unexpected ways etc. Using loose ladders might be a another
> way to try building NP hard instances. However, without a proof this
> assumption is still as valid as (1).
>
> I am curious what's John Tromp opinion on the above.

I spent some time thinking about the loss-less-ladder problem, that
asks if Black can capture
a given white group in a ladder without losing any stones herself.
I've come to suspect that this is an instance of (1), and that it
might be easier to prove than
the general capture go problem of which it is a special case.

regards,
-John
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Paper “Complexity of Go” by Robson

[John Tromp]

On Tue, Jun 19, 2018 at 12:03 PM, Marcel Crasmaru  wrote:
>> White can start one ladder as a ko threat to take back the middle ko, and 
>> black will then take the top ko.

> I claim that White cannot  use the ladders as a ko thread because:
> - if W plays R4 as a ko threat then B responds with S4
> - if next W takes a ko back on the board then B kills the group
> locally by playing S6: the left ladder is no longer a ladder and if W
> gets out of the right ladder then the bottom W group ends in 2
> liberties and B can capture it
>
> Is the above reasoning sound?

Thanks for correcting me. You're right White can't use the ladders as
ko threats.

I also seem to have confused the formula expressed by the choice gadgets.
If we call the three kos x,y,z from top to bottom, then a succesfull
White ladder amounts to
(x || y) && (y || z). Which is equivalent to y || (x && z).
So with y currently false, and White unable to flip it, White should
take the bottom ko to make z true.
Black can the make x false, but that allows White to make y true,
after which she can successfully escape
in a ladder.

regards,
-John
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Paper “Complexity of Go” by Robson

[John Tromp]

On Tue, Jun 19, 2018 at 3:52 AM, Marcel Crasmaru  wrote:
> I've eventually managed to create a problem that should show a full
> reduction from a Robson problem to Go - I hope is correct.
>
> The Problem: 
> https://drive.google.com/file/d/1tmClDIs-baXUqRC7fQ2iKzMRXoQuGmz2/view?usp=sharing
> Black just captured in the marked ko. How should White play to save
> the lower group?

It looks like White needs to hold the middle ko and either top or
bottom ko to make the ladders work.
White can start one ladder as a ko threat to take back the middle ko,
and black will then take the top ko.
Now if white (possibly using another ladder ko threat) takes back
either top or bottom ko, Black can retake
the middle one and White has made no progress. So it looks like White
is doomed?!

regards,
-John
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Paper “Complexity of Go” by Robson

[John Tromp]

On Mon, Jun 18, 2018 at 10:24 PM, Álvaro Begué  wrote:
> I don't think ko fights have anything to do with this. John Tromp told
> me that ladders are PSPACE complete: https://tromp.github.io/lad.ps

Ko fights are needed to take Go problems beyond PSPACE.
For Japanese rules they suffice to go beyond (assuming EXPTIME != PSPACE),
but for Chinese rules it's an open problem.

regards,
-John
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Paper “Complexity of Go” by Robson

[John Tromp]

On Mon, Jun 18, 2018 at 10:30 PM, Marcel Crasmaru  wrote:
>> FWIW, first-capture go (i.e. winner is first one to make a capture) should 
>> not be PSPACE-complete.
>
> Actually this is not obvious.
>
> If you are able to replace the White Choice gadget shown at page V in
> this paper: https://tromp.github.io/lad.ps with an equivalent Go
> gadget that doesn't capture any stone

In a ladder White is reduced to 1 liberty at every Black move, so the
only way to give White a choice is to provide an alternative to
playing that single liberty; which is necessarily a capture.

regards,
-John
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Number of Go positions is itself a Go position

[John Tromp]

dear David,

> To quote from: http://tromp.github.io/go/legal.html
>
> It should come as no surprise that L19, viewed as a position, is itself
> illegal.
>
> In this absolute form this statement got disproved in my German Go Forum
> article at
> http://www.dgob.de/yabbse/index.php?topic=5935.msg216064#msg216064

My form is not as absolute as you make it out to be. The absolute form would be:

It should come as no surprise that L19, mapped to a position by laying
out the 361 consecutive
trits to a path on the 19x19 grid, and choosing which trit represents
empty, is itself illegal.

That would indeed be a ridiculous claim:-)

> Basically it's using a more natural Hilbert-based curve instead of an
> arbitrary row-wise mapping which doesn't take the topology of the Go-grid
> into account. Let me now if you need any of the details in German
> translated.

The fact that you can describe my mapping simply as "row-wise" shows how it
is quite non-arbitrary. Your Hilbert curve on the contrary can hardly
be described
in a much simpler way than in its full explicit form, betraying its
arbitrariness...

Trotzdem, gratuliere zu deinem legale Kurve!

kind regards,
-John
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Zero performance

[John Tromp]

> You can also start with 9x9 go. That way games are shorter, and you probably
> don't need 1600 network evaluations per move to do well.

Bonus points if you can have it play on goquest where many
of us can enjoy watching its progress, or even challenge it...

regards,
-John
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Alphago and solving Go

[John Tromp]

> Shouldnt that number at most be 722^#positions? Since adding a black or a
> white stone is something fundamentally different?

The upper bound of 361^L(19,19) games is from Theorem 7 on page 31 of
http://tromp.github.io/go/gostate.pdf, where you will find a proof.
As the paragraph preceding that theorem explains, the difference from your
suggestion is due to the average position having only 361/3 empty points
available for play.

-John
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Alphago and solving Go

[John Tromp]

> And what is the connection between the number of "positions" and the number
> of games

The number of games is at most 361^#positions.

> or even solving games? In the game trees we do not care about
> positions, but about situations.

We care about lots of things, including intersections, stones,
liberties, strings, positions, sets of previous positions.

> I'm actually surprised that this "absurd" to you...

I said that referring to a board configuration together with the set
of all previously occurring board configurations (and turn to move) as
"position" is absurd.
We need a simple word to denote a board configuration, and "position" fits
that requirement. A good word for all the relevant historical
information leading up to a position is "situation".

-John
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Alphago and solving Go

[John Tromp]

> Under which ruleset is the 3^(n*n) a trivial upper bound for the number of
> legal positions?

Under all rulesets.

> Unless we talk about simply the visual aspect

Yes, we do.

> but then this has
> absolutely nothing to do with the discussion abour solving games.

If you want the notion of "position" to encode everything needed to
determine legality of future plays, then in the case of superko, you
need the entire set of previous board configurations, which to me is
rather absurd.
Instead you should call that "situation".
That's how we distinguish the two flavors of superko;
positional vs situational...

regards,
-John
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] It is official.We will see more of Alphago!

[John Tromp]

hi Ingo,

>> “Pair Go” — A game where one Chinese pro will play
>> against another...except they will both have their own
>> AlphaGo teammate, alternating moves, to take the concept
>> of ‘learning together’ quite literally.
>
> Will the pro players in these games see the evaluations
> of AlphaGo?  And also the principal line(s) ?

That would defeat the purpose of Pair Go,
which is all about having to second-guess your partners intentions.

> *
> In Jena we did preliminary exeriments on this setting
> two or three years ago, with Crazy Stone being the bot.
>
> One insights: Assume A = AlphaGo, B = human_1, C = human_2
> where B is two stones stronger than C.
>
> This does not necessarily mean that team A+B will be
> stronger than A+C.

In this setup we should have A+B <= A and A+C <= A.
Perhaps player C is modest enough not to interfere with A's choices,
so that A+B <= A = A+C
:-)

regards,
-John
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Zen lost to Mi Yu Ting

[John Tromp]

>> (Japanese rules are not *that* hard. IIRC, Many Faces, and all other
>> programs, including my own, scored in them
>
> There is a huge difference between doing some variation of territory
> scoring and implementing Japanese rules. Understanding this difference
> will get you some way to understanding why some people do not like them,
> and that has got nothing to do with computer go.

I do not like them because, as far as i can tell, they cannot answer
questions like: what is fair komi for 2x2 Go (i.e. what is the outcome
with perfect play) ?

regards,
-John
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Training the value network (a possibly more efficient approach)

[John Tromp]

hi Bo,

> Let me know if there is any silly mistakes :)

You say "the perfect policy network can be
derived from the perfect value network (the best next move is the move
that maximises the value for the player, if the value function is
perfect), but not vice versa.", but a perfect policy for both players
can be used to generate a perfect playout which yields the perfect
value...

regards,
-John
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] longest 3x3 game

[John Tromp]

dear Go researchers,

>> > Found a 582 move 3x3 game...
>> Can you give us sgf?
>
> I took the effort of trying to format the 582 game in a more insightful way.
> I ended up with lines of positions that mostly add stones, only starting
> a new line when a capture of more than 1 stone left at most 4 stones:
> The result is attached. I think there is clearly
> room for improvement, i.e. make this game much longer.

Gunnar Farnebäck took up my challenge and took a giant leap from 582
to 1808 moves, using a UCT oriented search with maximum playout length
as the score.

That led me to implement a so-called beam search,
in which we keep a set of W (the beam width) games at the same depth
D, and for each one, play some number B (branching factor) of random
playouts.
We then keep the W longest of these W*B playouts, truncated at depth D+1,
and repeat the process, until no more playouts are possible (all moves
being superko violations).

I ran a dozen beam searches with W=16384 and B=1024, and the best one
reached a record 2900 moves. See the attached sgf.

It's quite mesmerizing to load this sgf in your favorite go editor and just
cycle through all the moves at a rapid pace...

The rules should really be TT (Tromp/Taylor) instead of NZ (New Zealand),
but unfortunately Cgoban doesn't support TT.

regards,
-John


2900.sgf
Description: application/go-sgf
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Congratulations to Zen!

[John Tromp]

dear Aja,

> AlphaGo is getting stronger and stronger. I hope you all will enjoy watching
> the games.

Could you tell us if Alpha Go is able to come up with that most famous of moves:

http://senseis.xmp.net/?EarReddeningMove

Or is it so strong that it found an even better move:-?

regards,
-John

PS: looks like the games are played in the middle of the night for us
on the US east coast:-(
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] longest 3x3 game

[John Tromp]

dear Ingo,

>>> ... (1 + delta)^(m*n).
>>
>> This is true, and a delta > 2 follows from a Theorem in an
>> upcoming paper by Matthieu Walraet and myself.
>
> Do you mean (1+delta) > 2, or really (1+delta) > 3?

Oops; I mean delta >= 1, so the base of the exponent is at least 2.

(1+delta) is necessarily bounded by the base of liberties of 2.975734192...

> Please let us know when a preprint is available on ArXiv or some other place.

The original write-up by Matthieu is available at
http://matthieuw.github.io/go-games-number/GoGamesNumber.pdf

Our CG2016 submission both simplifies and improves on that,
but that write-up should already convince you of how to achieve delta 1.

regards,
-John
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Frisbee Go

[John Tromp]

dear Nick,

> There's an assumption implicitly made here, which does not accord with my
> experience of frisbee Go: that the player will always aim at an
> intersection.
>
> Suppose I want to play on either of two adjacent points, and I don't care
> which. If I aim for one of them, I will land on one of them with probability
> (3p+1)/4, or whatever the formula says. I feel that I ought to be able to do
> better by aiming midway between them.

But then why stop there? You may also want to aim in between 4 points.
Or perhaps just epsilon more toward the right of there.

There's no accounting for all possibilities of real life frisbee Go,
so we settle for the simplest rule that captures the esssence...

regards,
-John
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] longest 3x3 game

[John Tromp]

dear Darren, Ingo,

> Again by random sampling?

Yes, nothing fancy.

> Are there certain moves(*) that bring games to an end earlier, or
> certain moves(*) that make games go on longer? Would weighting them
> appropriately in your random playouts help?

You could try to weigh moves by how likely they lead to revisiting previous
positions. I think that's the only thing that makes moves worse.


> very interesting. Is it allowed for players
> to pass in between? Do these passes count like
> normal moves?

Yes, passes are implied whenever two consecutively played stones
are of the same color.

> > Found a 582 move 3x3 game...
> Can you give us sgf?

I took the effort of trying to format the 582 game in a more insightful way.
I ended up with lines of positions that mostly add stones, only starting
a new line when a capture of more than 1 stone left at most 4 stones:
The result is attached. I think there is clearly
room for improvement, i.e. make this game much longer.

> My intuition says that there should be a constant
> delta > 0 such that for all board sizes m x n (with
> m > 1, n > 1) there exist games of length
> at least (1 + delta)^(m*n).

This is true, and a delta > 2 follows from a Theorem in an
upcoming paper by Matthieu Walraet and myself.

> And also for m x 1 boards (so, only one "long" streak)
> there should exist games with length above
> (1 + delta)^m (they might be constructed by doing some
> pseudo-counting, starting at one end of the board).

We already have a lower bound of 2^{n+1}-4
as Theorem 9 in our combinatorics paper.

> Might neural nets help to find (very) long games
> for given board size?

Neural nets are not the best way to deal with avoiding superko:-(

regards,
-John


attach.582
Description: Binary data
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Frisbee Go

[John Tromp]

I don't remember if there was consensus, but can repeat my previous thoughts:

> 1. What happens with plays unintentionally on top of stones or out of
> bounds?

Converted to involuntary pass.
Note that a throw must have some positive probability of converting into
a legal move. This way, infinitely long games have 0 probability.

> 1.1 If converted to passes, do they count towards end of play and
> scoring phase?

No; only voluntary passes should. Otherwise games would most
likely end prematurely.

> 2. How are the play probabilities distributed?

They're governed by a single parameter, the hit probability p.
You hit the target with prob. p, and its 4 neighbours with probability (1-p)/4.

I don't believe there's a single value of p that everyone likes best.

One extreme p=1 is classical Go. The other extreme p=0 is guaranteed
to miss the target. Other natural choices are p=1/2 or p=1/5.
(Values in 1/2 < p < 1 seem a little dull to me).

regards,
-John
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] longest 3x3 game

[John Tromp]

> The longest I've been able to find, by more or less random sampling,
> is only 521 moves,

Found a 582 move 3x3 game...

regards,
-John
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Mastering the Game of Go with Deep Neural Networks and Tree Search

[John Tromp]

On Wed, Jan 27, 2016 at 1:46 PM, Aja Huang  wrote:
> We are very excited to announce that our Go program, AlphaGo, has beaten a
> professional player for the first time. AlphaGo beat the European champion
> Fan Hui by 5 games to 0.

It's interesting to go back nearly a decade and read this 2007 article:

http://spectrum.ieee.org/computing/software/cracking-go

where Feng-Hsiung Hsu, Deep Blue's lead developer, made this prediction:

"Nevertheless, I believe that a world-champion-level Go machine can be
built within 10 years"

Which now appears to be spot on. March 9 cannot come soon enough...
The remainder of his prediction rings less true though:

", based on the same method of intensive analysis—brute force,
basically—that Deep Blue employed for chess".

regards,
-John
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Mastering the Game of Go with Deep Neural Networks and Tree Search

[John Tromp]

For those of you who missed it, chess grandmaster Hikaru Nakamura,
rated 2787, recently played a match against the world's top chess program
Komodo, rated 3368. Each of the 4 games used a different kind of handicap:

Pawn and Move Odds
Pawn Odds
Exchange Odds
4-Move Odds

As you can see, handicaps in chess are no easy matter:-(
When AlphaGo surpasses the top human professionals we may see such
handicap challenges in the future. One may wonder if we'll ever see a
computer giving 4 handicap to a professional...

So how did Nakamura fare? See for yourself at

https://www.chess.com/news/komodo-beats-nakamura-in-final-battle-1331

regards,
-John
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Computer-go Digest, Vol 72, Issue 41

[John Tromp]

> You must be kidding about Lee Sedol.
> ...
> So he was by far the biggest fish Google could ever catch for that
> game, for Go insiders as well as for people outside the Go scene.

Well said, Marc.

In terms of name recognition and domination in the past decade,
who else but Lee Sedol should be picked as the "Kasparov of Go"
in the ultimate Man vs Machine match?

-John
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] AlphaGo and the Standard Mistake in Research and Journalism

[John Tromp]

dear Robert,

> The number G19 of legal games under a given go ruleset is unknown.

It will never be known since there's not enough space in the known
universe to write it down. We're talking about a number with over
10^100 digits.

> For positional
> superko (prohibition of recreation of the same position after
> completion of a move on the board), no passes, and no resignation, the
> number of possible games is smaller than N^P19

The no-pass restriction makes this rather uninteresting.
But actually, the same bound applies to games with passes,
stated as Theorem 7 in our paper.

Besides this upper bound, I can think of only two other numbers
that are well defined and interesting, namely

1) the size of the smallest search tree that proves the perfect komi.
and
2) same but for a full-width tree

These are called the decision complexity and game tree complexity on
https://en.wikipedia.org/wiki/Game_complexity#Decision_complexity

It is reasonable to expect the perfect komi does not depend on games
of more than 361 moves. Even with some ko fights, the ko recaptures
are likely bounded by the number of unplayed points.
The branching factor will be high though; let's put it at at most 200
on (geometric) average.

Then we estimate the decision complexity to be upper bounded by
200^181 and the game tree complexity by 200^361.

regards,
-John
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Game Over

[John Tromp]

I foresee a future where we watch Google vs Facebook matches with
human professionals providing commentary on their superiors :-)

Interesting times we live in!

-John
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Facebook Go

[John Tromp]

> A member of the German forum said, that a French Go player reported on
> Facebook, that Fan Hui lost 5 out of 5 games to the Google Go engine.

To ask the obvious:

Were these even or handicap games?

-John
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Number of Go positions computed at last (John Tromp)

[John Tromp]

dear Mark,

> Well, although Dr. Tromp seems rather modest about this result, I haven't
> heard of anyone else doing similarly interesting work on the theoretical
> foundations of the game.

There is a lot of other interesting research beyond counting things.
Just to name a few there's rule explorations, where Robert Jasiek
has done a lot of work, and the theory of evaluating Go positions,
endgames, kos, etc. in the setting of Combinatorial Game Theory,
where Elwyn Berlekamp is a name that comes to mind. Apologies for
leaving out countless others who have made valuable contributions.

> 1. So, as you go up the chart, what is the percentage of all possible
> positions that are legal?

The asymptotics of legal positions is derived in our paper (under some
conjecture) as

L(m,n) ~ 0.850639925845714538 * 0.96553505933837387^{m+n} *
2.97573419204335724938^{m*n}

So the legal probability grows as that divided by 3^{m*n}, or

Prob_legal(m,n) ~ 0.850639925845714538 * 0.96553505933837387^{m+n}
*0.99191139734778574979 ^{m*n}

> And isn't that an interesting sequence?  Perhaps more intuitively useful
> to a go-programmer  than the raw numbers themselves?

No; to a programmer that much precision is not interesting.
And to those for whom a lot of precision is interesting, the exact number
of legal positions is more natural than the probability.

>  Does this set of ratios make any
> intuitive sense to you
> ... or should I rephrase that as -- can you rationalize these results of
> the ratios?

Yes, the constant 2.97573419204335724938 is the effective freedom
per point under the legality constraint. That's why we call it the
"base of liberties".

> 2. One of the most frustrating things about writing a program to play go is
> that the rules are
> a bit blurry.  Far too blurry to really satisfy a computer programmer.
> I think some of the
> work you've done over the years is in creating a rigorous and computable
> set of rules.
> Is this correct, or have I heard wrong on this count?  Do you have a set
> of rules that
> could be profitably used for the basis of a go-playing program, that you
> like today?
> Is there a link to such a rule set somewhere?

Obviously I'm inclined to direct you to my personal Go page at

http://tromp.github.io/go.html

which states the Logical rules that I developed with Bill Taylor.

regards,
-John
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Number of Go positions computed at last

[John Tromp]

Wow, Robert, so many questions!
Many of which I have no idea how to answer:-(

> You must have needed 15 or 20 years of research to find the result?

Very intermittently though. If it were all continuous, it may be
several months of Go research, several more months of article editing,
and a few years of software development. Also don't forget the
contributions of my collaborators, mainly Gunnar and Michal.

> Eventually you heavily rely on computational power. How has it been possible
> to get hold of the computers and computation time?

Keep spreading the word; and keep begging. Eventually, people with the
resources and an interest in the outcome will come forward. Like Piet
Hutin my case. Publication of the 18x18 result led to more offers.

> When described in
> informal words, how have you attacked and proceeded with the theory of the
> problem? What can other researchers learn from your experience of how to
> research well? The number of legal positions itself seems like a piece of
> trivia (is it?) but why do you think it is important to have determined the
> number, that is, what is the research benefit? If I may ask, what has been
> your motivation beyond curiosity? You mention the calculation to be a server
> benchmark. Have there been other equally or more suitable server benchmarks
> or is this particular problem ground-breaking as a server benchmark?

Oh boy. Let me pass on these for now.

> What do the solution and its theory tell go players for tactics and strategy
> and go programmers for developing better go playing programs?

Zip. Nada. Nilch. :-(

> Does the solution give a useful clue of how difficult it is to solve go as a
> game weakly or strongly?

No clue, literally:-)

> That is, how is the number of legal positions
> related to the computational complexity in time and space of solving the
> 19x19 go game (under a given go ruleset) if viewed as the specific 19x19
> problem and not as the context of the general nxn problem's class of
> computational complexity?

As Douglas Adams would say,
almost, but not quite, entirely unrelated:-)

regards,
-John
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Number of Go positions computed at last

[John Tromp]

> shows how these 57 positions form 13 equivalence classes with respect
> to mirroring/reflection which further reduces to 7 classes when
> considering color symmetry as well.

Correction: that should be 8 (not 7) classes for all symmetries.

-John
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Number of Go positions computed at last

[John Tromp]

dear Erik,

> I was wondering if there is an efficient way to find the number of unique
> positions with symmetrical positions excluded.

It's roughly L19/16.
That's slightly short, but will be correct in the first 85 or so digits.

You just need to correct for the positions with rotational and/or
reflective symmetry. Counting those exactly requires a big ugly
modification of my program that will take about the same running time,
but will just be painful
to develop. So I'll pass on that:-)

-John
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

[Computer-go] Number of Go positions computed at last

[John Tromp]

It's been a long journey, and now it's finally complete!

http://tromp.github.io/go/legal.html

has all the juicy details...

regards,
-John
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Theoretical question

[John Tromp]

Our paper "Combinatorics of Go" has some results on this,
in a rule system allowing suicide.
See http://tromp.github.io/go/gostate.pdf,
in particular Section 7 on Hamiltonian games.

-John


On Thu, Nov 19, 2015 at 10:13 AM, Marc Landgraf  wrote:
> Hi,
> there is a question that lately crossed my mind. Considering an nxn Go
> board, no suicide allowed and with a rule that does not allow repetition of
> a position, unless caused by a single pass:
> What is the maximum number of board positions that can be run through in a
> single sequence starting from an empty board?
> Different wording: What is the maximum game length if not counting passes?
>
> It can easily be proven that for n>=3 this number must be lower than the
> number of legal positions. I didn't check for n=2, simple bruteforce would
> probably solve that.
>
> What happens to the ratio between the number of legal positions and the
> longest possible sequence with growing n?
>
> Is this already known? Or does anyone have a clue how to figure it out?
>
>  ~Marc
>
>
>
> ___
> Computer-go mailing list
> Computer-go@computer-go.org
> http://computer-go.org/mailman/listinfo/computer-go
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Frisbee Go Simulation

[John Tromp]

On Thu, Nov 12, 2015 at 9:07 AM, Nick Wedd  wrote:
> I was thinking about the ko rule for frisbee ko, and realised it leads to
> problems.
>
> 1.   Black takes a ko,  White tries to make a ko threat, but accidentally
> retakes the ko.  What should happen?

This was already covered by having any illegal frisbee landing revert to a pass.
Btw, it's impossible to make a ko threat neighbouring a ko retake, as
all those points are occupied:(

> 2.   Black takes a ko.  White tries to make a ko threat, but fails to make a
> valid move. Black tries to make connect the ko, but fails to make a valid
> move. May White now (try to) retake the ko?

Being a superko fan myself, the answer is clear: not if it repeats the position.

regards,
-John
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] KGS bot tournaments - what are your opinions?

[John Tromp]

On Wed, Oct 7, 2015 at 7:44 PM, Petr Baudis  wrote:
> On Wed, Oct 07, 2015 at 02:29:27PM +0200, Erik van der Werf wrote:
>> A measure that I find reasonable is a limit on number of threads x
>> clock frequency.

>   I'm not sure this would work well.  The #playouts difference between
> an old Bulldozer and new Haswell with the same nominal frequency and
> #cores might be many tens of percents.  Another question is how to find
> the scaling factors for other architectures?

Instead of frequency, one could use the single threaded Fhourstones score.

https://en.wikipedia.org/wiki/Fhourstones
http://tromp.github.io/c4/fhour.html

regards,
-John
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

[Computer-go] Number of Go positions computed modulo 2^64; source code available

[John Tromp]

See my updated webpage at

http://tromp.github.io/go/legal.html

regards,
-John
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Number of Go positions computed modulo 2^64; source code available

[John Tromp]

dear Robert,

 How much computation time do you expect to reveil the complete exact 19x19
 number? Or is more research necessary before I may ask this?

this computation of the 64 least significant bits was 1/9 of the total
effort needed. each such job contributes 64 bits to the answer.

regards,
-John
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Tromp Taylor rules http://senseis.xmp.net/?LogicalRules

[John Tromp]

On Wed, Mar 11, 2015 at 9:21 AM, folkert folk...@vanheusden.com wrote:
 Alvaro, Urban,

 thanks!

 I've got an additional question.
 It may be obvious but it is written a bit ambiguous imho on
 senseis.xmp.net:

 A player's score is the number of points of her color, plus the number
 of empty points that reach only her color.

 So an empty point that can reach the border of the board doesn't count,
 right?

Reaching is defined as a relation on points and colors (white, black or empty)
There is no notion of border in there. Borders are just lack of
adjacency for some points.
A 19x19 board with only a single black stone scores as +361 for Black.

-John
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

[Computer-go] The number of legal 18x18 Go positions is ...

[John Tromp]

669723114288829212892740188841706543509937780640178732810318337696945624428547218105214326012774371397184848890970111836283470468812827907149926502347633

More details at http://tromp.github.io/go/legal.html,
including a call for volunteers to contribute computing power for
determining what we all want to know, the number of 19x19 positions.

regards,
-John
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

[computer-go] go rules in Haskell

[John Tromp]

After some more tinkering, I put two new versions of Go Rules in Haskell
on my go page at

  http://www.cwi.nl/~tromp/go.html

The simpler one is annotated with the 10 articles of the rules, while
the fancier one is parametrized by board topology (like templates in C++).

Yesterday, I discovered a cute tutorial for Haskell at

  http://learnyouahaskell.com/

After completing that, it should be pretty easy to understand my programs...

regards,
-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] programming (languages) light-simulation contest

[John Tromp]

Claus Reinke wrote:
As for me, i'm really NOT interested in knowing what langage is good for go
programming. That's simply not a question i can ask myself, nor anyone else.
 This question doesn't make any sense for me. Still if someone can get the
standard light playout right in less than 10 code line, and they are very
understandable lines. I would be very happy to see it. But it would never
mean for me that, this language is BEST. Even if the peformances are
optimal there. I think 90% of the this language is the best debate gets it's
root in some affective part of the people engaged with it.

If, instead of asking what is the best language for writing a strong Go playing
program, we ask what is the best language for clealry expressing the rules of Go
(recognizing and scoring legal games), then I think Haskell
(http://www.haskell.org/)
deserves some consideration. See my attempt at

http://www.cwi.nl/~tromp/go/Go.hs

Such programs go a long way toward removing all ambiguity from informal
(e.g. English language) rule statements.

regards,
-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Please have your bot resign, for your own good

[John Tromp]

On Jan 3, 2008 10:46 AM, Don Dailey [EMAIL PROTECTED] wrote:
 Yes, the KGS rules gives only 1 chance to agree.   At one point KGS
 allowed this to happen repeatedly, but it cause some bots to infinite
 loop on the server when they disagreed. So I think it's better than
 nothing, but imperfect.

Infinite loops are impossible if the server ends the game with
board scoring after 4 consecutive passes
(i.e. after 2 passes, and disagreement, both players pass again).
It is up to the player who is behind in board score to make a move
in the continuation, in order to avoid losing.

regards,
-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

[computer-go] Re: language efficiency

[John Tromp]

On Dec 19, 2007 1:00 PM, Jeff Nowakowski [EMAIL PROTECTED] wrote:
 On Tue, 2007-12-18 at 15:04 -0500, John Tromp wrote:
 
  See the Haskell implementation of my connect-4 solver, Fhourstones, at
http://www.cwi.nl/~tromp/c4/fhour.html

 You say on that page: On my machine, the Java version is 75% slower
 than the C one, which I find hard to explain.

 Try running with -server, which enables aggressive JIT.  On my machine
 that made it nearly the same speed as the C version.  It needs more
 memory, though, and the first test case will be slow.

tromp java -version
java version 1.4.2_15
Java(TM) 2 Runtime Environment, Standard Edition (build 1.4.2_15-b02)
Java HotSpot(TM) Client VM (build 1.4.2_15-b02, mixed mode)
tromp javac -O SearchGame.java
tromp java -server -Xmx100m SearchGame  inputs
Fhourstones 3.1 (Java)
Boardsize = 7x6
Using 8306069 transposition table entries.

Solving 8-ply position after 45461667 . . .
score = 5 (+)  work = 14
51596 pos / 172 msec = 299.977 Kpos/sec
- 0.281  0 = 0.001  0.001 + 0.716

Solving 8-ply position after 35333571 . . .
score = 1 (-)  work = 21
8716732 pos / 4696 msec = 1856.204 Kpos/sec
- 0.271  0.036 = 0.02  0.089 + 0.584

Solving 8-ply position after 1111 . . .
score = 3 (=)  work = 26
169704432 pos / 89157 msec = 1903.434 Kpos/sec
- 0.216  0.144 = 0.021  0.242 + 0.377

tromp gcc -O3 -m64 -o SearchGame SearchGame.c
tromp ./SearchGame  inputs
Fhourstones 3.1 (C)
Boardsize = 7x6
Using 8306069 transposition table entries.

Solving 8-ply position after 45461667 . . .
score = 5 (+)  work = 15
105896 pos / 29 msec = 3651.6 Kpos/sec
- 0.285   0.000  = 0.000   0.000  + 0.714

Solving 8-ply position after 35333571 . . .
score = 1 (-)  work = 23
26134620 pos / 4777 msec = 5470.9 Kpos/sec
- 0.280   0.047  = 0.022   0.105  + 0.546

Solving 8-ply position after 1111 . . .
score = 5 (+)  work = 23
37058374 pos / 6561 msec = 5648.3 Kpos/sec
- 0.263   0.065  = 0.026   0.133  + 0.513

Huge difference (almost 3x faster)

Can someone try with a more up-to-date JVM, like
the latest from Sun and IBM, and with 64-bit opteron support?

regards,
-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Re: language efficiency

[John Tromp]

 But I have to admit, I don't know exactly how I'd go about
 implementing a transposition table in Haskell :-/ Perhaps I'll try for

See the Haskell implementation of my connect-4 solver, Fhourstones, at
  http://www.cwi.nl/~tromp/c4/fhour.html

regards,
-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Re: language efficiency

[John Tromp]

On Dec 18, 2007 3:03 PM, Chris Fant [EMAIL PROTECTED] wrote:
 On Dec 18, 2007 2:21 PM, Harald Korneliussen [EMAIL PROTECTED] wrote:
  I'd like to know how well MoGo would have played if you let it think
  for a week for every move. Only it seems to me that is not possible,
  because I don't think MoGo will run for a week without crashing.
  Crazystone also crashes quite a lot, if I understand the comments in
  KGS logs correctly.

 The windows version does crash after a while, but the Linux version
 seems stable until you run out of memory.

Which need never happen as long as you dynamcally increase the
  number_of_visits_before_leaf_expansion
parameter to slow down memory consumption over time.

regards,
-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Speed of generating random playouts

[John Tromp]

On Nov 16, 2007 10:05 AM, Chris Fant [EMAIL PROTECTED] wrote:
   Neat. Was the 15-bit version for 81 values or 361? At the risk of
   putting my foot in my mouth, I don't think there exist 361 15-bit
   numbers that satisfy minimum requirements (if the floating-point
   average of any four code values is a code value, then the four code
   values are identical).
 
  It was 361 values.  So either you are wrong or I have a bug.  I
  probably have a bug.  Here's the list.  If it violates the rules,
  please let me know.

 Yep, I think I had a bug.  I just removed an optimization that I
 thought was valid and now I'm getting smaller lists.  So I guess it
 was not valid.  Let me see how small I can get the numbers without
 that optimization...

No, it was far from valid; e.g. 14+14+14+3022 = 4 * 766
I don't think you can get 81 15-bit values either...

regards,
-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Speed of generating random playouts

[John Tromp]

On Nov 14, 2007 9:02 PM, Eric Boesch [EMAIL PROTECTED] wrote:

 The if average is in my original code_value set seems like a
 bottleneck here, requiring about #bits (i.e. about 9, since 361 is a
 9-bit number) operations no matter how you do it as far as I can tell
 (unless you use a stupidly gigantic lookup table), and there's a

The table can be kept small by having separate codes for x and y coordinate.

regards,
-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Speed of generating random playouts

[John Tromp]

On Nov 14, 2007 1:44 PM, Lavergne Thomas [EMAIL PROTECTED] wrote:

 Let elaborate a little more on this. We want one number for each cells :
   nums = {n1, n2, n3, ..., n81}

 And we want the following properties :

   for any a, b in nums :
   (a + b) / 2 is in nums -- a == b
   for any a, b, c in nums :
   (a + b + c) / 3 is in nums -- a == b == c
   for any a, b, c, d in nums :
   (a + b + c + d) / 4 is in nums -- a == b == c == d

If you want to make use of the pseudoliberty count, yes.
My solution doesn't make use of that, and satisfies the stronger property:

0 = a_i = 4 and sum a_i * n_i is in 1*nums union 2*nums union 3*nums
union 4*nums
= only one a_i is nonzero.

 If we have this we are sure to don't have problems like you pointed.
 Using brute force search, I've produced the following sequence of
 numbers :
 ...
 148912497, 156351446, 168096257, 176942297, 194310098, 211199842]
 This sequence is not the best you can found, but it was quick to
 generate...

indeed, it's possible with much smaller numbers.

 But now we have another problem... We have the sum of the number of the
 pseudo libertyes of a chain, and we can compute (sum / nb_plibs) but
 next we have to check if the resulting number is in the list.

 And the second problems is that this solution doesn't scale well. On
 19x19 you need 361 numbers in your list, so even if you find a list like
 this, I doubt that you can sum up the value of all the pseudo liberties
 of a big group without overflowing an unsigned and you have to switch
 to bigger int like int 64.

 So I think John was suggesting something different in his first mail,
 but I still search what it can be...
 Does anyone have an idea ?

you might try to encode the x and y coordinate of a point separately...

regards,
-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Speed of generating random playouts

[John Tromp]

On Nov 14, 2007 2:00 PM, John Tromp [EMAIL PROTECTED] wrote:

 My solution doesn't make use of that, and satisfies the stronger property:

 0 = a_i = 4 and sum a_i * n_i is in 1*nums union 2*nums union 3*nums
 union 4*nums
 = only one a_i is nonzero.

that was not quite correct. it should say:

let a_i be the number of adjacencies to a liberty at point i.

if sum a_i = 4, and sum (a_i * n_i)  is in {1,2,3,4} * nums,
then only one a_i is nonzero.

regards,
-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Speed of generating random playouts

[John Tromp]

On Nov 14, 2007 5:03 PM, Imran Hendley [EMAIL PROTECTED] wrote:

 On Nov 14, 2007 3:19 PM, John Tromp [EMAIL PROTECTED] wrote:
  On Nov 14, 2007 2:00 PM, John Tromp [EMAIL PROTECTED] wrote:
 
   My solution doesn't make use of that, and satisfies the stronger property:
 
   0 = a_i = 4 and sum a_i * n_i is in 1*nums union 2*nums union 3*nums
   union 4*nums
   = only one a_i is nonzero.
 
  that was not quite correct. it should say:
 
  let a_i be the number of adjacencies to a liberty at point i.
 
  if sum a_i = 4, and sum (a_i * n_i)  is in {1,2,3,4} * nums,
  then only one a_i is nonzero.

 I'm really lost now. a_i is the number of stones we have adjacent to a
 liberty at intersection i? Do we need to know the location of our
 liberties to update sum a_i? How is this easier than just remembering

For every string, you can keep track of this sum incrementally.
When the string establishes a new adjacency to an empty point i,
you add code[i] into the sum.

 the locations of all real liberties you saw? How do we know that the
 stones around i are from the same group? What are the n_i in

n_i was the name that Tom gave to my code[i].

 sum(a_i*n_i)? is {1,2,3,4}*nums supposed to be a cartesian product of

no, it's just my shorthand for the union of the 4 sets nums, 2*nums,
3*nums and 4*nums.

regards,
-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Language

[John Tromp]

On Nov 13, 2007 11:10 AM, William Harold Newman
[EMAIL PROTECTED] wrote:
 On Mon, Nov 12, 2007 at 04:41:35PM -0500, Chris Fant wrote:
  I would like some language recommendations.  Requirements:

 Among the languages I know something about (which excludes D and C#,
 for example)...

 technically perhaps allowed by your feature list, but in my judgment a
 poor fit for Go (because, e.g., strict purely functional data
 structures make it hard to efficiently modify a single square among
 361):
   * Haskell

Haskell does have arrays of course, even while remaining purely functional
(through the magic of so-called monads). I used them in
the Haskell version of my Connect-4 solver...

regards,
-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Language

[John Tromp]

On Nov 13, 2007 2:15 PM, Don Dailey [EMAIL PROTECTED] wrote:
 How does the speed of the Haskell version compare to the C and Java
 version? The Haskell web site now brags about how fast Haskell is.

Not too well:-(
Fhourstones in Haskell runs more than 10 times slower than the C version...

regards,
-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Speed of generating random playouts

[John Tromp]

  Yes, you can generalize pseudoliberties by extending them
  with another field, such that if the (summed) pseudoliberty field
  is between 1 and 4, then the other (summed) field will tell you if all
 these
  are coming from a single true liberty.

 Can you elaborate on this?

Let me pose it as an exercise.

You can assign to each point p a value code[p]
such that if you add up the code[] of between 1 and 4 points
(not necessarily different), then from this sum you can tell whether
all these points are identical, and if so, what that point is.

It's like an error correcting code.

instead of plain pseudoliberties, which sum the value 1 for each
stone-empty adjacency,
we can sum these code[]s as well...

regards,
-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Solving Go

[John Tromp]

On 11/12/07, Don Dailey [EMAIL PROTECTED] wrote:
 Ok,  on 2x2 I get a consistent result now that I implemented PSK.   It
 gives the same result with SSK too.  It's a 1 point win for the first
 player. I'm not sure this is in agreement with other peoples
 findings.   But it appears to be consistent.I can work my way

Yes, this is consistent with my programs at
  http://www.cwi.nl/~tromp/java/go/twoxtwo.html

 through the game and it always returns the same score if I make the
 move(s) the search believes is best.

 After black plays the first move,  white's best response is to move to
 the opposite corner.Otherwise it's a 4 point win for black.

 Here are the parameters I use:
1.  positional superko unless otherwise stated.
2.  evaluation function:   Each stone is alive - an empty point
 belongs to a player if only his stones touch it.
3.  game over after 2 passes.
4.  suicide illegal.

Suicide is particularly useless on 2x2 :-)

 3x3 gives a black win by 9 points (the whole board.)
 If black plays first move on the edge (a2 for instance)  then he wins by
 3 points instead of 9.

The only subtlety is that after white B2, black must clamp at c2,
since the hane moves at b1/b3 only win by 2.

 If black plays first move on corner,  white wins by 9 points.
 Does anyone have any data to check these facts ??

matches manual analysis and previous computer search.

 It may try this with 4x4 after doing something to improve the move ordering.

That should come out as B+2.

regards,
-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Solving Go

[John Tromp]

 I just ran my perm application for 4x4 and it's reporting
 43,046,721 unique board states and took  2m6.980s. Will try for 5 and 6.

seems you're computing 3**(n*n)

3**16 = 43046721
3**25 = 847288609443
3**36 = 150094635296999121

don't you want to exclude illegal positions?

-john
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] 19x19 CGOS

[John Tromp]

On 10/29/07, Christoph Birk [EMAIL PROTECTED] wrote:
 On Mon, 29 Oct 2007, Jacques Basaldúa wrote:
  This can also be done by the programmers. E.g. If CrazyStone is too strong,
  Rèmi can introduce a CrazyStoneH3 which passes 3 times
  at the beginning. But not at the first move, to avoid smart tricks.
 
  If CrazyStoneH3 is given white and plays: 2. whatever 4. pass 6. pass 8.
  pass. Black cannot pass and win the game because of komi.

But to avoid Black from winning by capturing white's stone and passing,
white needs to make sure to play her stone where it has 4 liberties.
Even that is not sufficient; white has to play this stone on the 3rd
line or higher
(exercise for the reader: how cld black take advantage of some 2nd line moves?)

regards,
-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] OT: median of a data stream

[John Tromp]

On 8/16/07, Darren Cook [EMAIL PROTECTED] wrote:
 Apologies for the off-topic post, but I know lots of people here are
 interested in statistics and algorithms.

 Calculating the mean of a stream of numbers [1] is easy: just keep track
 of the sum and the count, and divide at the end. But what about the
 median? I think I always need to buffer at least half the numbers, but
 does anyone know for sure, or know a clever algorithm [2]?

You'll have to remember all numbers.
If you've seen a_0  a_1  a_2  ...  a_n   so far,
then for any i, 0=i=n, you'll have to ouput a_i after an additional
(n-i) values less than a_0, and i values greater than a_n.

regards,
-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Re: Amsterdam 2007 paper

[John Tromp]

hi Sylvain  David,

Figure 3 in your UCT paper shows the accuracy of different simulation policies.
Could you repeat these experiments for accuracy of win/loss determination only?
So for each test position, you determine if it's won or lost under perfect play,
and then see how close each policy gets to either 0% or 100% wins.
One might think that this measure of accuracy is what actually matters to UCT,
since it is not concerned with margin of victory.
Is the advantage of Mogo's policy still as pronounced?

regards,
-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Re: Amsterdam 2007 paper

[John Tromp]

hi Sylvain,


 Figure 3 in your UCT paper shows the accuracy of different simulation 
policies.
 Could you repeat these experiments for accuracy of win/loss determination 
only?
Actually the labelled positions are rather end game positions, and are
labelled as 0/1 (loss/win). So we already are in the case you propose.


You mean they are positions in which humans passed and scored the game?
And you're just testing if the simulation correctly converts all
territories into 1-point eyes,
and kills all invasions?

regards,
-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Go and UCT: article in June 2007 SciAm

[John Tromp]

On 5/24/07, Darren Cook [EMAIL PROTECTED] wrote:

P.S. John, it says the new algorithm can topple strong players - shall
we just believe them and say I won that bet? We don't really need to
play the games out to prove it do we ;-).


On 9x9 they definitely can. I've lost a few games myself to the likes of Mogo.
But on 19x19 they have some way to go, and it will be interesting to see if
they can make it. 3.5 years is a long time, and with the current pace of
developments, I think you stand a fair chance to win our bet. Some people
have alrready inquired if they can get in on the bet themselves.
My co-author Álvaro thinks I'll still have the upper hand in 2010, so I
suggest people contact him to make additional bets:-)

regards,
-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Go and UCT: article in June 2007 SciAm

[John Tromp]

On 5/25/07, Don Dailey [EMAIL PROTECTED] wrote:

Is there some kind of bet on this?When did that happen?   What is
the bet exactly?


Somewhere around 2000, I claimed I would not be beaten by a computer
under match conditions (eg. 10 games at 1hr per side + byo-yomi)
within 10 years. Which Darren doubted. So we made a bet... for $1000.
So far Darren has not arranged for any match:-)

regards,
-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Progressive unpruning in Mango 19x19

[John Tromp]

Question for native English speakers: do you think this technique is best
described by progressive unpruning or progressive widening?


I'm no native speaker, but I think using the word selectivity may be
most descriptive.
Does regressive selectivity sound too weird ?

regards,
-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Amsterdam paper

[John Tromp]

On 5/19/07, Thomas Wolf [EMAIL PROTECTED] wrote:

Here is another Amsterdam paper on Go, although about life  death
and not full game playing.


I may be missing the obvious, but in Section 4.2, Diagram 13,
isn't Black 10 a basic ko violation?

regards,
-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] KO in Hashtable-UCT?

[John Tromp]

On 5/18/07, Peter Drake [EMAIL PROTECTED] wrote:

It took me a long time to get around my mental block and accept the advice
of everyone here, but your intuition is correct: superko is so rare, and so
expensive to detect, that you should NOT check for it on every move.


In dimwit, we check for superko while descending the UCT tree,
and only check basic ko in the MC playouts. Our check involves
a single lookup (of the current, incrementally computed Zobrist key)
in a hash_map of previous Zobrist keys, which is not all that expensive.
I agree that doing superko checks in MC playouts would cause an
unnecesary slowdown.

regards,
-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] 12th Computer Olympiad

[John Tromp]

On 4/5/07, Chaslot G (MICC) [EMAIL PROTECTED] wrote:


The workshop will be held on Friday 15. - Sunday 16. June 2007.


Must be a leap Saturday...

regards,
-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] KGS Computer Go tournaments

[John Tromp]

dear Nick,


   I am considering postponing the MAY KGS bot tournament from Sunday
   MAY 6th (in the UK, this is the Spring Bank Holiday) to Sunday MAY
   13th.Will this inconvenience anyone?


It might be a nice thing to watch on my birthday:-)
I might even participate...

regards,
-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

[computer-go] pseudoliberties

[John Tromp]

Out of curiosity,

Is 88 the maximum number of pseuoliberties a string can have on 9x9?

(it should be safe to use only 6 bits in practice, if you need every last bit:)

regards,
-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

[computer-go] Re: pseudoliberties

[John Tromp]

On 3/29/07, John Tromp [EMAIL PROTECTED] wrote:


Is 88 the maximum number of pseuoliberties a string can have on 9x9?


Make that 89:-)

-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Re: pseudoliberties

[John Tromp]

On 3/29/07, Weston Markham [EMAIL PROTECTED] wrote:

It appears to me that at least 91 is possible:

.xx.x.xx.
xx.xxx.xx
.xx.x.xx.
xx.xxx.xx
.xx.x.xx.
xx.xxx.xx
.xx.x.xx.
xx.xxx.xx
.xxx.xxx.


Nice! If you use O's instead like

.OO.O.OO.
OO.OOO.OO
.OO.O.OO.
OO.OOO.OO
.OO.O.OO.
OO.OOO.OO
.OO.O.OO.
OO.OOO.OO
.OOO.OOO.

it looks pretty artistic, like a vase with a flower inside:-)

-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Re: pseudoliberties

[John Tromp]

On 3/29/07, Weston Markham [EMAIL PROTECTED] wrote:

On 3/29/07, John Tromp [EMAIL PROTECTED] wrote:
 On 3/29/07, Weston Markham [EMAIL PROTECTED] wrote:
  It appears to me that at least 91 is possible:
 Nice! If you use O's instead like

 .OO.O.OO.
 OO.OOO.OO
 .OO.O.OO.
 OO.OOO.OO
 .OO.O.OO.
 OO.OOO.OO
 .OO.O.OO.
 OO.OOO.OO
 .OOO.OOO.

 it looks pretty artistic, like a vase with a flower inside:-)

:)

It appears that you can get 92 as well, by replacing the two empty
intersections along the upper edge of my diagram with a single one in
the center of that edge, and placing an empty intersection on one of
the other intersections along the central line of symmetry.


If it weren't for the fact that that central line is needed to keep
everything connected:-)

-john
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Re: pseudoliberties

[John Tromp]

On 3/29/07, Christoph Birk [EMAIL PROTECTED] wrote:

On Thu, 29 Mar 2007, Jim O'Flaherty, Jr. wrote:

 What's a pseudo-liberty?
 And how can there be more of them than there are empty intersections
 (81) on the board?

It is the sum of all stone's liberties in a group; ignoring common
liberties.


In other words, the number of stone-empty adjacencies.

-john
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Re: pseudoliberties

[John Tromp]

As far as I know, pseudo-liberties are only used for detecting a
capture or detecting atari.  If this method you suggest has some value
beyond that, then I'm interested to learn more about it.  But the



I have a nice mathematical puzzle for you.

Fix some k, say, 81.
What is the smallest range N for which you can pick k N-bit
numbers, n_1,n_2,...n_k with the following properties:

{2*n_i, 3*n_i, 4*n_i} is disjoint from
{n_a + n_b,
 n_a + n_b + n_c, n_a + 2n_b,
 n_a + n_b + n_c + n_d, n_a + n_b + 2n_c, n_a + 3n_b, 2n_a + 2n_b}
(where a,b,c,d are different)


regards,
-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: Re:[computer-go] MoGo

[John Tromp]

On 3/19/07, Don Dailey [EMAIL PROTECTED] wrote:

I'm testing a future Anchor player for CGOS.  I am calling
it FAT for Future Anchor Test!

It plays fixed depth and I pre-calculated what level to make
it play at 1800 strength.  I came pretty close,  Fat-25 is
playing at 1836 at the moment and doesn't require too much
CPU power.   It's Lazarus scaled down to play fast.


Isn't AnchorMan a program that plays pure MC with uniformly random
(unbiased except for eyeflll) moves?

Then it would be good to have as 2nd anchor a program that plays
pure UCT with pure MC and nothing fancy.

If parameters like #simulations and exploration coefficient are fixed,
then people can test their own implementations by seeing if they can
closely match this UCT anchor in rating.

I'm assuming here that it wouldn't take that much computing power to
make such a program play at an 1800 rating.

regards,
-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

[computer-go] Re: computer-go Digest, Vol 32, Issue 19

[John Tromp]

hi Don,


 Are you trying to make a Monte Carlo program?


Guilty:-)
Since about a week and a half, me and my colleague Alvaro Begue are
working on a Go program, which (like many others) wil try to imitate
Mogo's success...

regards,
-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] average length of 9x9 MC playout

[John Tromp]

dear Don,


Crazy me.  I just remembered why my numbers are not matching.  I forgot
that what I call the lite play-out version is not random.  It's mostly
lite but it favors capture moves.


Yes, I can see how that will shorten the games somewhat...
Is it easy to temporarily turn off that bias?

-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

[computer-go] Cheap multiprocessing

[John Tromp]

Those of you looking to wring more performance out of your
MonteCarlo Go programs might be interested in this article about
installing Linux on the Sony PlayStation 3 and programming the
6 available SPE coprocessors on its Cell cpu:
http://www-128.ibm.com/developerworks/power/library/pa-linuxps3-1/

regards,
-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Cheap multiprocessing

[John Tromp]

On 1/5/07, Darren Cook [EMAIL PROTECTED] wrote:


The playstation multiprocessing looks very different: you get 1 general
purpose CPU and 6 specialized CPUs. Their key feature is they have 256K
of local memory - this is not cache, it is all the memory they can
access. Not useful for UCT designs (which seem memory-limited currently)
but fine for normal monte-carlo.


The UCT tree is kept in main memory by the single PPE.
The 6 SPEs which do the individual MC simulations don't need any access
to that tree and should run perfectly fine in 256k...

regards,
-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Fw: Compensation for handicap plays?

[John Tromp]

On 12/29/06, Łukasz Lew [EMAIL PROTECTED] wrote:


I did some research and I would like to change my vote.

My criterion for perfect rules are elegance, simplicity and consistency.
As You know I want unification of area and territory scoring.
So here is my proposal.

The unification needs that *pass* costs one point.
And this is only modification needed.

The handicaps are set up in a way that white passes between Black's moves.
Ie. he gives one point to the black N-1 times.

Please think about it.



For reducing the value of handicap stones under area scoring,
white should *get* an extra point for each
additional handicap stone, not *lose* a point as you suggest.

-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Fw: Compensation for handicap plays?

[John Tromp]

On 12/28/06, Don Dailey [EMAIL PROTECTED] wrote:


 Just to be precise: KGS does option 2 if you select chinese rules, and
 it also does option 1 when you select AGA rules.

And to be more precise,  here is how it might work:

  Handicap
  
  0- komi is 7.5 and either player plays black.
  1- komi is 0.5 and weaker player plays black.
  2- komi is 0.5, weaker player gets black, white gets 2 points.
  3- komi is 0.5, weaker player gets black, white gets 3 points.

At 2 handicap and beyond, the net effect is as if komi was increased by
the number of stones handicap (but it won't be implemented that way.)

Is this how everyone else understands it?



That makes little sense to me. If you want to give white extra points at the
end
of the game, then put it in the komi. That's what it's for!
So above, for 2hcap, komi will be 2.5, and for 3hcap, it will be 3.5...
Why introduce 2 different komi's that need to be added?

-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Unsigned random numbers in Java

[John Tromp]

On 21 Dec 2006 21:41:25 +, David Denholm [EMAIL PROTECTED]
wrote:


John Tromp [EMAIL PROTECTED] writes:

 Or use (r  (-11)) to obtain a nonnegative value (instead of abs(r)),

I think you meant  (-1  1)  : (-1  1)  is still -1  since  is
a signed shift (preserves top bit).  is the unsigned shift which
clears top bit.



Right you are:)

-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] language choices

[John Tromp]

On 12/5/06, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote:


 Mogo would also have a memory problem.   The UCT programs build trees in
 memory.  My own  program cannot think more than a few minutes without
 running out of memory - so even the experiment you propose cannot be
 done.
Yes you are right. For MoGo it is even worst. As all the games we have to
play
in are short games, we did not at all optimize the memory use, and in
fact
MoGo a lot more memory than necessary. I am not totally sure, but I think
even 1 minute/move is already too much :). Of course, we can be more
carefull
with memory usage, but for the moment it is not the higher priority.



How long would it take Mogo to fill up 16GB of memory on a quad core opteron
machine?

regards,
-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] language choices

[John Tromp]

hi Sylvain,

This could be very interesting!


If by anyway I can have an user account on this machine, I can try to
compile
MoGo and launch it on KGS so that you can easily play, and everyone can
watch
the games.
What do you think?



The machine is a central component of the Linux supercomputer cluster at
CWI,
where I used to work.  Access is limited to CWI users I'm afraid:-(
Can you compile it on any other Linux machine with an up to date gcc -O3
-static -m64 ?

Once I get it running, I'll be happy to replay the game life on KGS as a
demo game.

regards,
-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] language choices

[John Tromp]

hi Don,

Why can't you just play it live on KGS?   This is much more exciting.

We would have no way to know if you were taking back moves or anything.
(Although I believe you to be an honest person I still like to see for
myself :-)



If Sylvain provides me with a Mogo version that can connect to KGS, then
I'll try to play it directly there. But I thought it might be easier for him
to
provide a console version... Let's wait and see:)

regards,
-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/