BOINC and brute forcing

For discussing go computing, software announcements, etc.
User avatar
Monadology
Lives in gote
Posts: 388
Joined: Wed Jun 23, 2010 1:26 pm
Rank: KGS 7 kyu
GD Posts: 0
KGS: Krill
OGS: Krill
Location: Riverside CA
Has thanked: 246 times
Been thanked: 79 times

Re: BOINC and brute forcing

Post by Monadology »

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.

There are two interesting things what we get from quantum logic: A) logic is empirical science. B) mathematics as a science loses meaning.


In the case of A, Logic simply ceases to be anything like actual logic. B, I don't see how this follows at all. In fact, I'm pretty sure B is a logical absurdity. The entire construct of quantum mechanics is derived from mathematical modeling of observed physical reality. If mathematics as a science becomes meaningless you've undermined the very thing which composes quantum mechanics in the first place.

You're making some very bold claims though, without clarifying what in the world they mean. What the heck is "quantum logic"? Why should we even want it? For all we know quantum mechanics is an ultimately inaccurate model of the universe like Newtonian mechanics. That's always the limitation of the empirical. A model like quantum mechanics simply is not capable of verification. You're suggesting we hedge some serious bets in a manner that indicates you have non-empirical knowledge of its ultimate truth. And even if it were true, I don't see why it would make mathematics or logic any less valuable or somehow obsolete. Modus ponens is still going to hold and will still have plenty of practical applications.
Kirby
Honinbo
Posts: 9553
Joined: Wed Feb 24, 2010 6:04 pm
GD Posts: 0
KGS: Kirby
Tygem: 커비라고해
Has thanked: 1583 times
Been thanked: 1707 times

Re: BOINC and brute forcing

Post by Kirby »

palapiku wrote:
Kirby wrote:As for whether go can be tied, Cassandra, I agree that it's a different type of game than checkers/draughts. I want to just point out that it is theoretically possible that humans, through suboptimal play, have come to believe that black has an advantage when it could, in fact, not be the case.

However, I agree that this is quite unlikely.

Especially since black is definitely way ahead on the small boards where we can verify this.


Well, this is not a proof, but there could potentially be a pattern.
be immersed
Kirby
Honinbo
Posts: 9553
Joined: Wed Feb 24, 2010 6:04 pm
GD Posts: 0
KGS: Kirby
Tygem: 커비라고해
Has thanked: 1583 times
Been thanked: 1707 times

Re: BOINC and brute forcing

Post by Kirby »

Liisa,
Solving go may indeed be very difficult, but it is possible because it is a finite two-person game with a finite number of possible strategies for each player.

John Nash proved that any such game has at least one Nash equilibrium - a solution where neither player has anything to gain by changing their (optimal) strategy.

You can read about it more on wikipedia, if you'd like:
http://en.wikipedia.org/wiki/Nash_equilibrium
be immersed
User avatar
daniel_the_smith
Gosei
Posts: 2116
Joined: Wed Apr 21, 2010 8:51 am
Rank: 2d AGA
GD Posts: 1193
KGS: lavalamp
Tygem: imapenguin
IGS: lavalamp
OGS: daniel_the_smith
Location: Silicon Valley
Has thanked: 152 times
Been thanked: 330 times
Contact:

Re: BOINC and brute forcing

Post by daniel_the_smith »

Don't forget, it's possible that white is able to force a triple ko. :mrgreen:
That which can be destroyed by the truth should be.
--
My (sadly neglected, but not forgotten) project: http://dailyjoseki.com
Kirby
Honinbo
Posts: 9553
Joined: Wed Feb 24, 2010 6:04 pm
GD Posts: 0
KGS: Kirby
Tygem: 커비라고해
Has thanked: 1583 times
Been thanked: 1707 times

Re: BOINC and brute forcing

Post by Kirby »

If white can force triple ko:
Forcing triple ko could be an optimal strategy, giving each player a payoff of zero - or it could be the case where a player can force a win (in which case forcing triple ko would not be the best strategy). Either way, an optimal strategy exists.
be immersed
User avatar
palapiku
Lives in sente
Posts: 761
Joined: Sun Apr 25, 2010 11:25 pm
Rank: the k-word
GD Posts: 0
Has thanked: 152 times
Been thanked: 204 times

Re: BOINC and brute forcing

Post by palapiku »

You don't need a triple ko to draw, since optimal strategy where nobody forces triple ko also ends in a draw, by the definition of komi :)

