BOINC and brute forcing

[Liisa]

Some people think that Hsu is crazy.

I bet €1000 that he is crazy.

[daniel_the_smith]

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.

[hyperpape]

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.

[Liisa]

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.

[Phelan]

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

[tj86430]

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.

Does the algorithm have to be implementable? If not, then brute-force approach to go is such an algorithm. It would most certainly play perfectly, if it was implementable.

[Kirby]

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.

Does the algorithm have to be implementable? If not, then brute-force approach to go is such an algorithm. It would most certainly play perfectly, if it was implementable.

Yes. For any finitely-positioned two-person game you could used brute force, but since it would cost an infeasible amount of time, something's not considered strongly or weakly solved unless it can be run by existing hardware in a reasonable amount of time (ie. you should implement the algorithm to prove you've solved the game).

[willemien]

Yes. For any finitely-positioned two-person game you could used brute force, but since it would cost an infeasible amount of time, something's not considered strongly or weakly solved unless it can be run by existing hardware in a reasonable amount of time (ie. you should implement the algorithm to prove you've solved the game).

Hm under these conditions you can hardly call checkers solved...
(It took 10 years and an big number of computers) something that can hardly be called "existing hardware in a reasonable amount of time"

But there is now a database and a program that uses it see http://webdocs.cs.ualberta.ca/~chinook/

I am not even sure that the proof (all positions and values) is even still available ( where do you store all the data. most of it is just reconstructable (but even that can take some time)

[hyperpape]

Well, reasonable differs depending on the purpose. For the sake of demonstration, ten years on top notch hardware is often perfectly reasonable.

[John Fairbairn]

One thing that surprised me a little about the draughts work is that it said perfect play is proven to end in a draw. Does this have any implications for go, where we, perhaps blithely, always assume Black has a big advantage and so should always win?

[Monadology]

One thing that surprised me a little about the draughts work is that it said perfect play is proven to end in a draw. Does this have any implications for go, where we, perhaps blithely, always assume Black has a big advantage and so should always win?

One potential relevant difference is the presence of a center point in Go which is not present in draughts.

Of course we have no idea if it plays any important part in perfect play, but it at least breaks up the symmetry enough that I'd say it's at least a little less likely that perfect play in Go will lead to a draw (barring Komi of course).

[willemien]

One thing that surprised me a little about the draughts work is that it said perfect play is proven to end in a draw. Does this have any implications for go, where we, perhaps blithely, always assume Black has a big advantage and so should always win?

I think in Go it will work the other way around.

The komi depends on the result.

If with 7.5 points komi optimal play leads to a half point win for white the proper komi is 7 (and so the result for optimal game becomes a draw)

For example on 7x7 go probable optimal play with 6.5 komi leads to a 2.5 points win for black.

Thereforethe probable perfect komi for 7x7 is 9 points (an not the other way around)

Unfortunedly it s not in our lifetime that 19x19 will be solved and therefore we the proper komi can not be established. but maybe our grand grand grand [add a couple to a couple of dozen more] grand children will now it.
(but I hop they will still like to play go)

[Kirby]

One thing that surprised me a little about the draughts work is that it said perfect play is proven to end in a draw. Does this have any implications for go, where we, perhaps blithely, always assume Black has a big advantage and so should always win?

We can control who has the advantage with komi.

It would be very interesting if, having a komi of 0, perfect play resulted in a draw for go.

[Cassandra]

It would be very interesting if, having a komi of 0, perfect play resulted in a draw for go.

Because Komi has grown over time, it is very, very unlikely that your assumption will become true.

[Kirby]

It would be very interesting if, having a komi of 0, perfect play resulted in a draw for go.

Because Komi has grown over time, it is very, very unlikely that your assumption will become true.

Agreed, but we cannot know until it's been proven, really. The growth of komi may have to do with psychological factors - or simply with the way that humans play the game.

I wonder, in the case of draughts/checkers, was it believed that the first player had the advantage before it was proven to be a draw with optimal play?