Reijer is a lecturer at the Department of Informatics at Yamagata University and the author of the shogi program SPEAR, developed over the last 10 years and currently in its third re-write. In this time he has also been connected with the development of AI Factory's Shogi engine Shotest, as these two programs have been developed in parallel. Reijer is now directly contributing to our latest Shogi program, due for market later this year.
See also: Appendix: Shotest at CSA 2008
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:
- Material
- Bonus for pieces in hand
- Attack distance of single pieces to the king
- Defense distance of single pieces to the king
- Castle value of pieces (for example, where to have the golds in a yagura castle)
- Assault value of pieces (for example, how to play a climbing silver attack)
- Balance of attack cover and defense cover on the 25 squares around the king
- Mobility of major pieces and lances
- Pinned pieces
- Penalty for blocked pawns, knight and silvers
- Penalty for pawn in the back of a rook
- Penalty for a knight on the 5th rank
With deep regret I found it impossible to avoid the use of game progress to add weights to evaluation features that are more important in the endgame than in the opening or the middle game. I think that using game progress makes it 100% certain that there will be many positions that are evaluated completely wrong. Especially when only one side is attacking, the progress value will be much lower than it should be. I was unable to make the program play the opening in a reasonable way without using progress value and self-play results clearly showed that using progress value made the program stronger. Therefore, I entered the tournament with a program that had this progress value to add weights to evaluation features, but I will almost certainly remove this for the next version (neither Bonanza nor Tanase Shogi use progress values).
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 First Preliminary Stage
Because Spear was seeded for the second preliminary stage this year, I only arrived at the venue on the afternoon of the first day. Not only did I miss half of the games, I also went to my room early to do some final tweaking, so I did not see much of the action on this first day. However, one program clearly stood out. This was the program Shuso, a first year entry that won all of its games. The level of the programs on the first day differs a lot, but there are some strong veteran competitors like My Move, Usapyon and Misaki, so winning all games is not so easy. Shuso was running under ShogiDokoro, a general interface for shogi like the program Arena for chess. There were quite a number of programs on the first day running under ShogiDokoro, which makes it easy to build a shogi program without having to worry about the messy details of the GUI.
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
The other programs that qualified from the first day were Yamada Shogi, Misaki, Mattari Yuchan, and Au Au Shogi. Not many surprises here, because all of these programs have played in the second preliminary stage before.
Results of the first qualification round
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 Second Preliminary Stage
The test run against Shotest seemed to show that my decision of going for speed over knowledge might have been the right one, but good results in tests often mean very little in real competition. Spear would have to prove itself against strong opposition on the second day. Of the 24 programs in the second preliminary stage, 9 programs had been to the finals at least once and Bonanza was obviously the favourite to do it again this year. I estimated that Spear would have about a 10% chance to make it to the final day, maybe less.
The program Wildcat in trouble?
To have a chance, I figured that Spear couldn't afford to drop games against programs that wouldn't have much chance of qualifying for the final and this seemed to go wrong from the start. Spear played Shuso, the program that had won all games in the first preliminary round and even though Spear managed to make a promoted bishop early, the huge attacking base that it gave up near the king was a long-term problem. Shuso didn't play any obviously bad moves and used the attacking base to set up an unstoppable attack. There was not much I could do about this loss, but I was disappointed to be losing against a rookie program. I could only hope that Shuso would beat other potential finalists as well.
This meant that the second round game against K-Shogi was already a make or break game. Losing this game would drop me into a 0-2 hole and it might even become a struggle to defend my seeded position. The opening of this game wasn't going well at all, as Spear put the bishop in a cramped position to complete the Yagura castle and this bishop fell victim to a silver, so Spear was behind in material without much compensation other than a stronger king position. However, a bug in the move generation by K-Shogi made it drop the bishop on a square where it could not move from and Spear got the bishop back in hand, with many squares to drop it. K-Shogi tried a desperate attack, but Spear defended this without too much of a problem and won quickly in the counterattack. All my practice games against K-Shogi (perhaps more than 1000) had paid off. Spear had beaten a former finalist for the first time!
The third round game against Misaki looked like it would be a straightforward victory. Spear first built a better castle, then promoted a bishop, then created a tokin that threatened to eat a number of pieces. However, Spear gave Misaki a dangerous looking attack when it went for material instead of king safety and in the end the game became quite close. I was very happy to see that Spear had found a very complicated mate that a human player would probably have overlooked. Misaki didn't have a great result on the first day, but it definitely is a program to be reckoned with.
Round 4: Spear - Dragon's Egg 0-1
Before the tournament, I figured that Dragon's Egg was one of the potential finalists that I might be able to beat. I had come close to beating it before, and considering that Spear had improved considerably, I gave it a 50% chance to win this game. however, the game was quite a letdown. Spear got confused in the opening, playing a very weak castle and used the silver that was supposed to be a castle piece for a wild edge attack that didn't have a prayer. Spear sacrificed a lot of material to get the king out in the open, but then had no material left to finish the job. Dragon's Egg defended calmly and easily won in the counter attack.
Round 5: Kinoa Shogi - Spear 0-1
Spear had already lost two games and couldn't afford to get further behind, but the next opponent also wasn't easy. Last year Spear only won against Kinoa Shogi because it had no way to claim a victory in a mutual entering king game and lost on time after 489 moves. This year's game was not such an epic battle, but a strange game anyway. Neither program managed to get into a proper castle and in the middle game the material balance shifted constantly. Just when it seemed that Spear got the upper hand, it played the attack wrongly, allowing Kinoa's king to escape up the board. Furthermore, Spear's king also had a free path up the board so visions of last year's game came back. Fortunately, Kinoa decided to attack instead of going for the entering king, allowing Spear to make a hisshi position.
Round 6: Spear - Nara Shogi 0-1
Time was running out if Spear wanted to make its push for a spot in the final. The game against Nara Shogi was a game it needed to win, and because Spear had beaten Nara Shogi last year, this seemed very much a possibility. However, just like the game against Dragon's Egg, the game was quite disappointing. Nara Shogi moved into a strong anaguma castle and Spear had only a two general mino to defend the king. Spear doesn't understand that opening up the game is dangerous when there is a big difference in castle strength, so it was happy to exchange a number of pieces when the chance presented itself. This backfired and even though Nara Shogi seemed to be a little overanxious to drop a gold in defense to defend against an attack that was not so powerful, Spear didn't realise that it had to hurry, calmly promoting a bishop. This gave Nara Shogi the time to start a slow but strong tokin attack that was decisive.
With three losses, the window of opportunity was almost closed and I was more or less resigned to the fact that the best I could do was defend my seeded position. Still, the game against Shotest was a game I definitely wanted to win. Not only were the test results against Shotest on the previous day heavily in Spear's favour, I also had never beaten Shotest in the CSA tournament. Even though we have been entering for years, our encounter in the 2006 tournament was our first (Spear lost that game without much of a chance). Finally, this year there were only two programs made by non-Japanese programmers, so this game would also decide the (admittedly rather futile) "best of the West" bragging rights. Interestingly, the game had a completely different flow than the test games we had played the night before. Spear got a small but significant advantage when bishops were exchanged and Shotest almost immediately dropped it in a spot where it was not very effective. After that, Shotest sacrificed some material to make a couple of tokins that were far away from Spear's king, but kept on moving closer and closer. For a long time it seemed that Shotest's attack would be in time, but when it made a mistake by playing a not very effective defensive move instead of attacking, Spear could finally use its extra material to start a winning attack. I was very relieved to see the evaluation jump from almost level (which was rather optimistic) to winning within a couple of moves.
Round 8: Spear - GPS Shogi 0-1
GPS Shogi had been kicking Spear's butt on the floodgate server, so expectations for this game were not high. It seemed like it was going to be a one-sided loss when GPS Shogi broke through, but then it voluntarily weakened its mino castle and suddenly a rook exchange would make things very interesting. However, Spear didn't realise it needed the rook and was happy to exchange its passive rook for an active bishop. The bishop promoted, but the rook was much stronger in attack and the game became rather one-sided.
Four losses meant that a place in the final was out of reach. There had been three chances to move up, but losing against Dragon's Egg, Nara Shogi and GPS Shogi killed the run before it started. All three games were kind of one-sided, so I couldn't really complain. Despite my failure to make an impact, there was still a lot to play for in the final game. Although even losing it would be good enough to save a seeded position, a victory would mean a majority of wins, which feels much better. Also, I have not been doing very well against My Move in the past, losing twice and coming very close to losing in last year's tournament as well. This game was probably the closest game Spear played in this tournament. Again it allowed an attack base close to the king that looked very dangerous. However, unlike Shuso, My Move couldn't quite figure out how to use it and a passive defense move where a strong attack was the only way to keep it interesting sealed it.
Results of the second qualification round
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 Au Au 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 Au Au 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 single SOS point. Winning the game against Au Au 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!
Round 4: A-Class Move#1 - Mattari Yuchan Sennichite
Actually, A-Class Move#1 had 28 consecutive positions where it could play a mate in one move. This must be some kind of record and because it was the last game to finish in this round it was displayed on the big screen in the tournament hall, magnifying the embarrassment. It just goes to show that even though the level of the programs has skyrocketed in the past couple of years, there are still some comical bugs left in the programs.
The Finals
For a number of years now, there has been a large gap in the finals between the top programs (YSS, Tanase Shogi, Gekisashi and Bonanza) and the other programs, who more or less take turns in qualifying for the final day. As I wrote above, no less than 9 programs in the second preliminary tournament had experience of playing in the finals, but except for Bonanza, none of them had finished higher than 5th place in the past five years. One of the questions I had before the tournament was if a program like Bingo Shogi or Otsuki Shogi had a shot at closing the gap. Otsuki Shogi had played impressively at the tournament during the Game Programming Workshop in November and Bingo Shogi was rated about as high as YSS on the floodgate server as mentioned before. In my opinion the program to beat was Tanase Shogi and I decided to follow Tanase Shogi from up close, hoping to learn a little more about its strengths and weaknesses.
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. 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 not the inevitable outcome. 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.
Results of the finals
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
This year, there were two exhibition games. Top amateurs Kato Yukio (Asahi Amateur Meijin title holder) and Shimizugami Toru (Amateur Meijin) would play the winner and the runner-up. Shimizugami has been in great form recently, beating a number of professionals. His biggest scalp is that of 7-dan professional Nozuki Hirotaka. Kato had played computer programs four times before in exhibition matches and won all four. For Shimizugami it was his first encounter with the computer. Furigoma had decided that Kato would first play runner-up Tanase Shogi and then Shimizugami would play Gekisashi. Time limits were 15 minutes per side followed by 30 seconds byoyomi. Although this strict time control favours the computer, the general opinion seemed to be that 1-1 was the likely and most desirable outcome (the computers would not be embarrassed).
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 Party
For the first time in years, I attended the party after the tournament. Usually I have no time to stay until the end, but this year the schedule was favourable with an extra holiday after the tournament finished. The party is a great opportunity to exchange some final ideas before parting ways for another year. Also, this year's speeches had a lot of highlights. Gekisashi's Tsuruoka said that the main problem with the tournament victory was not the way it had been achieved, but the fact that Tanase would mention it in conversations from now until eternity. Tanase Shogi said that he didn't feel he had lost a game in the tournament and that made it very hard to accept second place. However, he also said that being critically acclaimed as being the best program in the tournament eased the pain a little and that he realized that in earlier tournaments with IS Shogi he sometimes had luck on his side, so that it was only natural to see it from the other side. Still, he ended with the promise to win the tournament in 2009. Hoki teased Kato and Shimizugami by stating that amateur players now had officially become too weak to face the computer and that he was looking forward to seeing professional opposition next time. Also, he noted that after losing only one game two years ago and two games last year, he had now lost three games and jokingly said that he started to feel sorry about explaining his successful learning method to everyone. Professional Katsumata said in his speech that he would have lost to Tanase Shogi as well, because every move that Kato had played would have been his first choice as well. Kato and Shimizugami pledged revenge, but the most interesting speech was by Ladies Meijin Yauchi. She has been a guest at the CSA tournament for years and after her first visit she said that she didn't want to play the computer because it would mess up her style of play. This year she just said she wanted to avoid playing the computer at all costs. I thought I saw some real fear in her face when she said this and she seemed genuinely shocked that both Kato and Shimizugami had lost. No surprise as both of them are probably stronger players than she is. Actually, despite having achieved nothing of significance, I also had a speech in which I stressed the importance of new idea and the danger of everybody blindly following Hoki's learning method. I think computer shogi needs one more breakthrough to beat the top human players, most likely in the area of strategic play.
Trying to make a point with one beer too many.
Conclusions
This was the most dramatic and historic CSA tournament that I have ever participated in. For me personally, it turned out to be a vanilla tournament and only the wins against K-Shogi and Shotest I will probably still remember in a couple of years. However, to see the dramatic game between Gekishashi and Tanase Shogi up close and then see two top human players lose their games against the computer made this a tournament to remember. It is clear that the areas where human players can still outplay the computer are narrowing. This is good, because from this moment on human players will have to use all of their flexibility and inventiveness to beat the computer. We are at the brink of another great battle between man and computer and although there is not much doubt about the outcome, it will be exciting to watch. Of course, I am hoping to be in the middle of this with my program Spear, but this tournament showed me that I am running out of time, Important improvements must be made in the next year or I will just be another spectator until the likes of Habu succumb to the computer. Writing this report has already cost me too much time, I must get back to programming!
Reijer Grimbergen: May 2008
Appendix: Shotest at CSA 2008
Click here for the full (photo) event report of the championship.
As a footnote to Reijer's excellent article, following Spear's progress, we also have Shotest's detailed progress below.
Shotest entered the CSA tournament this year after having spent most of the year being prepared primarily for a commercial release. Preparation for the tournament was focussed on just play testing against K-Shogi, the current world number 7. Last year's program was scoring 35% against this program and this year's entry pulled this up to 50%. A concern was that, although Shotest is in good shape, it is still just a single core product (more ideally suited for commercial use), whereas increasingly the competing programs are running on multi-core machines, many on 8-cores. Shotest is also built around a complex node evaluator, so the number of positions it examines per move is small. Given it was facing fast programs on multi-core hardware this potentially left Shotest vulnerable to being out-searched.
The previous year Shotest, for the first time in 10 years, was not the top Western program, tying in games with SPEAR, but behind in tie-breaking points. I knew that this was now a "title" I could no longer assume, and SPEAR was looking good!
Round 1: Shotest - WILDCAT : 1-0
This was a favourable first pairing for Shotest, but WILDCAT is no pushover. It is generally a seeded program and last year took games from the likes of the improved SPEAR. However Shotest seems to be a tough opponent for WILDCAT, and in all encounters Shotest has won easily. This was no exception. WILDCAT was a little defensive, quickly placing its king in the strongest castle, the Anaguma. From there WILDCAT was too passive, allowing Shotest to steam-roller into WILDCAT's position. Shotest quickly controlled the board, swallowing WILDCAT's pieces. The Anaguma, although strong, offers few chances for escape via an entering king, so Shotest closed in and trapped the king.
On paper Shotest has an undefeated 8:0 record against TACOS, but this is very misleading as this was against a much weaker earlier version. The new TACOS runs on 8 x cores and is world ranked 6th, so I expected to lose this one. However Shotest clearly came out of the opening and middlegame with an advantage. By move 70 TACOS seemed to have over-playing an attack. Shotest defended this well and appeared to be ahead. However, by move 106, Shotest's rook was pushed out of play and TACOS was able to press home a winning attack. The TACOS team admitted they were lucky!
Round 3: Bonanza - Shotest : 1-0
Having just faced the number 3 seed in this round, Shotest then faced the 1st seed. This is the toughest pairing that any program faced for their first 3 rounds. Bonanza is the previous World Champion and was a candidate to win again this year. Shotest's prospects were not good! Shotest early on made the mistake of using its bishop drop to win a pawn. By move 54 Shotest had lost that material gain but Bonanza was left with a bishop in-hand. This was decisive as it gave Bonanza many more options and constrained Shotest. Bonanza found a way in and Shotest was thereafter always behind.
With 1 win and 2 losses Shotest was then given a weaker opponent, which had qualified from day one. DOS qualified with 5 wins and 2 losses. The game started with a very cramped position. By move 54 neither side had any advantage and Shotest even appeared to dither. However DOS had used 30% of its clock, but Shotest only 11%. Move 55 and Shotest attacked. DOS fell to a pin of its Gold and Shotest broke through. DOS was quickly in trouble as Shotest controlled the centre of the board. DOS was losing by move 79 and lost on move 88.
This is a greatly improving program, with a dedicated OS and 8 cores. It also has the largest development team of 10 members. Shotest repeated the same mistake it had made against Bonanza, using a drop bishop to win a pawn, but in this game was more quickly punished. By move 29 the gained pawn had been lost and GPS, with bishop in hand, was able to pressurise well. From then on Shotest was always behind and the game ended after 91 moves.
Round 6: Shotest - Yamada : 1-0
Again a loss gave Shotest a weaker opponent. Like DOS, Yamada qualified to day 2 with 5 wins and 2 losses on day 1, but again Shotest has never lost to Yamada. Shotest appeared to always have the advantage in this game, with territory advantage and then on move 47 finally breaking through on one flank. However this clear substantial advantage was slow to convert to an eventual win. Yamada planted a defensive pawn on move 85 that Shotest found hard to bypass with its threatening Tokin army. These powerful Tokins, close to the enemy king, were stalled, so Shotest broke through with other pieces and finally on move 143 the block pawn fell, as did Yamada's king.
Round 7: Shotest - SPEAR : 0-1
Shotest was now on 3 wins and 3 losses, so would need to win all remaining games to have any chance of qualifying to the final round. This match was the re-match after Shotest won in 2006. However this time Spear had the edge. SPEAR was running on a quad code and this, with an improved program, showed SPEAR's advantage in an overnight run which SPEAR won by 17 games to 6. Given that this suggested that Shotest would probably lose, I figured I should re-introduce held back evaluation features to improve Shotest's chances. I did this and a game that started favouring SPEAR turned into what looked like a possible win for Shotest. Having been behind most of the game, by move 110 Shotest had a very threatening Tokin army bearing down on SPEAR's king and Shotest thought it was ahead. However, even though poised for what looked like a possible deadly attack, Shotest instead opted to defend against SPEAR's threats and the chance was lost. This was a just result, as SPEAR was stronger.
Round 8: Auau Shogi - Shotest : 1-0
Now I was facing a likely repeat of last years 5 win 4 loss record. Auau was ranked 13 places below Shotest, so this was a likely very "easy" game in prospect. However it turned out to be a nightmare comedy of errors! In creating a new version of Shotest to play SPEAR, the first build had been defective, so needed to be re-built. Unfortunately I failed to delete the defective build and accidentally used it for this game. For its first move Shotest took 41 seconds and reported an evaluation of losing by 20 golds. Transfixed, rather like a rabbit in the headlights, I stared as the next few moves were rattled off at very high speed, veering between +/- 20 golds. Suddenly the game was over, after 12 moves each, before it could be stopped. The author of Auau offered to play again, which was done with the correct version, and Shotest won very easily. The author of Auau also generously offered for the second game to be the official game, but the organisers held that the first game result must count.
Round 9: Mattari-Yuchan - Shotest : 0-1
With the unexpected loss in round 8 all chances of holding last year's ranked position were gone. With only 9 games to play you cannot afford to throw one game away. This also meant I would face an even weaker program so that I would also lose tie-breaking points, reducing the value of any win. Mattari-Yuchan was ranked 10 places below Shotest, so a win was expected. Curiously Shotest make the same mistake it made against Bonanza and GPS, in using a drop bishop to win a pawn. However Mattari-Yuchan was unable to take advantage of that and Shotest was always ahead. Mattari-Yuchan played a aggressive game but inevitably succumbed after 152 moves.
Conclusions for Shotest:
This was an unexpected disappointing result for Shotest but the ranking does not really reflect Shotest's strength. In losing the 8th game by error, Shotest dropped 5 places in the table. Of the 4 programs moved above Shotest, 3 had a previous track record and were all ranked below Shotest, by up to 9 places. In terms of game performance Shotest performed quite well. The strong game against TACOS was encouraging and its wins were all convincing. The pairing system gave Shotest the toughest first 3 round pairings of any other program, playing both the 1st and 3rd seed. Shotest's lowest ranked opponent loss (ignoring Auau) was against SPEAR, but that was a close game. Even though the official ranking was 17th, with the Auau game overturned Shotest would probably have been left 13th, placing it at the lower end of the 5 win 4 loss pack with the strong TACOS, Dragon's egg, GPS and SPEAR.
Sometimes an unexpected bad result is a good imperative to drive progress for the following year. Shotest is still basically very close to the version that came 3rd in two successive years in 1998 and 1999. It is due a re-write. Shotest is single core and does not even use opponent's thinking time. As a post tournament test Shotest was re-tested against a single core SPEAR (instead of 4 cores) and improved its win rate from 26% to 45%, and that is without opp-think time turned off. This gives a limited indication that turning Shotest into multi-core alone might give a significant performance boost.
However Shotest still needs to move on to the next stage. For its very low node analysis rate, Shotest clearly performs very well, beating programs that are 100 times faster. This needs to be taken to the next level. Shotest has a very sophisticated evaluation that is designed to drive the search, but this is under-exploited. Given more direct control Shotest would be tactically much stronger. A late sleepless night in Tokyo followed and the penny dropped. A core barrier to this development was solved and now Shotest will adopt direct search control by evaluation. This could be a needed breakthrough for CSA 2009.
A final issue is positional evaluation. It is clear that Hoki's success with piece tables and learning (Bonanza) has been very successful and similar systems have now been adopted by Tanase and other programs. Clearly other programs will be doing this as well soon. Work had already began with Shotest with this type of system in mind, but this will take a different path to coordinate with Shotest's complex analysis. We shall see what this does for Shotest in CSA 2009!
Jeff Rollason: May 2008
