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.

_________________
Offending ad removed

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

_________________
be immersed

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)

_________________
Promotor and Librarian of Sensei's Library

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

_________________
Occupy Babel!

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

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)

_________________
Promotor and Librarian of Sensei's Library

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.

_________________
be immersed

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

_________________
The really most difficult Go problem ever: https://igohatsuyoron120.de/index.htm
Igo Hatsuyōron #120 (really solved by KataGo)

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?

_________________
be immersed

Perfect play is an irrational concept. It is not meaningful to speak from perfect play, because there does not exist any absolute mathematical concepts (such as perfect play) in nature. Everything that exist does exist only as a construction of particular things (such as atoms) that are defined only in probabilistic sense.

This is curious and interesting point and most people assume opposite to be the Truth.

I would like to suggest also returning to earth from higher worlds while discussing. It is sometimes healthy.

Isn't it possible, within a closed system to have a strategy that will guarantee the best result?

_________________
be immersed

Go is not nature. Go is an artificially constructed finite game and atoms have nothing to do with it. 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.




You're equally guilty of this. 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.

We live in very closed system (universe) and it it's size is extremely limited compared to solution for go. In other words, perfect play does not fit to this universe or multiverse, what ever. It is too big.

I think that the reason for this is that you need knowledge from end position in order to play perfectly.

I suppose that this in not comparable to Go.

In Draughts / Checkers - as in Chess - aim is (total) destruction of the opponent's pieces. The players want to destroy something. In Go you have to build up.

In Go you cannot reach a draw with only preventing your stones being captured. You have to create territory as well.

Let's assume that Go without Komi would have results with a mean value something about 6 to 8 points for Black. 7 points equal 2 percent of the Go-board.
With this compensation (and with "perfect" play) Tagaisen would not be necessary any more.
Without "perfect" play, the significance of Tagaisen will increase dramatically.

It is said that Shusaku won every game with Black. It is a clear sign that Komi is necessary, because even he did not win every game with White.

Let's compare this with checkers or chess (and leave aside the different nature of the games). Even if the player moving first would win over 50% of the games in the average. What will you do ?
Apparently this difference does not equal the value of one piece in checkers or one pawn in chess. So it is impossible to adjust the starting position to make up for this one-sided advantage (1 piece in checkers is 5% of the players pieces). And after the end of these games there is no room for compensation either.

Compensation in Go is possible, because the aim is so comparatively small - just one of 361 points.

_________________
The really most difficult Go problem ever: https://igohatsuyoron120.de/index.htm
Igo Hatsuyōron #120 (really solved by KataGo)

Well, go is complex for sure. But it is still a finite two person game. And for any such game, it is possible to find an optimal strategy. It just might take a very, very long time with go.

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.

_________________
be immersed

so many people are stunned by the number of possibile game go can have but if we can build good program that will eleminate bad moves then it might be possible to solve go. that is just my opinion....

_________________
"The more we think we know about
The greater the unknown"
Words by neil peart, music by geddy lee and alex lifeson

As far as I can tell, this post is completely meaningless. Will you tell me tic-tac-toe cannot be sure to end in a draw with perfect play? The same (invalid) logic would apply.

That is not so. Most people are like you that they do not have much of sense for orders of magnitudes. Also they do not have clear definition for infinite, and in general they cannot distinguish mathematics and reality. From realistic standpoint, and that is only meaningful standpoint, we cannot have objects whats extent is bigger than universe (infinite equals absurd). And problem is that if you try to strip bad plays away from perfect play, you need much bigger recycle bin than you currently have. This was also commented that it does not do much, if you strip most of the bad variations away. You still have from realistic standpoint infinite amount of possibilities left. The same goes for Chess and every other complex systems, not just for Go. World is full of complex systems. It is exactly as impossible to solve go as to solve weather patterns for the next 100 years.

It seems that Amnal does not like to read much what is the topic of the forum, before writing. Suits her.

I can't help but be a little irked by the many people who invoke system dynamics and chaos theory as a sort of general metaphor for things being strange. There are some great mathematical proofs showing that certain classes of systems, such as systems of differential equations or finite difference maps like the logistic map, are very difficult to predict. This is meant in a concrete way: differences in initial state create exponential divergence in paths over time (read about the Lyapunov exponent if you're curious).

But those systems have a very important property: the state space is INFINITE. NO result from chaos theory could possibly apply to go, because the state space is FINITE. There are no strange attractors in go, no butterflies flapping wings etc. etc. At best one could perhaps imagine a go as a low-fidelity approximation to an infinite space, and try to prove that some chaotic attractor of the underlying infinite space shows itself in some way in the finite approximation. If you could prove something like that, we would all be amazed and you could publish in a very respectable journal.

As many people have pointed out, go is finite, and thus solveable by alpha-beta search in finite time. Many of these people have also pointed out that such a brute force search would take more time and space than we will ever have available. Does that mean there's no hope? No.

I'd like to make an analogy to the Traveling Salesman Problem. The problem is quite simple: you have a set of cities, and you wish to visit them in the shortest total travel distance. There is no algorithm that can exactly solve TSP without needing exponential time (unless P=NP). Not so long ago solving 30 city problems was an enormous task. But approximation methods and heuristics have gotten much better, and now researchers routinely solve problems with thousands of cities. By making good guesses and avoiding the worst case, many problems can be solved quickly.

As an undergrad, a professor told me something very helpful once: If you're trying to prove "This cannot be done", it's not enough to say "I tried very hard and couldn't do it".