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

BOINC and brute forcing
http://www.lifein19x19.com/viewtopic.php?f=18&t=1538		 Page 1 of 4
Author:  Enink [ Wed Sep 01, 2010 2:38 pm ]
Post subject:  BOINC and brute forcing
So first of all, I don't really know much about programming for go or programming in general. But, I recently started running BOINC for Einstein@Home (pulsars!) and was thinking about that idea (as I understand it) of using the processing of home computers for a major processing project.

So basically, my understanding of programming a go AI is that brute forcing it is just highly unrealistic and so we have to take other approaches. However, could we create a brute force analytical program that uses BOINC to get the processing power/time to simply go through every possibility?

So once again, I don't really know anything about programming but I was just thinking about it, and would appreciate your responses, even if it's just to point out the obvious CS reason why it doesn't work.
Author:  hyperpape [ Wed Sep 01, 2010 2:40 pm ]
Post subject:  Re: BOINC and brute forcing
Nope: http://senseis.xmp.net/?NumberOfPossibleGoGames.
Author:  daniel_the_smith [ Wed Sep 01, 2010 3:03 pm ]
Post subject:  Re: BOINC and brute forcing
Brute-forcing 19x19 go is probably not possible even if you had all the resources of the universe at your disposal, the numbers are that big.

9x9 might be possible eventually.
Author:  xed_over [ Wed Sep 01, 2010 3:14 pm ]
Post subject:  Re: BOINC and brute forcing
so, does that mean that SETI should not be searching for extraterrestrials, because there are too many possibilities?
Author:  Monadology [ Wed Sep 01, 2010 3:21 pm ]
Post subject:  Re: BOINC and brute forcing
xed_over wrote:
so, does that mean that SETI should not be searching for extraterrestrials, because there are too many possibilities?


There is a very different method involved. Go won't be solved until EVERY possibility is tried (or at least an exceedingly, exceedingly large number of possibilities).

SETI just has to keep going until it detects something. It's more like throwing dice. Sure the odds might be massive, but every time you roll them there's an equal chance the result will come up and when it does, then you're done (or at least have one success).
Author:  Kirby [ Wed Sep 01, 2010 3:35 pm ]
Post subject:  Re: BOINC and brute forcing
Hsu, a guy that was involved with deep blue, believes that the answer to go is brute force. He said that people didn't believe that it could be done with chess, but it was. That's because computers are good with brute force.

Some people think that Hsu is crazy. But he did contribute to deep blue.

Here's some background on what I'm talking about:
http://spectrum.ieee.org/computing/software/cracking-go
Author:  xed_over [ Wed Sep 01, 2010 3:52 pm ]
Post subject:  Re: BOINC and brute forcing
Monadology wrote:
There is a very different method involved. Go won't be solved until EVERY possibility is tried (or at least an exceedingly, exceedingly large number of possibilities).

I'm with Hsu. As the article in Kirby's link points out, its actually not necessary to try EVERY possibility.

Monadology wrote:
SETI just has to keep going until it detects something. It's more like throwing dice. Sure the odds might be massive, but every time you roll them there's an equal chance the result will come up and when it does, then you're done (or at least have one success).

I'm off to buy a lottery ticket now.
Author:  Monadology [ Wed Sep 01, 2010 4:04 pm ]
Post subject:  Re: BOINC and brute forcing
xed_over wrote:
Monadology wrote:
SETI just has to keep going until it detects something. It's more like throwing dice. Sure the odds might be massive, but every time you roll them there's an equal chance the result will come up and when it does, then you're done (or at least have one success).

I'm off to buy a lottery ticket now.


:roll:

EDIT: Finished the article, so I can remark on the first part of your post.

First we need to be clear: are we talking about solving Go or simply making a computer which can beat any human player? The article was talking about the latter which requires a lot less than the former, as indicated by the fact that Chess is not solved but we have long since made very strong computers. I was talking about solving Go. I even use the word "solved" in my post.
Author:  daniel_the_smith [ Wed Sep 01, 2010 4:20 pm ]
Post subject:  Re: BOINC and brute forcing
Brute-forcing go well enough to beat humans is probably possible in the not-too-distant future, but it's nothing like actually solving the game, which is what I was talking about.
Author:  Enink [ Wed Sep 01, 2010 4:32 pm ]
Post subject:  Re: BOINC and brute forcing
Monadology wrote:
xed_over wrote:
Monadology wrote:
SETI just has to keep going until it detects something. It's more like throwing dice. Sure the odds might be massive, but every time you roll them there's an equal chance the result will come up and when it does, then you're done (or at least have one success).