(we just don't know if the komi is greater than zero or not...)
Kirby
Honinbo
Posts: 9553
Joined: Wed Feb 24, 2010 6:04 pm
GD Posts: 0
KGS: Kirby
Tygem: 커비라고해
Has thanked: 1583 times
Been thanked: 1707 times

Re: BOINC and brute forcing

Post by Kirby »

palapiku wrote:You don't need a triple ko to draw, since optimal strategy where nobody forces triple ko also ends in a draw, by the definition of komi :)

(we just don't know if the komi is greater than zero or not...)


I think, to solve go and have an optimal strategy for both players, you need to set the komi to some particular value (could be zero). Then, you can know the best strategy for both players to take, considering that komi.

If the komi has a different value, it could be possible that there's a different optimal strategy for both sides.

A simple example:
Situation A.) Setting komi to X is proven to be a win for black unless white can force a draw with a triple ko situation, for example. So there is some sequence of moves that are best for both players, which will lead to white forcing the triple ko to get the draw.

Situation B.) Now if we set the komi to X+1. Let's say that with X+1 komi, white has the ability to force a win by playing optimally. His strategy must, therefore, change. To get the best result.

In Situation A, the best strategy for both sides leads to a draw. In situation B, the best strategy for both sides leads to a win for white, due to the higher komi.

So to solve go, we must first set a particular komi, and then find a winning strategy with that komi. If we could ever solve the game with that komi, though we have a strategy for that komi, we may need a different set of strategies to solve the game for different komis.

In a sense, having a different komi produces a different game, and leads to potentially different optimal strategies.
be immersed
User avatar
Liisa
Lives with ko
Posts: 129
Joined: Wed Jun 16, 2010 3:30 am
Rank: EGF 1989 KGS 2d
GD Posts: 0
Location: Turku, Finland
Has thanked: 12 times
Been thanked: 21 times
Contact:

Re: BOINC and brute forcing

Post by Liisa »

Kirby, if something is mathematically possible, that does not imply that it is actually possible within the framework of real world. That is because number of objects that are available for us is limited. This is (common) fallacy in reasoning, because people do not distinguish mathematics from reality. This fallacy in reasoning goes back to Leibniz, Galilei and Platon.

Monadology wrote:Perfect play also takes the form of a logical conditional so it cannot be invalidated by a negation of the antecedent, which is all your argument against its existence could potentially manage.


I did refute the idea of logic as a product of your (false) experiences and imagination. Logic is empirically derived from experiences by induction. People have observed several occasions where Jackdaws (Corvus monedula), have done something non-contradictory and thus they have generalized that contradictory events are logically impossible. And they have promoted the principle of contradictions as axiom of logic. And assumed that it is self-evident. But while observing quantum objects this axiom is not self-evident at all.

Go maybe defined as a abstract set of rules, but as soon as you are referring actual games (such as perfect game) it does exist as a natural, real world object. In the case of perfect play, reference is false. E.g. we can say that there is a unicorn, but statement is false.

Quantum phenomena are just as far away from having anything to do with the game of Go as the effectively indeterminable perfect line of play.


Of course it has all to do with the particular games that you have played. individual go games do exist, and you can view them with .sgf editor. That are visible due to quantum phenomena in liquid crystals and your retinal cells.


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.


Problem is that if combinations are meaningful, it is required that we make changes to combinations (e.g. while reading output) and because speed of light limits individual particle's interaction. There is not gained significant increase in orders of magnitudes to the information content of the universe even if relations of particles has considered, because limiting factor will be time. E.g. Jackdaw does include way more information as a whole than it's constituents alone, but still for solving go this is irrelevant.

Liisa wrote:There are two interesting things what we get from quantum logic: A) logic is empirical science. B) mathematics as a science loses meaning.


In the case of A, Logic simply ceases to be anything like actual logic. B, I don't see how this follows at all.


I think that here your reason is that that you do not think that logic that you have learned can be questioned and you assume that logic is a priori truth. But logic is more or less derived from your experiences and therefore correspondence to the real world can be either true or false.

Mathematics loses meaning, because quantum logic (i.e. quantum physics) is inherently probabilistic theory of logic. That will imply that there cannot be anything that is called as truth in mathematical sense, but only highly probable events. Implication is that you can select any sets of mathematical axioms and make logical exercises with them, but they have little to do with real world. Correspondence between real world and mathematics will fail.

The thing that quantum mechanics is formulated using mathematics does not imply that mathematics is build into objects themselves, but they are only tools for humans to calculate probabilities, to make reasoning more simple.

Quantum logic is necessary concept from some reasons: a) it can show that logic is derived ultimately from experiences. b) contemporary logic is poor in handling probabilities and induction and QM is inherently probabilistic theory that has been derived by inductive method.

