HaChu, an AI for playing Chu Shogi

HaChu is program to think up moves for Chu Shogi. It does not provide any graphical user interface; it communicates the moves purely in text format. It is intended as a so-called engine or plugin for the WinBoard graphical user interface. The WinBoard Alien Edition supports many Chess-like board games, including the large Shogi variants Chu Shogi, Dai Shogi, Tenjiku Shogi, Dai Dai Shogi, Maka Dai Dai Shogi and Tai Shogi. HaChu so far only plays Sho, Chu and Dai Shogi, although the rules of Tenjiku Shogi already have been partially implemented.

Playing Chu Shogi over the internet HaChu is run as an automated computer opponent (a 'bot') on 81Dojo.com, a website dedicated to on-line live playing of Shogi and its variants. 81Dojo is actually a cluster of servers, which each handle a different set of variants. On the EARTH server you can play regular Shogi and some of its small variants (5x5 mini-Shogi and 6x6 Judkins Shogi). The JUPITER server is dedicated to Chu Shogi, and this is where the HaChu bot usually plays. It can be logged in under the name HaChu or ChuBot; the latter usually is an experimental version I want to try out, while HaChu is the account used by the 81Dojo operators themselves to run the standard version. When logged on to JUPITER, the HaChu bot places game requests for a certain time control, like 20 min + 10 sec/move byoyomi. People that want to play it at these settings can simply accept the challenge by double-clicking the game request in the usual way. It is possible, however, to make the bot alter its game request for another time setting. To this end you have to send it a private chat message (by double-clicking on the bot's name in the list of logged-on users). When you send it the chat line "set time 45-60" (say), it would revise its game request to play 45 min + 60 sec/move byoyomi. In this way you can allow yourself more time. Note that the bot will always play at the original speed, and will never use the byoyomi time.

To challenge HaChu, click on the game it requests on the lower left

Playing HaChu at home

HaChu and WinBoard are free software, and can be downloaded from my website. With this package you can install them locally on your computer, and play against HaChu there. This way you can also play Dai and Sho Shogi, which are currently not supported at 81Dojo. Note that WinBoard has a resizable board, but that not every board size supports special piece graphics for Chu or Sho Shogi. The board size can be selected from the View->Board menu, and only sizes 'petite' and 'tiny' have built-in piece symbols for Chu Shogi and larger variants. These pieces are not traditional Japanese pieces, but the so-called 'mnemonic piece set'. At other board sizes you can still play Chu, provided your computer has support for Asian languages: in stead of piece symbols, WinBoard will write the kanji for the pieces into the board squares, as text. It uses single-kanji notation at sizes 'small' and below, and double kanji at larger sizes. At size 'mediocre' it furthermore draws traditional pentagonal koma in the squares onto which it writes the kanji. People that want to adjust the kanji font should know that WinBoard uses the 'ICS Interaction' font for the kanji, with the GB2312 charset (code page 128) to encode them.

For Sho Shogi there are traditional kanji pieces in board size 'moderate', and Chess-style symbolic piece symbols at sizes 'petite', 'middling' and 'bulky'. At other sizes it will not work. HaChu also supports some non-Shogi variants, in particular Makruk and Shatranj, which have the same restrictions on board size as Sho Shogi. (It even supports a crippled version of FIDE Chess, without castling and e.p. capture!)

To play, you just start WinBoard, and accept the default choices of the Startup Dialog, which ia thw HaChu engine set for Chu Shogi. You can then select Dai from the File->New Variant menu if you want to play that, and either start playing with white, or select Machine White from the Mode menu. (Note that 'white' is WinBoard speak for the side that moves first (sente), which might be a bit confusing for people used to Shogi). With Options->Time Control you can adjust the thinking time. If the engine is too strong, it can be dumbed down by specifying a time-odds factor for the first engine there; e.g. 10 would make it think 10 times shorter than the nominal time.

To play Sho Shogi is a bit more tricky, as it has to be played as a modified version of regular Shogi, with altered holdings size and a different initial position. WinBoard also has to be made aware the Drunk Elephant participates. The Startup Dialog contains an entry in the engine comboboxes that starts WinBoard with those modifying options, and HaChu as engine. This also instructs it to take the initial position from the included file sho.fen. For playing Sho Shogi you can select that entry.

HaChu can think in the time of the opponent, controlable through the WinBoard 'Ponder next move' setting in the General Options dialog. It can also be switched to analysis mode (in the Mode menu), where the user can move pieces of both sides, and the engine only ponders about those (showing its analysis in the engine Output window), but never moves itself.

HaChu supports a number of options that can be set through WinBoard's Engine Settings dialogs. These include options to modify the rules it uses in Chu Shogi. By default it plays according to the rules specified in the (English) Wikipedia. In these rules repetition of a previous position with the same side to move is absolutely forbidden, and pieces can promote when their move touches the promotion zone (i.e. they enter it, leave it or move in it), except on the first turn after they deferred (unless they capture). An option 'Allow repeats', when ticked, makes it consider repeats legal moves that happen to lose, unless they are check evasions, in which cases it thinks they win. This is a poor-man's (and probably defective) attempt to make it play closer to Chu-Shogi-Renmei rules. The option 'Promote on entry' limits promotion to moves that enter the zone from outside, or captures that touch the zone. The option 'Full analysis PV' (on by default) forces the principal variations shown during analysis to be full length, at the expense of a bit of search efficiency.

HaChu also implements a special mode to solve tsume problems, where you have to checkmate your opponent by an uninterrupted sequence of checks. It then only considers checks for the side that has to made (which you specified with the option), and evasions for the other side. This way it can search much deeper than when it considers all moves. If it cannot find a mate before it runs out of checks, its score drops to the level it would have when it will be checkmated itself.

Technical details

HaChu is an engine especially designed to handle huge Shogi variants like Tai or Taikyoku (on 25x25 and 36x36 boards, respectively). With such large boards and numbers of pieces, incremental techniques become very competitive. To get the alterations of the move list due to a move, one only has to scan along all rays through the from- and to-square, to get the old (disappearing) moves of the moved piece, new moves of that piece, and blocked and unblocked moves of other pieces. (The very few pieces that have Knight jumps can be treated special at negligible effort.) The computational cost of this only scales as the circumference of the board, while generating the move list from scratch would scale with the number of pieces (which again scales as the board area).

Another problem in the large Shogi variants that requires unconventional treatment is Quiescence Search. Pieces like Lions (and even worse, the Fire Demons of Tenjiku) tend to blow up a conventional capture search, which would consider every capture. The reason is that these pieces are very good at executing 'plunder raids', where both sides approximately keep the material balance by using their powerful piece to clean out the opponent. In Chess Queens tend to do the same, but can be easily stopped by considering the moves that capture the most valuable victim first. Because that will put a stop to the plunder raid as soon as the Queen captures a protected piece. Against Lions or Fire Demons protection doesn't mean a thing, however, as these pieces can end their move on a different square as the piece they capture was standing on. So special methods are needed to make sure the time spent in QS remains affordable.

Otherwise HaChu is a quite conventional Chess engine. It uses a standard alpha-beta search, with null-move pruning, check extension, killer heuristic, late move reductions. Its evaluation is a dynamical average of an opening and an end-game evaluation, interpolated as a function of the total board material. This accounts for the easy promotability of pieces that can slide forward, and hence their value increase, as the board population thins. The evaluation is mainly based on material, position (through piece-square tables) and mobility, but there are some special terms to avoid common strategic mistakes (such as venturing with an unprotected Lion into the opponent's corners, or leaving the corners unprotected against Lion invasion).

Future plans

Search improvements that are on the to-do list are singular extension for check evasions, and extension for Lion evasions. The incremental update at the attack map currently does not work yet, so that the attack map has to be generated from scratch in each position, which sort of defeats its purpose, and would start to hurt badly in variants larger than Chu. Fixing this has a high priority. In the evaluation terms for King Safety and Kylin handling are sorely missed. Tenjiku Shogi is nearly finished, and only the 'area moves' are still missing. For the larger variants, the hook movers still need to be implemented, and the mechanism of promotion on capture.