I'm off to buy a lottery ticket now.


:roll:

EDIT: Finished the article, so I can remarked on the first part of your post.

First we need to be clear: are we talking about solving Go or simply making a computer which can beat any human player? The article was talking about the latter which requires a lot less than the former, as indicated by the fact that Chess is not solved but we have long since made very strong computers. I was talking about solving Go. I even use the word "solved" in my post.


Maybe we are (or should be) talking about both? I was probably originally talking about either, probably the more obtainable of the two (although I'd totally buy into the argument that unless it's "solved" you can't really say that it could beat any human player ever in all possible worlds, including the world of go savants, so if you tried me I'd jump on the "solving" band wagon). But the point here is, the general thought is that brute forcing is not a valid way of developing a go playing AI. So, do you think "solving" is an essential part of that goal? I'd say that we're looking to attain the same level we have with Chess, at least to start with, although that is quite a debatable point. Ultimately, then, if one is attainable and the other isn't, there isn't much point in discussing the impossible (or more far off anyway) one. That even "able to beat any human" is attainable through brute force is certainly still contestable.


EDIT: in light of other posts in the meantime. Okay, even if we are talking about solving, what exactly makes solving go by brute force so much different than having it learn to beat people that way?
Author:  Monadology [ Wed Sep 01, 2010 4:42 pm ]
Post subject:  Re: BOINC and brute forcing
Enink wrote:
EDIT: in light of other posts in the meantime. Okay, even if we are talking about solving, what exactly makes solving go by brute force so much different than having it learn to beat people that way?


Because for all we know, humans have been playing Go horribly for millenia and making a computer that can beat us at it doesn't mean the computer is at all close to perfect play. We won't know that for sure, which we need to to solve it, until all of the possibilities (or at least a very large number) have been processed.

Consider the fact that in terms of opening moves we have no idea what is optimal. Even if we exclude anything below the third line, we still have to solve it for the remaining 289 possibilities. When a computer is actually playing against an opponent every other move will require no selection on the part of the computer. Further, it will not need to read out every other possible move to beat the human opponent and many of the pruning methods can be applied.

EDIT: Actually, thanks to symmetry it would only be about a quarter of 289? Still, as play proceeded symmetry would no longer apply and there would still be a pretty vast number of plays and their branches in the sparse opening game.
Author:  Kirby [ Wed Sep 01, 2010 4:58 pm ]
Post subject:  Re: BOINC and brute forcing
Enink wrote:
...
EDIT: in light of other posts in the meantime. Okay, even if we are talking about solving, what exactly makes solving go by brute force so much different than having it learn to beat people that way?


People do not play optimally. "Solving" a game in a game theoretical sense has a specific meaning. There's actually a couple of different categories of solving games:

Ultra-weakly solved game: You can prove the status of the game. In the case of go, this would mean proving that black has a winning strategy from the beginning of the game, white has a winning strategy, or that if both play optimally, it will be a draw. Having an "ultra-weak" solution doesn't mean you actually have to have a strategy - just that you can prove the status.

Weakly solved game: You have identified an algorithm that plays optimally. In the case of go, this means having an algorithm that will play without making any mistakes from the start of the game. This is different than just winning against any human. It means being able to play perfectly against ANY line of play.

Strongly solved game: This is the same as a weakly solved game, except that the algorithm can play perfectly from any board position. In the case of go, this means giving a board position, and it will determine optimal play for the remainder of the game.

Checkers is the most complicated game that I know of that has been weakly solved.
Author:  xed_over [ Wed Sep 01, 2010 5:03 pm ]
Post subject:  Re: BOINC and brute forcing
Is it actually necessary to plug in each and every possible value into all the variables of an equation in order to prove (solve) a given mathematical theorem?

What does it mean to solve Go? Isn't it to find the best possible move(s) for both sides?

If it can be proven early enough that a black 1st move on the 1-1 point will not be black's best move, then can't we at some point trim that tree without having to actually try each and every permutation along that same line? Do we really think that a sacrifice by black that early in the game can possibly lead to black's best game?

So I don't think the brute force numbers are quite as large as everyone fears (they are still quite large, though)

If the last digit in a really, really large number is a 0,2,4,5,6, or 8, then I can tell you that number is not a prime number. Now there are still a lot of other tests to try, but we've just eliminated an even larger chunk without having to "brute force" each and every value. And yet proving/disproving the number is prime will still be considered a brute force effort, no?
Author:  Monadology [ Wed Sep 01, 2010 5:15 pm ]
Post subject:  Re: BOINC and brute forcing
xed_over wrote:
Is it actually necessary to plug in each and every possible value into all the variables of an equation in order to prove (solve) a given mathematical theorem?


