BOINC and brute forcing

[Enink]

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.

[hyperpape]

Nope: http://senseis.xmp.net/?NumberOfPossibleGoGames.

[daniel_the_smith]

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.

[xed_over]

so, does that mean that SETI should not be searching for extraterrestrials, because there are too many possibilities?

[Monadology]

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).

[Kirby]

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

[xed_over]

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.

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.

[Monadology]

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.

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.

[daniel_the_smith]

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.

[Enink]

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.

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?

[Monadology]

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.

[Kirby]

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

[xed_over]

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?

[Monadology]

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.

[Kirby]

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.