From: Reijer Grimbergen ETL GO JP> Date: 13 may 1997 Subject: Re: Real chess computing Since I am struggling with this issue daily (who said this is a great job :-)), my opinion on this might be of interest. First, I talked to Mr. Feng-Hsu (the programmer of Deep Blue and all its predecessors) last year. He knows the rules of shogi (which means that he is only slightly better at chess than at shogi :-) ) and is convinced that a Deep Blue like machine could play shogi at the top level. Of course some changes need be made in the hardware (Deep Blue currently using seperate processors for all squares on the board), but he thought the problem could be solved if a good algorithm for filtering out useless drops could be found. Let me assure you that IBM has no intention to build a Shogi computer. In fact, if Feng-Hsu's prediction is right, the Deep Blue project might be terminated after the win against Kasparov. Still, I do not agree with Feng-Hsu. I think it is extremely difficult to find an algorithm to weed out all or most useless drops. However, Feng-Hsu is right about the basic difference between chess and shogi and that is the difference in branching factor. Chess has an average branching factor of 35, while Shogi has an average branching factor of 80 (Go is a horrible game in this respect with a branching factor of 250!). If it is possible to bring this branching factor down to the level of chess, there seems no doubt that a computer can play shogi at Habu's level. Currently, I am trying to use pattern recognition to get that branching factor down to an acceptable level, but thus far the program does not generate the correct move in about 25% of the positions. This needs to improve to at least less than 5% to play well. The other problem with Shogi is the difference in evaluation of position. Endgame positions in chess are clearly judged differently than endgame positions in shogi. (I believe that the reason Deep Blue won this year is the improvement in evaluation compared to last year's evaluation function and that the enhanced speed played only a secondary role.) In Shogi, I think the mediocre evaluation functions are a lack of combined effort to find something good. Even in Japan, there are maybe only about 50 people doing research in this area. Even when you count the professional Shogi game programmers there are not more than a 100. If that number does not increase, it will take a long time to build a really strong program. My conclusion after a year of research: dropping of pieces is the vital difference between shogi and chess. All other differences are marginal. This has an effect on the branching factor and the evaluation function. If people work together I think it is possible to have a good evaluation function within five years. I can make no prediction about how long it will take to bring down the branching factor. I believe that different algorithms are necessary to do that, and that is what I am doing now. However, I may be wrong and Feng-Hsu may be right. He has been right in the past, you know :-). Reijer P.S.: More details can be found on my homepage. -- Reijer Grimbergen Electrotechnical Laboratory Palcious Tsukuba 302 1-1-4 Umezono 1-24-8 Ninomiya Tsukuba-shi, Ibaraki-ken Tsukuba-shi, Ibaraki-ken 305 JAPAN 305 JAPAN E-mail: grimberg etl go jp Tel: 0298-59-1606 WWW: http://www.etl.go.jp:8080/etl/suiron/~grimberg Tel: +81-(0)298-54-5080 extension: 67431 Fax: +81-(0)298-58-5918