Not logged inRybka Chess Community Forum
Up Topic The Rybka Lounge / Computer Chess / Computer Shogi and Go
- - By tasdourian (**) Date 2007-08-30 04:59
Although I'm assuming Larry is the most informed about this (being a US Shogi champion), I'm of course interested if anyone (including Larry!) knows about the current strength of Shogi and Go programs.  The part of Wikipedia's entry on Shogi and computer programs was self-contradictory, and thus not helpful.  I would assume, of course, that Shogi would be much closer to chess in terms of what a computer would have to do to play well. Anyway, what is the state of the art?
Parent - - By lkaufman (*****) Date 2007-08-30 05:17
In shogi, the best pc program now is about the level of an apprentice pro (like Pro 2 Dan), which in chess terms would probably be strong IM or weak GM level. In rapid play they are already on the level of top pros. The rate of improvement is quite impressive, and I think it won't be long until a program can play on even terms with the champ. In Go I think the current best is somewhere around amateur 1 Dan or so, which is maybe like 1900 or so in chess, but here too the rate of progress is very high, with the "Monte Carlo" method getting the best results.
Parent - - By Permanent Brain (*****) Date 2007-08-30 17:08
I wonder if the Monte Carlo method could replace the "normal", or traditional positional evaluation functions in chess engines. Or, if it is not a competitive replacement, could it be at least a reasonable approach up to a certain strength level? - I am not a programmer and I have no idea how many M.C. games would be required to create an percentage reliable enough to make sense, for a single position.

Is the method too slow for chess? I think the M.C. games could probably be generated virtually without any eval, except mate and stalemate, so the move generator could generate them very fast without having to call another eval function. But I have only rough ideas of all these things. Maybe it's something which would require very many CPUs.

My interest in "minimalistic" approaches for chess engines was raised by microMax, an engine which is based on less than 2,000 bytes of source code.

http://home.hccnet.nl/h.g.muller/progress.html

It's evaluation function is very small, but nevertheless, it plays quite good chess on 2000 Elo (comp rating) level. I tried some games against it and didn't find big positional blunders. Most of it's strength seems to come from the depths it quickly achieves though, like 10 or 12 ply in blitz.
Parent - By lkaufman (*****) Date 2007-08-30 17:23
In my opinion the MC method will be viable for chess as soon as the number of processors reaches the number where the speedup in current programs from doubling drops well below 1.5 or so. Actually for Rybka I think we are already there at around 8 processors, but hopefully that will change soon. With the MC method, any number of processors can be used with minimal waste. The problem is that you need a very large number of games for the results to be likely to help the eval, and I don't think that stripping out the eval will speed things up enough to make this adviseable. Still, it is already feasible to consider MC with an 8 or 16 core machine, using half the processors for MC. Rybka can play 2-3 ply games very quickly, and the quality is not so awful. With 8 processors playing such games, a sufficient number could be played in the standard 3 minute tournament time. Then the problem is how to choose a move when MC and regular eval disagree. I think this is a problem that can be solved, so basically I am saying that this is something I expect to be tried (either by us or someone else) within the next couple years.
Parent - By Neuromancer (*) Date 2007-08-30 18:21
I wonder if the Monte Carlo method could replace the "normal", or traditional positional evaluation functions in chess engines. Or, if it is not a competitive replacement, could it be at least a reasonable approach up to a certain strength level? - I am not a programmer and I have no idea how many M.C. games would be required to create an percentage reliable enough to make sense, for a single position.

Note that in go, the UCT algorithm (which by itself is already a good deal more sophisticated than straight mc playout counting) does not only replace evaluation but also alpha-beta search. In chess, several decades of research have gone into refining the basic alpha-beta approach, so I would not expect anything completely different to be competitive on its own with this basic setup any time soon.
One idea which in my opinion could work would be to use relatively shallow alpha-beta searches in every as-yet-unexplored node we encounter during UCT search in order to obtain estimates of the winning percentage in all child-nodes of that UCT node. These estimates would then be used to initialize these childnodes (i.e. we would set the winrate of the childnode to the winrate suggested by our estimate obtained by the alpha-beta-search and the playout number of the childnode to some value which reflects the level of trust that we put into the results of that alpha-beta-evaluation).  This would build a very selective searchtree which would (by the nature of UCT) home in more and more on the most promising lines for either side as the number of playouts increases; if the Elo gains per doubling of number of playouts were similar to what we see in Go, this would eventually be superior to an alpha-beta searcher.
However, it is worth noting that in positions which are clearly won or clearly lost, any type of monte carlo evaluation will tend to stop discriminating between moves that win/lose more quickly and moves that speed up the win or delay the certain loss. In Go, this has the effect that the modern breed of UCT programs start to play horrible moves when they have a clearly won position (in clearly lost positions, there is no problem, as the program can just resign if all playouts have it losing); they will indeed do so until their advantage has gone down to a few points of territory, at which point they will start to play accurately again and go on to still win the game. In chess, the consequences of such behaviour would obviously be worse, as it might simply push a secure win over the 50 moves rule eventually. However, this could be resolved in chess by letting a straight alpha-beta player take over once the predicted winrate from the UCT playouts has exceeded a preset value for a couple of moves.
Every now and then, I am considering trying these ideas myself by studying the toga source and doing the necessary modifications. So far, I have not found the time to do the former (the latter should be easy in my opinion ;) ).

