It is currently Thu Mar 28, 2024 7:09 pm

All times are UTC - 8 hours [ DST ]




Post new topic Reply to topic  [ 69 posts ]  Go to page Previous  1, 2, 3, 4
Author Message
Offline
 Post subject: Re: BOINC and brute forcing
Post #61 Posted: Mon Sep 06, 2010 5:39 pm 
Lives in gote

Posts: 589
Liked others: 0
Was liked: 114
Rank: 2 dan
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.

Top
 Profile  
 
Offline
 Post subject: Re: BOINC and brute forcing
Post #62 Posted: Mon Sep 06, 2010 5:43 pm 
Lives in sente
User avatar

Posts: 761
Liked others: 152
Was liked: 204
Rank: the k-word
Let me just say this, speaking as someone with a math degree:

Bwahahahaha finitists.

Top
 Profile  
 
Offline
 Post subject: Re: BOINC and brute forcing
Post #63 Posted: Mon Sep 06, 2010 5:54 pm 
Lives with ko
User avatar

Posts: 129
Location: Turku, Finland
Liked others: 12
Was liked: 21
Rank: EGF 1989 KGS 2d
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?

Top
 Profile  
 
Offline
 Post subject: Re: BOINC and brute forcing
Post #64 Posted: Mon Sep 06, 2010 5:59 pm 
Lives in gote

Posts: 589
Liked others: 0
Was liked: 114
Rank: 2 dan
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.

Top
 Profile  
 
Offline
 Post subject: Re: BOINC and brute forcing
Post #65 Posted: Tue Sep 07, 2010 11:42 am 
Lives in sente
User avatar

Posts: 761
Liked others: 152
Was liked: 204
Rank: the k-word
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.

Top
 Profile  
 
Offline
 Post subject: Re: BOINC and brute forcing
Post #66 Posted: Tue Sep 07, 2010 11:45 am 
Honinbo

Posts: 9545
Liked others: 1600
Was liked: 1711
KGS: Kirby
Tygem: 커비라고해
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.

_________________
be immersed

Top
 Profile  
 
Offline
 Post subject: Re: BOINC and brute forcing
Post #67 Posted: Tue Sep 07, 2010 12:31 pm 
Tengen
User avatar

Posts: 4844
Location: Mechanicsburg, PA
Liked others: 62
Was liked: 505
Rank: Wbaduk 7D
KGS: magicwand
Tygem: magicwand
Wbaduk: rlatkfkd
DGS: magicwand
OGS: magicwand
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.

_________________
"The more we think we know about
The greater the unknown"

Words by neil peart, music by geddy lee and alex lifeson

Top
 Profile  
 
Offline
 Post subject: Re: BOINC and brute forcing
Post #68 Posted: Tue Sep 07, 2010 12:51 pm 
Lives in gote
User avatar

Posts: 388
Location: Riverside CA
Liked others: 246
Was liked: 79
Rank: KGS 7 kyu
KGS: Krill
OGS: Krill
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.

Top
 Profile  
 
Offline
 Post subject: Re: BOINC and brute forcing
Post #69 Posted: Tue Sep 07, 2010 1:38 pm 
Lives in sente
User avatar

Posts: 761
Liked others: 152
Was liked: 204
Rank: the k-word
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).

Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 69 posts ]  Go to page Previous  1, 2, 3, 4

All times are UTC - 8 hours [ DST ]


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group