Forum for Computer Go
Obsolete and Incorrect [#2910]
Should we take out obsolete stuff like 1995? That's 18 years ago. We should focus on the last 5 years. In the last 5 years, programs went from 1 kyu to 6 dan. Should we take out incorrect stuff like chess programs use brute force? Cell phones running chess programs search 20k positions and play at world champion level. A brute force chess program would have the same problem as a brute force go program. Chess programs are selective just like go programs. Chess and go are in the same game complexity class, exptime complete. Mark Schreiber 7/18/2013 3:54:05 PM
Sure, by all means! It is a wiki, feel free to edit the page with more up to date information.
If you see incorrect information, then please feel free to correct it.
Historic documentation of go is one of the main purposes of this wiki. If you wish to organize or update a page in a way that discusses recent history first, then consider a way in which you can rewrite or move the older history to another section or page.
You are totally incorrect comparing compexity of go to complexity of chess.The further is much more complex(considering 19x19 board).Go programs on 9x9 board have stenght close to pro(or equal to low pro) - have beaten pros many times on equal.If what you said would be true then on 19x19 go programs would win on black no komi enough of games and even win some of equal games - but its not true, on 19x19 go programs are about 3 stones weaker than top pros.Methematically complexity of chess are more or less equal to complexity of go on 9x9 board and this is it - chess programs are about level of top players(of course its estimation, less time computers are better , more time human have much more chances but its another story).Computers programs use MC method with some eliminations and others tricks, chess programs dont use MC, mostly brute force( with some eliminations and so on) - but none of programs is even inch to sth like AI.A pure brute force chess programs running on supercomputer (or even just a big cluster of 8 strong computers) would be easy on gm level(add him advanced table of nalimov and he cant make a bad move in such a endgame and he will be able to evaluate actual position knowing the result of the possible ending - to contrary even best masters like Capablanca are gulty of making errors in known rook ending:
![[ext]](images/extlink.gif)
http://www.chessgames.com/perl/chessgame?gid=1258259
Capablanca in rook ending made many mistakes, his opponent to, and at the end he won game which was draw many times.
Even brute chess program would be master in openings, go programs are so bad at openings that even KGS 3d have better fuseki.But in chess computers openings are top class.
Saying brute chess program would have same problems as brute go program is wrong.On poor hardware its obvious, at the beggining chess programs had depth of 3 moves and sometimes programmers would declare loss of his program to avoid further humilitation of his product.But when hardware was able to compute milions of postions per second strenght of programs exploded.On 386 i was able to beat one of chess program quite easily, but on pentium 166 he beats me easily(althought time settings was in favor of program, on normal tournament setting i would do better although i dont think i would score at plus).
Coincident?I dont think so
I do not understand a lot of what you said because of the spelling, grammar and missing word mistakes. I will try to answer as best as I understand you. We compare complexity of go to complexity of chess. They are both numbers measuring the same thing. Both chess and go are in the same game complexity class, exptime complete. Go has a state space complexity of 10^171. Chess has a state space complexity of 10^47. I do not see why you bring in 9x9 go. I agree that go programs are about 3 stones weaker than some pros on a 19x19 board. We need to define brute force. What is brute force? Brute force is searching through all possible moves. Therefore, no current chess program uses brute force. You are right chess programs do not use MC. I would not include opening book or endgame database in a brute force program. Currently a large opening book and an endgame database could not be created using brute force methods. Why do you mention a supercomputer? All top chess program use computer that you would find a home to achieve their results. Even a super computer would only see 4 moves ahead in over an hour. 4 moves would be less than a master player.
Again i cant agree with you.You said: "Currently a large opening book and an endgame database could not be created using brute force methods." This is false.All openings book are made through joint analysis of GMs with aid of programs.But not all endgames databases. Nalimov tables was made only by brute force analysis(thats why they are 100% free of mistakes). Another thing: same complexity and same complexity class(exptime complete)) - its not same thing, you agree its different? The only one thing i agree we need to define brute force.I was meant no just pure brute force(as you truly mentioned computer even with super opening book and Nalimovs tables would be weak(4 moves depth is not enough)).But if you add not so complicated features like eliminations of moves which will fail almost sure, etc. computer progam would become easily over GMs. The point of computer chess is that on poor hardware they would have no chance to beat world champion.I agree that in developing programs, code is much more important than hardware, but without good hardware(i mean sth more than pentium 1) there is no chance now to compete with tops.
Once you use a program to help a GM with creating an opening book then you are using selective search and not brute force search to creating the opening book. Endgame tablebases would be allowed. If we are not talking about "pure" brute force but brute force then brute force will also work in go. We see Monte Carlo Tree Search in go programs is a fast game played with random moves, the opposite of heuristics, from a starting position to the end of the game, a kind of brute force. However, heuristics plays a minor role in chess. Heuristics plays a minor role in go today. Heuristics will play a minor role in go in the future. What do you mean "same complexity and same complexity class (exptime complete)) - it's not same thing"? Both chess and go are in the same game complexity class, exptime complete. Go has a state space complexity of 10^171. Chess has a state space complexity of 10^47. Go has a much higher state space complexity so go is much harder for the computer.
My sense is that alpha beta search is often referred to as being brute-force. It's true that it's not literal brute force, since many branches of the tree are culled, but it's not particularly sophisticated, which leads to people referring to it as "brute force". However, I'm not sure if it makes sense to distinguish Go and chess on this axis. Go programs don't use alpha-beta search, but also work by building a large tree. They primarily differ by evaluation strategy. --Hyperpape
Alpha beta is not sophisticated. However, chess programs use much more than just alpha beta. Therefore, chess programs are sophisticated and not just brute force. I can imagine in 20 years go programs defeat the top go professionals. Some people will say the go programs are using MC, brute force not AI.
I must admit that i made a mistake reading your post, i thought sth that you didnt writed.You used word "selective" where i readed "complex"(lol my mind :). So i think now we both can agree that: Class of complex is same - exptime complete. Number of possibilities are much higher in go than in chess. So part of our discussion was pointless due to mine mistake.
At first post u make statement: "go programs are selective just like chess programs" - this is i dont agree. "Cell phones running chess programs search 20k positions and play at world champion level" - there is no kuy in chess, and this is sth like i cant agree too.If u meant 20k = 20000 postions/sec, then its a bit suspicious, but even with this it means that cell phone can evaluate 1.2m of positions in one minute - how many human can? Beside cell phones has now quite powerfull CPU, much more powerfull than computer which beated Kasparov in blitz(or maybe it was 20 mins dont remember expactly).
What is "sth"? What do mean, "there is no kuy in chess"?
hey mschribr, two notes. First, Zen19d briefly reached 6d in its latest iteration but 5d is the only rank it has held in a stable way. I want to state (uncontroversially and conservatively) that Zen has a 5d rank on KG, and then provide details for the curious in a separate section. Second, all the crap about the computational complexity of Go should be in a _different_ section from "Historical Background". I see historical background as a chance to explain the historical difficulties go programmers have faced, for someone who hasn't been following. Make a separate section (or better yet, a separate page) to discuss the computational complexity of Go. ~~172
If the program was not stable, it would not have gotten a 6 dan rating. Therefore, when it received it, it was stable. Therefore, it did reach 6d. Right now, it is only a tiny bit below 6. But uncontroversially, it did reach 6d. The computational complexity is to explain why computers are better at chess and other games than at go. Many people claim if a computer beat the best go player then we would have AI. But, beating the best chess player is only brute force. Computational complexity easily explains why that reasoning is crap.
Do you understand what "stable" means when people talk about Go rankings? When you hold a rank for a few hours, we don't call it stable. If you want to add random-ass victories against amateurs with Tygem accounts, put it down in the section I added on the "strongest go programs"
Zen was 6 dan for more than a few hours. If you win 1 or 2 games that is random-ass victories. If you receive a rating that means you won more than few a games. In fact, you have won enough games and you are stable enough to receive a rating. Zen was 6 dan. Beating a current Tygem 9 dan is better than beating a player who was 9 dan 30 years ago. We do not know how strong he was when he played the computer.
hey 172.0.9.139, Did you know Zen was a 6 dan on KGS in March 2012?
![[Welcome to Sensei's Library!]](images/stone-hello.png "Sensei's Library")