Game theory and mathematical theorems work differently sometimes I reckon. Fermat's Last Theorem if it has a proof (we have one currently that I don't think has been shown to be wrong at this point, but it pays to be cautious) it will not require plugging in every variable because that would require processing an infinite number of variables.

I don't know that a game is susceptible to a similar 'proof', because I don't think it can be reduced to a form susceptible to Reductio Ad Absurdum proof (for instance).

But I really don't know enough about game theory to say. All I know is a good number of the experts think that solving Chess is out of the question without a serious leap in technological possibilities that we can't be sure will happen. And I would find it odd if they were working on the assumption that every single value has to be plugged in unless it's truly necessary.
Author:  Kirby [ Wed Sep 01, 2010 5:31 pm ]
Post subject:  Re: BOINC and brute forcing
Proof does not require testing of all possible inputs, but must provide clarity that it will work with any input.

If the proof leaves room for the possibility of being wrong, it is not a proof.
Author:  Liisa [ Wed Sep 01, 2010 6:08 pm ]
Post subject:  Re: BOINC and brute forcing
Kirby wrote:
Some people think that Hsu is crazy.


I bet €1000 that he is crazy. :D
Author:  daniel_the_smith [ Wed Sep 01, 2010 6:27 pm ]
Post subject:  Re: BOINC and brute forcing
xed_over wrote:
If the last digit in a really, really large number is a 0,2,4,5,6, or 8, then I can tell you that number is not a prime number. Now there are still a lot of other tests to try, but we've just eliminated an even larger chunk without having to "brute force" each and every value. And yet proving/disproving the number is prime will still be considered a brute force effort, no?


That is actually a pretty good analogy. Every "https" secure website *depends* on the fact that sufficiently large numbers are impossible to factor given current computation limits. In the same way that eliminating even numbers doesn't significantly alter the time it takes to factor a huge number, eliminating known bad moves doesn't gain you more than a few orders of magnitude* towards solving go. If you go with the number of possible games from sensei's, 10^800, -- say you manage to eliminate 99.99999% of possible games right off the top-- that leaves you with 10^795 games still to check by hand, an impossibly large number.


*from memory. Somewhere there is a paper written by the guys who solved 6x7 go (I think that's the largest solved board). In it they go into detail about all the tricks they used to make it possible.
Author:  hyperpape [ Wed Sep 01, 2010 8:59 pm ]
Post subject:  Re: BOINC and brute forcing
Just to be clear, testing primality is not quite so difficult (http://en.wikipedia.org/wiki/Primality_test). It's factoring that is (afaik) still in the realm of brute force approaches.

As for Hsu, there's interesting stuff in that article, but I don't know if he has the target properly in mind. He's talking about searching 12 plies deep, but that's quite small for professionals. Unless I misread, all the optimizations he's describing wouldn't even approach what you'd need to have to play at a high level.
Author:  Liisa [ Thu Sep 02, 2010 3:48 am ]
Post subject:  Re: BOINC and brute forcing
hyperpape wrote:
As for Hsu, there's interesting stuff in that article, but I don't know if he has the target properly in mind. He's talking about searching 12 plies deep, but that's quite small for professionals.


Also, 12 plies deep is not sufficient to any SDK player. My record in exact reading ahead in DGS was 64 plies ahead and it took little less than 2 hours. And humans do not even need to be exact in reading because it is sufficient to find good enough sequence.

Go is interesting that it is meaningless to search trees ahead for a few moves, because unlike in Chess, it is impossible to score positions by any reasonable accuracy. This is the reason why Monte Carlo search is 5 stones better than any other approaches, because at least it tries to think game as a whole and look the end position. For humans this kind of inaccurate reasoning is natural, but it is difficult for computer without genuinely new ideas for either brute force algorithms or AI.

But for the topic, I would think that BOINC search would be interesting. Then we would get cheap super computer so that we could monitor the inevitable defeat of Human by Machine. I just think that we won't see it within this century. I think that it is not problematic to gather 1000 PC for the BOINC calculations, but more difficult it is to find a person, who is familiar with BOINC calculation AND gobot programming AND who has motivation for the project.
Author:  Phelan [ Thu Sep 02, 2010 4:09 am ]
Post subject:  Re: BOINC and brute forcing
I would install and run a BOINC go solving program. It might not lead to much, but I find the subject interesting.

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