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

[Stefan Kaitschick]

Good joke to render the solution as a board position.
___
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

[Erik van der Werf]

Congratulations John!

Does the number include symmetrical positions (rotations / mirroring /
color reversal)?

Best,
Erik


On Fri, Jan 22, 2016 at 5:18 AM, John Tromp  wrote:

> 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
___
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

[Petr Baudis]

On Thu, Jan 21, 2016 at 11:18:25PM -0500, John Tromp wrote:
> It's been a long journey, and now it's finally complete!
> 
> http://tromp.github.io/go/legal.html
> 
> has all the juicy details...

Congratulations!

(Piece of trivia: Michal Koucky who collaborated on this research is
essentially in the same department where I was when I was working on
Pachi, and where most of Pachi tuning and testing happenned, but we
don't really know each other (I was already external when he joined).
And the department head is the 1985 Czech Go champion, though he
doesn't play Go anymore.  And none of these facts are causally
connected in any way AFAIK!)

-- 
Petr Baudis
If you have good ideas, good data and fast computers,
you can do almost anything. -- Geoffrey Hinton
___
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

[Robert Jasiek]

On 22.01.2016 05:18, John Tromp wrote:

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

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


Congratulations!

You must have needed 15 or 20 years of research to find the result? 
Eventually you heavily rely on computational power. How has it been 
possible to get hold of the computers and computation time? 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?


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


Does the solution give a useful clue of how difficult it is to solve go 
as a game weakly or strongly? 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?


--
robert jasiek
___
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

[Aja Huang]

Very interesting. Thanks John. :)

Aja

On Fri, Jan 22, 2016 at 4:18 AM, John Tromp  wrote:

> 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
___
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

[Ingo Althöfer]

Congratulations, John!

Do you want to publish your result in a paper?
(One leading member in the editorial board of the "International Journal
of Game Theory" is interested in such types of results.

Cheers, Ingo.


> Gesendet: Freitag, 22. Januar 2016 um 05:18 Uhr
> Von: "John Tromp" 
> An: computer-go 
> Betreff: [Computer-go] Number of Go positions computed at last
>
> 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
___
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

[Adrian Petrescu]

Very cool! I find it interesting that the number is only about 1.2% of
3^361 (though I realize 3^361 doesn't take symmetries into account). On the
surface it's counterintuitive to me that nearly 99% of random stone
configurations are not legal Go positions!

On Fri, Jan 22, 2016 at 10:50 AM, Xavier Combelle  wrote:

> well done !
>
> 2016-01-22 5:18 GMT+01:00 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
>
>
>
> ___
> 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] Number of Go positions computed at last

[Thomas Wolf]

On Fri, 22 Jan 2016, Adrian Petrescu wrote:


Very cool! I find it interesting that the number is only about 1.2% of 3^361 
(though I realize 3^361 doesn't take symmetries into account).
On the surface it's counterintuitive to me that nearly 99% of random stone 
configurations are not legal Go positions!


The chance to violate the rule somewhere goes linearly with the area, so
quadratically with the size of the board.



On Fri, Jan 22, 2016 at 10:50 AM, Xavier Combelle  
wrote:
  well done !

2016-01-22 5:18 GMT+01:00 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



___
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] 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