Life In 19x19
http://lifein19x19.com/

BOINC and brute forcing
http://lifein19x19.com/viewtopic.php?f=18&t=1538
Page 4 of 4

Author:  amnal [ Mon Sep 06, 2010 5:39 pm ]
Post subject:  Re: BOINC and brute forcing

Liisa wrote:
Kirby wrote:
So in terms of go, it has already been proven that a solution exists. We do not know what the solution is, but when we find it, we will have a practical and implementable strategy for both sides, which, yes, you can play on a real go board.


If solution for go would be in any case meaningful statement, you need to make estimation how big is the solution. We know that there is 10^80 protons in the universe and time span has been only 10^60 units in Planck time. These are our ultimate limits how much data we can process. If you think that solution is non-absurd and fits the limits, then fine and solution is meaningful. But I would disagree, because we need to have some knowledge from end position in order find even weak solution and say with certainty who is leading in given position.


It has already been pointed out that you have made a non-obvious leap from 'the Universe can only store so much information' to 'a complete brute force solution of Go would require more information than the Universe can contain'. You have provided an estimate for information capacity in fairly meaningless units of proton number and timespan, but have not provided an estimate for the information necessary to describe Go - saying only that you think it's bigger than this value, without justification.

These are my problems with drawing any conclusions from your points, though the question 'how much information is necessary to weakly or strongly solve Go' is an interesting one.

Author:  palapiku [ Mon Sep 06, 2010 5:43 pm ]
Post subject:  Re: BOINC and brute forcing

Let me just say this, speaking as someone with a math degree:

Bwahahahaha finitists.

Author:  Liisa [ Mon Sep 06, 2010 5:54 pm ]
Post subject:  Re: BOINC and brute forcing

amnal wrote:
These are my problems with drawing any conclusions from your points, though the question 'how much information is necessary to weakly or strongly solve Go' is an interesting one.


May I have your answers to this question. How big solution do you think is still meaningful?

Author:  amnal [ Mon Sep 06, 2010 5:59 pm ]
Post subject:  Re: BOINC and brute forcing

Liisa wrote:
amnal wrote:
These are my problems with drawing any conclusions from your points, though the question 'how much information is necessary to weakly or strongly solve Go' is an interesting one.


May I have your answers to this question. How big solution do you think is still meaningful?


I don't really know what your question means.

Author:  palapiku [ Tue Sep 07, 2010 11:42 am ]
Post subject:  Re: BOINC and brute forcing

Monadology wrote:
One of the problems, Liisa, is you're only considering the quantity of objects in the 'size' of the universe. This is not strictly accurate in terms of what it can contain computationally. Not only are there objects, there are relationships between and combinations of objects to count. And those possibilities easily exceed the size of Go as a game.

No, they don't. Here's a paper that calculates the computational capacity of the universe:

http://www.scribd.com/doc/15664694/Comp ... SCIENCECOM

According to the paper, the capacity is 10^120 bits, using all the possible degrees of freedom of every particle in the universe.
The number of different Go positions (2*10^170) is already much larger than that. The number of different games is much larger still.

Author:  Kirby [ Tue Sep 07, 2010 11:45 am ]
Post subject:  Re: BOINC and brute forcing

The thing is, we don't know what techniques people will develop in the future. It is possible that somebody is able to prove some generalization X, which could allow us to prove other things about the game without having to literally iterate through each possibility.

For example, suppose we can prove certain properties for any shape Y. Then we no longer need to iterate through things having to do with such shapes on the board, because we've already proven the properties.

So, yes, the numbers for go are large. But we cannot say definitively that future developments will not lead to proofs for optimal strategies.

Author:  Magicwand [ Tue Sep 07, 2010 12:31 pm ]
Post subject:  Re: BOINC and brute forcing

computer already beat professional chess player but still didnt prove chess.
i am sure we can create an algorithm that is stronger than professional.
we dont have to prove it.

Author:  Monadology [ Tue Sep 07, 2010 12:51 pm ]
Post subject:  Re: BOINC and brute forcing

palapiku wrote:
Monadology wrote:
One of the problems, Liisa, is you're only considering the quantity of objects in the 'size' of the universe. This is not strictly accurate in terms of what it can contain computationally. Not only are there objects, there are relationships between and combinations of objects to count. And those possibilities easily exceed the size of Go as a game.

No, they don't. Here's a paper that calculates the computational capacity of the universe:

http://www.scribd.com/doc/15664694/Comp ... SCIENCECOM

According to the paper, the capacity is 10^120 bits, using all the possible degrees of freedom of every particle in the universe.
The number of different Go positions (2*10^170) is already much larger than that. The number of different games is much larger still.


Can't argue with the math, I suppose, but can you explain to me how 361 entities each with 3 possible states produces more potential combinations than the sum of the particles of the universe (much greater than 361) each with far more than 3 possible states? I'm assuming it has to do with the virtual possibilities of Go in terms of 'time' (successive positions), but you've got the math degree.

Author:  palapiku [ Tue Sep 07, 2010 1:38 pm ]
Post subject:  Re: BOINC and brute forcing

Monadology wrote:
palapiku wrote:
Monadology wrote:
One of the problems, Liisa, is you're only considering the quantity of objects in the 'size' of the universe. This is not strictly accurate in terms of what it can contain computationally. Not only are there objects, there are relationships between and combinations of objects to count. And those possibilities easily exceed the size of Go as a game.

No, they don't. Here's a paper that calculates the computational capacity of the universe:

http://www.scribd.com/doc/15664694/Comp ... SCIENCECOM

According to the paper, the capacity is 10^120 bits, using all the possible degrees of freedom of every particle in the universe.
The number of different Go positions (2*10^170) is already much larger than that. The number of different games is much larger still.


Can't argue with the math, I suppose, but can you explain to me how 361 entities each with 3 possible states produces more potential combinations than the sum of the particles of the universe (much greater than 361) each with far more than 3 possible states? I'm assuming it has to do with the virtual possibilities of Go in terms of 'time' (successive positions), but you've got the math degree.


The computational capacity of the universe - the amount of information it can hold - is 10^120 bits. The computational capacity of the Go board is only about 572 bits (361 trits, like you said).

The number of different states the universe can be in is 2^(10^120), a much bigger number. The universe can certainly be in a state where it encodes any Go position (example: there's a Go board somewhere in the universe with that position on it :)). But the universe is not big enough, for example, to construct a table of all positions and mark whether each one is a win by Black (that would require just 1 bit per position, and there're not enough bits).

Page 4 of 4 All times are UTC - 8 hours [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/