Greetings,
Neuromancer
Parent - - By Neuromancer (*) Date 2007-08-30 17:56

> Anyway, what is the state of the art?


The strongest rank a go program has so far been able to reach and hold at reasonable time controls on the kiseido Go server is 2 kyu, to the best of my knowledge, which is maybe equivalent to a 1600 rating on the FIDE Elo scale in terms of the time that it takes an average human who seriously tries to learn the game in question to reach that level.
On the small 9x9 board, the strongest UCT programs are quite strong now; being a strong 9x9 player myself, I would rate them between 3d and 4d.
I think progress will be rapid in Go and that in 20 years, it will be possible to beat pros on the 19x19 board.

Greetings,
Neuromancer
Parent - - By XmikeX (**) Date 2007-09-01 04:04
Got an Elo estimate for GNU_Go-v3.7.10 ?

I beat this program on my 5th Go game ever (19x19).

I would like to think that being a follower of Conway's ""Game"" of Life is responsible for this victory, but I know I'm just an uneducated western barbarian at Go.

It seems like software still has a long ways to.. Go... on this game.  (??)
Parent - - By Neuromancer (*) Date 2007-09-02 06:49
Hello,

while Gnugo is a couple of stones weaker than the top programs, I would not expect a beginner to have any chance at an even game on the large board.  At least on the 19 x 19 board it should beat you every time. In fact, if you are a complete beginner, it should beat you every time even giving a nine-stone handicap. Are you certain that it was set to full strength?  If so, it would be interesting if you could post a sample win.
The estimated playing strength of Gnugo should be in the sixth kyu range, because this is the rating that Gnugos running there have achieved consistently on the Kiseido Go Server. Even exploiting weaknesses, I expect anyone who can beat it often to be at least in the ten kyu range on the kgs scale.

Regards,
Neuromancer
Parent - - By XmikeX (**) Date 2007-09-03 03:12 Edited 2007-09-03 03:18
I'm a complete beginner.  Perhaps I've misinterpreted the scoring?

Anyways, here ya go:

All games, Beginner as Black.
--

Games 1-3 complete wins for GNU Go : unsaved

GNU Go v3.7-10 wins (4th game) : http://starbase.globalpc.net/~xmx/test4.sgf

GNU Go v3.7-10 loses?? (5th game) : http://starbase.globalpc.net/~xmx/test5.sgf

No more games played.

Let me know if I should thank the online sensei at : http://playgo.to/interactive/
Parent - - By Neuromancer (*) Date 2007-09-03 11:06
I'm a complete beginner.  Perhaps I've misinterpreted the scoring?

Thanks for posting.  Gnugo won that game.  Before you count you have to remove all dead stones.  After removal of all dead groups, the result is a 230 point white win.  Not to remove dead groups or not to recognize dead status is a common mistake for beginners.
Note that some user interfaces (such as glGo) will offer you the option of having Gnugo score the game after both sides have passed. The score estimator that comes with the KGS client will also mark the territories for you, although it is *way* less accurate than the gnugo scoring function. If you play the bots on kgs, they will also remove all the dead stones for you.

Greetings,
Neuromancer
Parent - - By XmikeX (**) Date 2007-09-04 00:48 Edited 2007-09-04 01:07
"" Not to remove dead groups or not to recognize dead status is a common mistake for beginners. ""

At this point, I wouldn't trust myself to score the game, so I'm dependent entirely on machine counts (rightly or wrongly), as follows :

Courtesy Jago 4.9 - "Chinese Count: Black 112, White 80 ..  Japanese count: Black 44, White 13   ... Prisoner Count - Black 12, White 7"

but then, as you point out...

gnugo-3.7.10-.exe --score -l test5.sgf ----> White wins by 230.0 points

Fascinating...

Ok, so to clarify..

http://starbase.globalpc.net/~xmx/test5-score.jpg

There are black groups there that are deemed "dead" at that stage in the game, and will be scored for white... and because I thought these groups were alive and blindly followed the proverb -> "Stones are never truly dead until they're removed from the board", I passed and lost the game immediately....  ?
:)
Parent - By Neuromancer (*) Date 2007-09-04 18:36
There are black groups there that are deemed "dead" at that stage in the game, and will be scored for white... and because I thought these groups were alive and blindly followed the proverb -> "Stones are never truly dead until they're removed from the board", I passed and lost the game immediately....  ?