You are using contemporary logic in claiming (boldly) that empirical theories are not capable for verification. This is the reason why we need case b), because verification is possible within the framework of inherently probabilistic logic, because with probabilistic logic it is required for verification that we calculate only probabilities for the events that we can observe. And we can always calculate probabilities for the events.

Idea with this is that logic is based on assumption that it will generate a world that behaves like observed world. There is no inherent problems in describing flying jackdaw in contemporary logical terms. But there would be some inherent problems, if jackdaws would behave like quantum objects while flying through double slit. If that would be the case, we would have never developed a comtemporary logic, because that would not make any sense in describing observed world.

Quantum logic, however interesting subject by itself, is way off topic!
amnal
Lives in gote
Posts: 589
Joined: Fri Apr 23, 2010 10:42 am
Rank: 2 dan
GD Posts: 0
Been thanked: 114 times

Re: BOINC and brute forcing

Post by amnal »

Liisa wrote:Kirby, if something is mathematically possible, that does not imply that it is actually possible within the framework of real world. That is because number of objects that are available for us is limited. This is (common) fallacy in reasoning, because people do not distinguish mathematics from reality. This fallacy in reasoning goes back to Leibniz, Galilei and Platon.


Even if you were completely correct with everything you say (which you actually really really aren't), Go is essentially a mathematical problem, so I don't see why it shouldn't be solvable. For instance, are you really, seriously telling me that we haven't solved tic tac toe, and that 'quantum logic' may allow a different result?

Monadology wrote:Perfect play also takes the form of a logical conditional so it cannot be invalidated by a negation of the antecedent, which is all your argument against its existence could potentially manage.


I did refute the idea of logic as a product of your (false) experiences and imagination. Logic is empirically derived from experiences by induction. People have observed several occasions where Jackdaws (Corvus monedula), have done something non-contradictory and thus they have generalized that contradictory events are logically impossible. And they have promoted the principle of contradictions as axiom of logic. And assumed that it is self-evident. But while observing quantum objects this axiom is not self-evident at all.


Go is not a quantum object. It's a mathematics problem. Where do you imagine that a breach in our rubbishy old classical logic could occur, it just makes no sense to apply quantum ideas?


Go maybe defined as a abstract set of rules, but as soon as you are referring actual games (such as perfect game) it does exist as a natural, real world object. In the case of perfect play, reference is false. E.g. we can say that there is a unicorn, but statement is false.


This is meaningless! Just meaningless! What difference does it make to the abstract logic of the set of rules if you actually put some bits of rock on a piece of wood? The only thing I can imagine is that you think it's relevant that technically the board could spontaneously disappear or something.

Quantum phenomena are just as far away from having anything to do with the game of Go as the effectively indeterminable perfect line of play.


Of course it has all to do with the particular games that you have played. individual go games do exist, and you can view them with .sgf editor. That are visible due to quantum phenomena in liquid crystals and your retinal cells.


This makes me think that maybe your argument really is 'quantum effects could move the stones around or something'. Which still makes no difference to the abstract game logic.



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.


Problem is that if combinations are meaningful, it is required that we make changes to combinations (e.g. while reading output) and because speed of light limits individual particle's interaction. There is not gained significant increase in orders of magnitudes to the information content of the universe even if relations of particles has considered, because limiting factor will be time. E.g. Jackdaw does include way more information as a whole than it's constituents alone, but still for solving go this is irrelevant.



I can't work out what you're trying to say here. 'It would take a long time to express this, therefore it does not exist'?



...
[more rambling]
...


I don't really know what else to say. Maybe I've fundamentally misunderstood what's going on, and Liisa is actually making a profound point. I look forward to working out what it is...
User avatar
Liisa
Lives with ko
Posts: 129
Joined: Wed Jun 16, 2010 3:30 am
Rank: EGF 1989 KGS 2d
GD Posts: 0
Location: Turku, Finland
Has thanked: 12 times
Been thanked: 21 times
Contact:

Re: BOINC and brute forcing

Post by Liisa »

amnal wrote:Maybe I've fundamentally misunderstood what's going on, and Liisa is actually making a profound point. I look forward to working out what it is...


My profound point is that it is meaningless to think abstract solution, if it is impossible to make it be actual game that can be in practice play out on real goban. And here I refer what is practical for type 4 civilization. We Earthlings are currently type ca. 0.7 civilization.

In other words, we must separate mathematical concepts from actual world.

It is meaningless to say that solving go is in principle possible, but in practice "very difficult". That is because, in nature there is no principles, but all the Great Principles are products of human imagination (with truth value false). We do not have God's eye point of view to see hand of god, because we are living in very finite universe. People just loses track how big number's are when we approach the googol. In practice very difficult problems, which information content would require bigger amount of bits than googol, are just impossible and they round up to the infinity.

It is useful concept to understand how big is practical infinity. In practice, practical infinity behaves similarly as mathematical infinity, but is just smaller in size. If people get annoyed using infinity in practical sense, we can always replace say that infinity equals absurdity.
Last edited by Liisa on Mon Sep 06, 2010 4:42 pm, edited 1 time in total.
User avatar
emeraldemon
Gosei
Posts: 1744
Joined: Sun May 02, 2010 1:33 pm
GD Posts: 0
KGS: greendemon
Tygem: greendemon
DGS: smaragdaemon
OGS: emeraldemon
Has thanked: 697 times
Been thanked: 287 times

Re: BOINC and brute forcing

Post by emeraldemon »

Going all the way back to the original post, I have no idea how hard it is to run BOINC or what it takes, but I'd be very curious to try and see what we could solve for smaller board sizes. 2x2 Tromp Taylor rules can be solved easily and quickly on a single machine (http://homepages.cwi.nl/~tromp/java/go/twoxtwo.html), so we could start there and work our way up. If we could solve 7x7 say, that would be a pretty cool accomplishment. Is anyone else interested in such a project?
User avatar
Monadology
Lives in gote
Posts: 388
Joined: Wed Jun 23, 2010 1:26 pm
Rank: KGS 7 kyu
GD Posts: 0
KGS: Krill
OGS: Krill
Location: Riverside CA
Has thanked: 246 times
Been thanked: 79 times

Re: BOINC and brute forcing

Post by Monadology »

I would like to discuss things further with you, Liisa. Unfortunately, trying to argue with you over the tenability of radical empiricism is probably going to lead way off the beaten path.

If you'd like to continue via PM, send me one. Alternately, we could make an thread in the Off-Topic board.
Kirby
Honinbo
Posts: 9553
Joined: Wed Feb 24, 2010 6:04 pm
GD Posts: 0
KGS: Kirby
Tygem: 커비라고해
Has thanked: 1583 times
Been thanked: 1707 times

Re: BOINC and brute forcing

Post by Kirby »

Liisa wrote:...
My profound point is that it is meaningless to think abstract solution, if it is impossible to make it be actual game that can be in practice play out on real goban. And here I refer what is practical for type 4 civilization. We Earthlings are currently type ca. 0.7 civilization.

...


It is not meaningless to think of an abstract solution, because that is the first step to making an actual game that can be in practice played out on a real goban. That is what solving the game is about - being able to have a real strategy that you can use in practice (except in the case of "weakly solving" the game, in which you just prove who wins).

So the "solving" we are talking about means finding a strategy for both players that is practically implementable, and that can be played on the go board once it is known.

And because of John Nash and others, we know that this is possible to do.

---

Now, if you are going to talk about uncertainty, of course everything that you know has some degree of certainty. But I don't think that you'll get very far arguing against people if that's your only basis for argument.

It may be well known that you are sitting in a chair right now (if you are, for example), but you only can know this to some degree of certainty. You have some degree of uncertainty in which you are trusting your senses, etc. That's how it is with everything. Yes, we aren't God, so we can't know anything for sure.

But to make an assertion about ANYTHING, you must accept this uncertainty and say something with some degree of confidence. Within a closed, mathematical system we can make statements about what we think is true. We believe these things to be true because of the idea of logic. We may be wrong about our conceptions of logic, but the idea of rationality has to start somewhere.

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.
be immersed
User avatar
Liisa
Lives with ko
Posts: 129
Joined: Wed Jun 16, 2010 3:30 am
Rank: EGF 1989 KGS 2d
GD Posts: 0
Location: Turku, Finland
Has thanked: 12 times
Been thanked: 21 times
Contact:

Re: BOINC and brute forcing

Post by Liisa »

I started new thread that deals more with the nature of logic. Reply's about mathematics and empiricism goes there and and Boinc discussion in particular shall continue here.

http://lifein19x19.com/forum/viewtopic.php?f=8&t=1579
User avatar
Liisa
Lives with ko
Posts: 129
Joined: Wed Jun 16, 2010 3:30 am
Rank: EGF 1989 KGS 2d
GD Posts: 0
Location: Turku, Finland
Has thanked: 12 times
Been thanked: 21 times
Contact:

Re: BOINC and brute forcing

Post by Liisa »

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.

Perhaps ultra-weak solution is plausible, if it does not require knowledge from end position.
Last edited by Liisa on Mon Sep 06, 2010 5:43 pm, edited 1 time in total.
Post Reply