When I rebuilt my program Spear from scratch in the summer of 2006, I was aiming for a program with solid foundations, which would be easier to improve. In the past I had entered the tournament with unstable programs that were hanging together with ad-hoc solutions, but it turned out that it was almost impossible to improve these programs and sooner or later they had to be discarded. In the 2007 tournament I had entered with a program based on bitboards, which seems to be a good starting point, even in games where the number of squares is not a power of two.
The main addition to the 2008 Spear was the implementation of running the search in parallel. Because I was already using an implementation close to Crafty, it was not difficult to add this and I had parallelism working in about two weeks, although I still found some minor bugs in the weeks after that. This gave the program another important performance boost, and running on a 4 core machine it searched about 2,000,000 positions per second on average. Not close to the top programs that do about 10,000,000 positions on 8 core machines, but still quite good.
I also made a conscious effort to keep the evaluation function as simple as possible. Using automatic learning is in vogue since Hoki published the machine learning technique he used in the 2006 World Champion program Bonanza, but rather than copying this method I want to use my program for other ways of using knowledge and I decided not to implement Bonanza's learning at this point. As a result, the evaluation function had to be simple enough to tune by hand or it would be impossible to make a stable program. Therefore, the evaluation function of my program only evaluated the following things:
Because of the simplicity of the evaluation, I found myself in the unusual situation that a few weeks before the tournament there was not much I could do to significantly improve the program. I had been testing Spear against K-Shogi (which finished 7th in the 2007 tournament) and minor tweaking of the evaluation values always gave similar results, a little above 50% at best. Also, I had been playing Spear on the new computer shogi server (floodgate) made available by Kaneko of the GPS team and the rating had been stable for a long time there as well, winning about 30% against TACOS and about 10% against Kakinoki Shogi, GPS and Bingo Shogi. These were not results that would make a place in the finals very likely, but good enough to have some hope if luck was on my side. Anyway, there was not much I could do but this minor tweaking of evaluation feature values in the weeks before the tournament. It would have been too risky to try anything radical.
If I needed to pick a favourite this year, I would have picked Tanase Shogi. I actually met Tanase on the bus from Tokyo Station to the venue and we talked for about an hour about our programs. It was clear that his program had improved significantly again and would be the program to beat. The other usual suspects would be Gekisashi, Bonanza and of course last year's winner YSS. However, Jeff Rollason had told me that Yamashita had been neglecting YSS a little in favour of his Go program Aya and that he didn't expect to do well this year. Judging from the floodgate server ratings, I also expected Bingo Shogi to do well. It seemed like Bingo had also improved a lot since last year and most of the games that Spear lost against Bingo on this server were very one-sided.
I was really looking forward to the tournament this year, expecting a lot of excitement. I got what I hoped for and a lot more, because this turned out to be one of the most dramatic and historic CSA tournaments ever...
The program My Move finished second and another first-year entry called dos finished third. Fourth place was for the veteran program Usapyon and fifth place was for the program A-class Move#1. I was actually rooting for this program, because it definitely is not like any of the other programs. The reason for this is that it is running on an FPGA (Field Programmable Gate Array). It has been common practice for shogi programs to run on off-the-shelf hardware and only a few programmers have made the effort to design special hardware for shogi. I once worked with a PhD. student on making a mating solver for shogi using an FPGA, but when the student got his degree, this work also stopped. I think using FPGAs could give us a new generation of shogi computers and be a great help in reaching the ultimate goal of beating the best professional players. I was therefore very happy to see this program reach the second preliminary stage, although there it showed that there are still a lot of bugs that need to be fixed before this will be a top program.
The FPGA on which A-class Move#1 was running.
No. Program Name 1 2 3 4 5 6 7 Pt SOS SB MD 1* Shuso 8+ 20+ 3+ 17+ 4+ 2+ 6+ 7.0 28.0 28.0 21.0 2* My Move 16+ 21+ 5+ 10+ 6+ 1- 3+ 6.0 30.0 23.0 17.0 3* dos 7+ 13+ 1- 20+ 12+ 9+ 2- 5.0 28.0 15.0 10.0 4* Usapyon 22+ 16+ 12- 5+ 1- 8+ 7+ 5.0 27.0 17.0 11.0 5* A-class Move#1 9+ 15+ 2- 4- 18+ 12+ 10+ 5.0 27.0 16.0 10.0 6* Yamada Shogi 19+ 14+ 18+ 12+ 2- 7+ 1- 5.0 27.0 14.0 8.0 7* Misaki 3- 11+ 13+ 8+ 10+ 6- 4- 4.0 30.0 15.0 8.0 8* Mattari Yuchan 1- 18+ 11+ 7- 17+ 4- 14+ 4.0 27.0 11.0 5.0 9* Auau Shogi 5- 10- 16+ 15+ 14+ 3- 13+ 4.0 26.0 12.0 6.0 10 Narikin Shogi 15+ 9+ 17+ 2- 7- 18+ 5- 4.0 26.0 11.0 5.0 11 Oki 13- 7- 8- 19+ 20+ 17+ 12+ 4.0 19.0 8.0 4.0 12 HIT Shogi 14+ 19+ 4+ 6- 3- 5- 11- 3.0 29.0 10.0 3.0 13 Yumeki 11+ 3- 7- 14- 21+ 15+ 9- 3.0 24.0 8.0 3.0 14 Garyu 12- 6- 22+ 13+ 9- 19+ 8- 3.0 22.0 6.0 2.0 15 Sexy AI-chan 10- 5- 21+ 9- 16+ 13- 17+ 3.0 22.0 6.0 2.0 16 Ym Shogi 2- 4- 9- 21+ 15- 20+ 18+ 3.0 22.0 4.0 1.0 17 Hayabusa 21+ 22+ 10- 1- 8- 11- 15- 2.0 24.0 2.0 0.0 18 Hakusa Shogi 20+ 8- 6- 22+ 5- 10- 16- 2.0 23.0 2.0 0.0 19 ShallowThoughts 6- 12- 20- 11- 22+ 14- 21+ 2.0 18.0 2.0 0.0 20 Bald Rat 18- 1- 19+ 3- 11- 16- 22- 1.0 24.0 2.0 0.0 21 Nanoha 17- 2- 15- 16- 13- 22+ 19- 1.0 20.0 1.0 0.0 22 Tohu 4- 17- 14- 18- 19- 21- 20+ 1.0 16.0 1.0 0.0 * Shuso, My Move, dos, Usapyon, A-class Move#1, Yamada Shogi, Misaki, Mattari Yuchan and Auau Shogi qualify for the second qualification round.Jeff Rollason arrived early in the evening and Spear played some test games against Shotest. Spear was winning most of these, but definitely not without a fight. A striking example was a test run we started before going to sleep. Spear was 2-1 up and I watched the fourth game before going to bed while Jeff was already snoring away his jetlag. Shotest was completely winning, so I turned off the monitor and went to sleep. I woke up at 4:15 in the morning and couldn't resist taking another look. To my surprise, Spear was 11-1 up! Not only had it managed to pull a rabbit out of the hat by winning the game it was obviously losing, it turned out that this was a pattern rather than an exception. Shotest was holding its own in the opening and middle game, but the raw search power seemed to be too much in the endgame.
The program Wildcat in trouble?
No. Program Name 1 2 3 4 5 6 7 8 9 Pt SOS SB MD 1* Bonanza 21+ 19+ 17+ 7+ 2+ 3+ 9+ 4- 8+ 8.0 44.5 38.5 29.5 2* Kakinoki Shogi 18+ 9+ 6+ 3+ 1- 10+ 5- 13+ 4+ 7.0 50.5 36.5 25.5 3* Bingo Shogi 22+ 5+ 15+ 2- 4+ 1- 7+ 10+ 9+ 7.0 48.0 33.0 25.0 4* Otsuki Shogi 14+ 8+ 5- 6+ 3- 11+ 10+ 1+ 2- 6.0 52.5 32.5 20.5 5* Nara Shogi 16+ 3- 4+ 11- 13+ 12+ 2+ 8- 7+ 6.0 48.0 31.0 20.0 6 Kiri 19+ 21+ 2- 4- 14- 18+ 8= 15+ 16+ 5.5 39.5 17.5 11.5 7 Shuso 12+ 23+ 10+ 1- 8- 14+ 3- 11+ 5- 5.0 47.0 21.0 14.0 8 Dragon's Egg 15= 4- 22+ 12+ 7+ 9- 6= 5+ 1- 5.0 46.5 18.0 10.0 9 GPS Shogi 24+ 2- 11- 20+ 17+ 8+ 1- 12+ 3- 5.0 46.0 19.0 12.0 10 TACOS 13+ 17+ 7- 14+ 11+ 2- 4- 3- 19+ 5.0 45.5 20.5 12.0 11 K-Shogi 23+ 12- 9+ 5+ 10- 4- 15+ 7- 13+ 5.0 42.0 21.0 13.0 12 SPEAR 7- 11+ 13+ 8- 16+ 5- 17+ 9- 14+ 5.0 42.0 21.0 12.0 13 Misaki 10- 20+ 12- 18+ 5- 16+ 14+ 2- 11- 4.0 43.0 15.0 8.0 14 My Move 4- 15+ 16+ 10- 6+ 7- 13- 18+ 12- 4.0 42.5 17.5 8.0 15 A-Class Move#1 8= 14- 3- 22= 24+ 20+ 11- 6- 23+ 4.0 35.5 7.0 2.0 16 Kinoa Shogi 5- 22+ 14- 19+ 12- 13- 24+ 20+ 6- 4.0 35.0 10.5 5.0 17 Shotest 20+ 10- 1- 24+ 9- 23+ 12- 21- 22+ 4.0 34.0 9.0 4.0 18 Usapyon 2- 24+ 19- 13- 23+ 6- 20+ 14- 21+ 4.0 33.0 9.0 4.0 19 Ayamari Shogi 6- 1- 18+ 16- 20- 22= 21+ 23+ 10- 3.5 35.5 8.0 2.0 20 WILDCAT 17- 13- 21+ 9- 19+ 15- 18- 16- 24+ 3.0 32.5 7.5 2.0 21 Auau Shogi 1- 6- 20- 23- 22+ 24- 19- 17+ 18- 2.0 34.0 6.0 0.0 22 Mattari Yuchan 3- 16- 8- 15= 21- 19= 23- 24+ 17- 2.0 33.5 2.0 0.0 23 Yamada Shogi 11- 7- 24- 21+ 18- 17- 22+ 19- 15- 2.0 31.5 4.0 0.0 24 dos 9- 18- 23+ 17- 15- 21+ 16- 22- 20- 2.0 30.0 4.0 0.0 * Bonanza, Kakinoki Shogi, Bingo Shogi, Otsuki Shogi and Nara Shogi qualify for the finals.
What else happened on the second day? Quite a lot, actually. As expected, Bonanza was way above the rest, easily qualifying for the finals with 8 wins out of 9 games. Its only loss was against Otsuki Shogi, which also qualified for the finals despite losing against Nara Shogi, Bingo Shogi and Kakinoki Shogi. Second place was for Kakinoki Shogi, which must have had visions of last year's disaster after losing to Nara Shogi in round 7, but this time it was not to be denied, winning against Misaki in round 8 to get the precious 6th win. Bingo Shogi finished third, which was more or less as I expected, although I was a little surprised it lost against Kakinoki Shogi even though Bingo Shogi's rating on the floodgate server is much higher than Kakinoki Shogi.
The last program to claim a place in the final was a surprise: Nara Shogi. It kind of sneaked in through the back door, avoiding an almost certain loss to Bonanza. However, wins against Otsuki Shogi and Kakinoki Shogi indicated that it had been improved significantly since last year and deserved to make its debut on the final day. Still, the programmer of Shuso will not have been too happy about the outcome of the final game. After 13 moves, Shuso failed to send the next move to the server and it lost on time. Of course, it is unclear if Shuso would have been beaten Nara Shogi, but losing without playing a proper game is very unsatisfactory.
The GPS team gave us the floodgate server, but there was no reward in this tournament...
With the likes of Otsuki Shogi and Nara Shogi claiming a spot in the finals, there were quite a number of strong programs who didn't make the cut this time. Sixth place Kiri was probably not one of them, using a draw against Dragon's Egg and a rather weak schedule to get a high finish. Dragon's Egg will have had more regrets. The draws by repetition of moves against A-Class Move#1 and Kiri proved especially costly. Both draws could have been avoided with a proper contempt factor. GPS Shogi also didn't manage to reach the finals, but this was caused by the schedule more than anything else. It lost against four strong programs and probably losing against K-Shogi was the biggest factor in not qualifying. Looking at it in another way, GPS Shogi had four chances to get to six points and failed each time, which seems to indicate that it just wasn't strong enough. Also disappointing was the result of TACOS. The loss in the second round against Shuso was important, but TACOS also failed to beat any of the strong programs, losing to Kakinoki Shogi, Bingo Shogi and Otsuki Shogi in rounds 6, 7 and 8. A victory against K-Shogi was unable to make up for that.
Shotest: small error with major consequences...
There was also drama in the struggle for finishing among the best 16, securing a seeded position for next year's tournament. The biggest drama involved Shotest. Shotest was actually doing quite well in this tournament, coming quite close to beating TACOS in the second round and having chances to beat Spear. Furthermore, its victories against WILDCAT, dos and Yamada Shogi were in typical "Shotest Anaconda Style": slow but certain death by strangulation. Then disaster struck in round 8. Shotest was paired with the rather weak Auau Shogi, ranked a rather prohibitive 13 places below Shotest, an opponent it would certainly beat. However, Jeff made a terrible mistake in starting up the wrong program. This was broken version that Jeff had failed to delete and accidentally clicked on (still a bit hungover from jetlag?). The program almost comically self-destructed in 23 moves. Unfortunately, the tournament rules stated that a game result stands if it lasts longer than five moves. They played another game, which was easily won by Shotest, and the programmer of Auau Shogi graciously proposed to make the second game count, but the tournament rules didn't allow this. Unfortunately, this meant that even an easy victory over Mattari Yuchan in the final round wasn't good enough for Shotest to keep its seeded position because of the weak opposition it had been paired against. Actually, Shotest missed 16th place and the final seed by a singled SOS point. Winning the game against Auau Shogi would have given Shotest a stronger opponent in the final round, which would have been enough to secure seeding even with a loss. Furthermore, a win (not unlikely considering how Shotest played) would have put it in the group with GPS Shogi, TACOS, K-Shogi and Spear where it probably belongs. Very tough break for Jeff that a mistake in a mouse click had such far-reaching consequences.
Finally, there was also some comical relief on the second day. The FPGA program A-Class Move#1 surprisingly secured a seeded position by finishing 15th, but the game against Mattari Yuchan showed that there are still some important flaws that need to be addressed. The game ended in a draw when A-Class Move#1 decided to move the promoted bishop back and forth in a position where there was a mate in one.
Not really a position where you want to go for a draw!
Professional Katsumata is an expert on computer shogi and his explanations are a joy for every visitor.
The first round already had a surprise: Bonanza lost against Bingo Shogi. Bonanza's attacking style backfired because it ran out of pieces, unable to place the final blow. Bingo Shogi made no mistake and Bonanza graciously resigned in a position it had no hope of winning, but that still was far from mate. All the other games went according to seeding.
The second and third round were uneventful, as all of the higher ranked programs won their games. The first game that was interesting was played in the 4th round between Tanase Shogi and Bonanza. A high level double Anaguma game where Tanase Shogi allowed a simple rook promotion. This looks bad (and probably is), but interestingly enough it was the same type of promotion Tanase Shogi had allowed last year in the game against Spear in the first preliminary round. Spear didn't find a way to make use of this and lost quickly. Bonanza clearly is a better program than Spear and it seemed like it had the advantage, but Tanase Shogi defended very well against the Bonanza attack and won the game in only 84 moves.
Inconsistent performance by Bonanza in the finals.
The fifth round had the first test for unbeaten champion YSS, playing Gekisashi. This was a strange game, as YSS had an early advantage after promoting the bishop, but then it seemed to lose its way. Unable to find a safe area for its king, it moved it to an even more vulnerable position than it was already in and then it sacrificed some pawns that seemed to indicate attacking intentions, but there was no follow-up. Gekisashi took full advantage, launching a strong attack through the middle straight at the king, winning easily after that. Meanwhile, Bonanza suffered a second unexpected loss against Otsuki Shogi. Otsuki Shogi had found the going to be very tough in the finals, but made clear with this win that it had indeed managed to close the gap with the big names quite a bit.
The sixth round became a dramatic round that will not be easily forgotten, especially not by Tanase. Tanase Shogi was playing Gekisashi and they played a very difficult game. Tanase Shogi refused to put the king in a safe spot and Gekisashi's king was also far from properly protected. The game was like a boxing match with both players continually throwing punches without being able to land a decisive one. When the game was about half way through, the game between YSS and Bonanza had finished with Bonanza winning. This meant that the winner of the game between Gekisashi and Tanase Shogi would also be the 2008 World Champion. Tanase Shogi was slowly starting to build a lead by exposing Gekisashi's king, while Gekisashi could not find a way to get to Tanase Shogi's king in the center. It was quite a long game, but on the screen it said that Tanase Shogi still had about three minutes while Gekisashi was already over the time limit (25 minutes without byoyomi for each program). When I mentioned this to Tanase, he said that he didn't keep track of the time of the opponent, so this could be ignored (the server actually sends the time that is being used for the moves back to the programs, but a lot of programs only update their own time using this information and ignore the information given about the time of the opponent). Tanase Shogi made a nice hisshi position against Gekisashi's king and Gekisashi had only a number of useless checks to extend the game, but without any hope of mating the king. Then word came that the game was over because the time was up. Tanase was overjoyed, because he was convinced that he had won the game. After all, the clock he had running had more than 2 minutes left for his program, while Gekisashi had used about 27 minutes. I was also convinced that he had won and congratulated him on a great performance. Then Katsumata, the professional player who commented the game, congratulated Gekisashi with the tournament victory. Tanase was stunned (and so was I) and even called out to Katsumata that he made a mistake and that Tanase Shogi was the winner. I then saw that on the big screen, the last move that Tanase Shogi had sent to the server had not been displayed. The final move there was Gekisashi's 189th move. I realized that Tanase Shogi had lost the game on time according to the server. The tournament rules state that the time the server sends back is the official time used for the move, but Tanase still refused to believe that he had lost the game on time. When we replayed the game, it turned out that the time used for each move as recorded by Tanase Shogi was identical to the time that had been recorded by the server! Tanase Shogi had lost this vital game because of an error in translating the time received from the server to the internal clock used by the program to decide the time for its moves. It is hard to believe that 1) an experienced programmer like Tanase would make such a mistake; 2) didn't realize there was a mistake in two years of testing, 3) had the mistake turn up in a game that decided the World Championship and 4) having the mistake turn a certain victory into a defeat. If ever Murphy's Law was at work in computer shogi, there it was. For Tanase it was not the first time a freakish error cost him at the worst possible time, because he also lost last year's title due to a small mistake in the calling of the mate solver when running the program on multiple processors.
Tanase after the game against Gekisashi: what went wrong??
There was an awkward silence after the game. Usually there is a roar of applause for the tournament winner, but the confusion after the game and the way the title had gone to Gekisashi only lead to some uneasy congratulatory handshakes for the Gekisashi team, which was feeling a little embarrassed as well. The general feeling was that the title had not gone to the best program in the tournament. The final round rubbed more salt in the wound. While Tanase was staring in the distance for most of the time, his program happily butchered YSS (computer programs know no disappointment), while Bonanza crushed Gekisashi.
Gekisashi programmer Tsuruoka after the exhibition.
Because of these results, Bonanza came in third, having the best SB points of three programs finishing on 4 points. YSS also had 4 points, losing its final three games, while Bingo Shogi reached 4 points by winning its last three games. Also, Otsuki Shogi finished with 3 points, so it seems that Bingo Shogi and (to a lesser extent) Otsuki Shogi have closed the gap to the top. Nara Shogi beat Kakinoki Shogi to get at least one win in its first appearance in the final, while Kakinoki Shogi couldn't follow-up on its strong performance on the first day and lost all games.
No. Program Name 1 2 3 4 5 6 7 Pt SB MD 1 Gekisashi 6+ 8+ 7+ 5+ 4+ 2+ 3- 6.0 18.0 12.0 2 Tanase Shogi 7+ 6+ 5+ 3+ 8+ 1- 4+ 6.0 16.0 12.0 3 Bonanza 5- 7+ 8+ 2- 6- 4+ 1+ 4.0 11.0 5.0 4 YSS 8+ 5+ 6+ 7+ 1- 3- 2- 4.0 8.0 4.0 5 Bingo Shogi 3+ 4- 2- 1- 7+ 6+ 8+ 4.0 8.0 4.0 6 Otsuki Shogi 1- 2- 4- 8+ 3+ 5- 7+ 3.0 5.0 1.0 7 Nara Shogi 2- 3- 1- 4- 5- 8+ 6- 1.0 0.0 0.0 8 Kakinoki Shogi 4- 1- 3- 6- 2- 7- 5- 0.0 0.0 0.0
The exhibition game between Kato Yukio and Tanase Shogi.
The first game was already a big surprise. Computer veteran Kato
played a natural looking pawn drop to improve his position in the
early middle game and this
turned out to be the decisive mistake! Tanase Shogi launched a
devastating attack and Kato had to resign in only 75 moves! This loss
put a lot of extra pressure on Shimizugami in the second game, but he
seemed to deal with that pressure very well as he came out of the
opening with a clear advantage. However, after that he rushed his
attack and he too felt the endgame strength of the computer as
Gekisashi attacked strongly without giving Shimizugami a chance to
recover. Two wins for the computer! CSA Chairman Takizawa spoke of
a historic day for computer shogi and that was what it was. Computer
shogi has come of age and seems ready to make a final push to
beat the top professional players. Still, there was a word of warning
by both Tanase and Tsuruoka (Gekisashi) after the game that
the victory was mainly caused by having Kato and Shimizugami playing to
the computer's strengths instead of its weaknesses. This
may be true, but it also shows that computers have become too strong to
just play them without proper preparation. Chess programs
have long been known to have strategic weaknesses and this is even more
so for shogi programs. Only by aiming for a perfect win
by playing a superior strategic game and avoiding tactical
complications as much as possible, it is still possible to beat the
top programs. This year's exhibition showed that the only way to beat
computers is by being extremely careful.
The exhibition games
Trying to make a point with one beer too many.