To pass at that point was the right thing to do. The groups in question were unconditionally dead, and there was no territory left to fight about. Specifically, the groups around J12 and A9 are clearly dead since they have only one eye and no way whatsoever of connecting to anything that could supply another eye; likewise, the lone stones on K5 and N6 have no chance of connecting to anything alive. Hence, all these stones need to be removed before counting.
The reason that go user interfaces usually will leave the marking of dead stones to the human in front of the screen is, of course, that deciding which stones are alive and which are dead is in the general case not easy. Humans will occasionally get it wrong even when they are single-digit kyus already (I think the last time I disagreed with an opponent about the status of a group at the end of the game and was wrong happened when I was around 8k). This is also the primary reason why the chinese ruleset is generally considered to be better suited to computer Go than japanese rules, as with the former it is possible to simply play out any dispute without changing the result.

Greetings,
Neuromancer
Parent - - By shogi64 (*) Date 2007-09-01 04:12
I can't add much to the above, other than it was interesting venture several years back to even get my hands on a program!  i ended up contacting Mr. Kakinoki, the programmer, and did get his program KVII through the Japanese Shogi Association (with his help), along with huge CD database of games.  Habu was a great champion and was the only player to win all 7 of the premier tournaments in a single year.  The game is incredible...good luck finding an outlet for a top ranked program here--I don't know if it is possible.   I was very happy to get his program...did some reading about shogi programming and the problems they are encountering.   Interesting to read about the mate finder, the longest known mate was I believe in 152 moves and someone eventually came up with an algorithm to solve it; is the Win Finder in Rybka similar to the mating algorithm--looking for a mate in a seperate thread?   Interesting game, relies alot on distraction.  The last i read was the Korean team going with FPGA's.  What shocked me most was the time involved, ummm....thinking for 2 hrs on one move!  Not sure, but I believe it is a 7 hour game.  I would think the programming is quite different as the pieces keep getting recycled, closer to bughouse on a single board, so the evaluation must be much more complex.  So you end up exchanging a silver for a knight, then drop a pawn, another pawn, bust into the castled king's position, keep exchanging and dropping those pieces...mate in 152.
:-)  Shogi proverb:  3 knights in hand you win (unless you're a patzer).  Something like that Larry?
Parent - - By lkaufman (*****) Date 2007-09-09 04:39
     The shogi programs were mostly pretty different than chess programs, but in the last couple years the program "Bonanza" reached the top by basically emulating chess programs (with of course some differences). As for the proverb, "with three knights there is always a mate" is the version I heard; of course it only makes sense if the enemy king is exposed.
Parent - By shogi64 (*) Date 2007-09-11 04:39
writing SMP code is a bitch...why not get AMD as sponsor, doesn't hurt to ask,
they might even take a peak at the SMP code portions, hey IBM stock went up 18 billion after kasparov, don't forget
to tell them that...then I am sure they would like all of us to go barcelona not penryn...
"Optimized for Barcelona Inside" ha :-)  oops, that's intel's phrase.

sure vas has seen these.

http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/40546.pdf

http://developer.amd.com/quadcore.jsp

you might like the Tyan board I posted Larry, it looked Tops to me, ~ 1k for the board, then add 4 barcelona's (opteron's)
heat translates into problems.   I would think that would make a nice machine, you probably have < 7k in it.
Take a peak at amd home page if you haven't already.

shoot, i remember spending 5k on an old 486 from Gateway!!

Go AMD!!
Parent - - By Mekk (**) Date 2007-09-18 10:30
I would think the programming is quite different as the pieces keep getting recycled, closer to bughouse on a single board

Hmm, there are engines which play crazyhouse (this is exactly bughouse on one board). And they are not that bad, sunsetter is at the moment 2nd and TJchess 7th on FICS crazyhouse rating list.... Although that is mostly fast blitz, not sure how would they perform at slower pace (any good zh/bug player has opinion?)
Parent - By Vempele (Silver) Date 2007-09-18 11:38
I'm about 2200 at FICS (haven't played for a while though), but I'm almost certainly stronger than Sunsetter at slow blitz. Really, crazyhouse engines just suck compared to humans but their tactical strength tends to dominate at the usual fast time controls.

Bug is even more difficult for computers. All of them are below 2000; they basically don't take other board into account at all unless their partner tells to (and most players don't use Sunsetter's limited commands properly).
Parent - By Neuromancer (*) Date 2007-09-18 17:02
Note that a version of Mogo has recently been released to the public at http://www.lri.fr/~gelly/MoGo_Download.htm . People who have access to very fast freestyle-class hardware (8 cores) can hence now probably get a go opponent which is a good 2k and maybe even a weak 1k on 19x19 I guess.

Greetings,
Neuromancer
Up Topic The Rybka Lounge / Computer Chess / Computer Shogi and Go

Powered by mwForum 2.27.4 © 1999-2012 Markus Wichitill