Shogi

[hgm]

I don't understand what is interesting about Shogi. Almost nobody in Holland knows this game.

You should not think so nationalistic. This is the internet, not the hollandnet. When hundreds of people are very happy they can use my Chu Shogi engine, why should it bother me that they all live in Japan, and that there are only two people in the Netherlands that have heard of this game?

Standard Shogi is one of the three world's most-played forms of Chess, after Xiangqi and Mad Queen (= FIDE). Millions of people play it. And objectively, it is a better game than the form of Chess that is popular here. It is also much more interesting to build an engine for it, as it poses challenges that are so far truly unsolved.

[hgm]

I'm playing Sjaak against GNUshogi at the moment, just to get some baseline for how strong/weak it is. Not sure this is helping much though, since Sjaak is eating GNUshogi alive and GNUshogi seems to have some issues (like horrible time-management).

Well, GNU Shogi is 'asymptotically weak'. There also is a mini-Shogi version, (gnuminishogi) and I could beat it by hand! (In one of the first mini-Shogi games I actually played myself.)

[Evert]

Is there a consensus on the ordering of drop moves?

I don't mean where they should be in the move list, though that is an interesting debate as well (I order them as late as possible, and keep a separate history table for them as well). What I mean is: should a pawn drop be searched before a rook drop, or not? I originally had it so more valuable piece drops were tried first, but I wonder if it wouldn't be better to keep powerful pieces in reserve. The test is currently running and so far it looks like my initial ordering is best, but I'd be curious to hear about other ideas.

I'm also considering if it's worthwhile to extend if it turns out that the best move is a check-drop, which gets countered by an immediate capture, while the null-move search returned a mate score. This suggests that we're just trying to push a mate score over the horizon. Any thoughts on this?

[hgm]

Is there a consensus on the ordering of drop moves?

I only know for Shokidoki, and there I start with Pawn drops. I never tried it the other way, though. The drops are truly late moves in Shokidoki; they aren't even generated untill all other moves are searched. (Except the ones that are killers.) So I never thought much about their sorting. Of course you could also sort them by dropsquare, rather than piece type.

I guess one could keep a sort of drop-history table, and sort by that. If I would try a completely static sorting, I would probably base it on what the drop attacks (and sort MVV-wise). Just keep a bitmap of what drops you already tried (e.g. one byte per square), and then geenrate all drops that attack a Dragon, then Horse, then Rook, then Bishop.... What is truly useless can be tries by scanning through the bitmap as a last step.

I'm also considering if it's worthwhile to extend if it turns out that the best move is a check-drop, which gets countered by an immediate capture, while the null-move search returned a mate score. This suggests that we're just trying to push a mate score over the horizon. Any thoughts on this?

Well, evasions are already extended as normal check extension, I suppose. So extending the check-drops as well will open the possibility for infinite recursion. I tried to search check-drops in QS, which is similar. It always was a disaster. (Instant crash due to stack overflow.) I looked at the lines that reached the maximum depth (of 100 ply), and the checks and evasions just go on forever. No matter what I tried in term of restricting the drops, or sorting those, or the evasions, it always crashed.

[Evert]

I only know for Shokidoki, and there I start with Pawn drops. I never tried it the other way, though. The drops are truly late moves in Shokidoki; they aren't even generated untill all other moves are searched. (Except the ones that are killers.) So I never thought much about their sorting. Of course you could also sort them by dropsquare, rather than piece type.

One day I should look into a staged move generator. I generally reduce all drops by 1 ply, unless they are next to the enemy king. Drops that are on my own half of the board, or have negative SEE are reduced by 2 ply. Near the leaves, drops with negative SEE are pruned outright. I tried doing some drops in QS, but ended up removing that code again.

So far (after 1000 games or so), for me the version that sorts drops in order of piece value is scoring 55% against the version that does inverse ordering.

I guess one could keep a sort of drop-history table, and sort by that.

Oops.
I actually have one of those, but it ends up never being used for sorting moves in the end…

Guess I'll have to fix that next.

Well, evasions are already extended as normal check extension, I suppose. So extending the check-drops as well will open the possibility for infinite recursion.

Indeed. I would only do this in the very specific situation I mentioned: near the leaves, when a drop that ends up being captured immediately counters a mate threat. It's probably just a spite-check.

I tried to search check-drops in QS, which is similar. It always was a disaster. (Instant crash due to stack overflow.) I looked at the lines that reached the maximum depth (of 100 ply), and the checks and evasions just go on forever. No matter what I tried in term of restricting the drops, or sorting those, or the evasions, it always crashed.

I've tried it too. It didn't crash, because after a certain depth my QS devolves into a static capture evaluation (I haven't tried restricting it to a capture search yet), but it very clearly didn't help either. It just explodes the tree for no obvious benefit.

[hgm]

Spite checks are probably not really a problem. The fact that they give away material, is usually enough to make them fail low. There really isn't any point then into proving they failed low by getting you mated. The only case where this would make a difference is whe the opponnet in a side branch sacs a lot of material to finally achieve a 'brink mate' (hishi), and that you then unjustly think you can defend against the brink mate by surviving on spite checks to the horizon. But this is pretty rare.

My guess is that it would work better to declare such sequences of spite checks that go all the way to the horizon in the presence of a to-be-mated window as an outright loss, rather than extend it.

[hgm]

I guess the above is not really true: the window does not have to be at a mate score. What you want to prevent is that with some non-mate-score in the current PV, there is a side branch where the opponent sacs a lot to put you in a brinkmate position (e.g. draws out your King with a number of drop checks), and that after that you can hold off the mate long and cheap enough to survive to the horizon, and still come out positive. And thus imagine that you will not be mated, after running out of spite checks.

This is recognizable by the fact that after the sacs, when you are very much ahead in material, and thus would expect the null move to fail high, it will in fact fail low with a mate score. You don't have to be afraid alpha-beta will be lazy, and return a very loose upper bound, because you are so much ahead in material that the only way he can push you back bllow lapha is by checkmating you.

So the situation where eval >> beta and null move gets you mated is the signature of a brink mate. From there on every branch that leads up to the horizon with only checks is suspect. The burden of proof is then on you that you actually defended against the mate rather than just having pushed the inevitable mate over the horizon. And by keeping him in check you cannot deliver that proof. Only a non-check can do that. So if there isn't any, you'd better assume your checks will eventually run out, and you will get mated. And normally you will end (after his last evasion, which he gets extended for) in a situation where you can decide to stand pat based on the eval. So this should in any case be forbidden. You must either fail low on the assumption that your checks would not have solved the fact that you stand to be mated yourself, or extend with a null move to see if you can survive that.

The problem is that the brinkmate might still be lengthy, even if unstoppable. So by first giving some spite checks and then attempting to clear the situation by null move you might have reduced the remaining depth after that null move so much that you cannot see the mate for him anymore. The only method I can see to avoid that is by not lowering the depth for this 'clearing' null move at all. Which does sort of amount to giving a double-extension to the spite-check + evasion, and so probably is unaffordably expensive.

[Evert]

I guess one could keep a sort of drop-history table, and sort by that.

Oops.
I actually have one of those, but it ends up never being used for sorting moves in the end…

Guess I'll have to fix that next.

This actually looks like a very nice improvement so-far: scoring 55% at the moment.

[hgm]

The main problem I always encounter, which prevents me from searching the tree I really would like to search, is that as soon as you eliminate check + evasion from the depth count completely, you lose iterative deepening, and it becomes a pure depth-first search. And as some as the branches are infinitely long, depth-fist is not feasible.

In particular, when you are trying to figure out if checks will lead to mate or ar just spite checks, the problem is that many of the checks will be sacrificial spite checks where he just captures the checker. This will give the opponent many pieces in hand, which he will subsequently use to evade distant checks by means of 'futile interposition drops', which are then immediately taken by the checking slider, replenishing the hand from which the check-drops are made. This mix of sacrificial checks and futile interpositions in general keeps the branch alive forever.

This could be avoided by traversing the tree as an iteratively deepened fixed-depth search. This would guarantee that you identify the 'exits' to the tree, where either one side has run out of checks, or the other side is mated, in the order of their distance from the root. These exits then prune the tree of the next iteration through alpha-beta, pruning the pointless checks in all nodes where a mate can be forced, and all futile interpositions where an escape from checks can be forced. That leaves only the branches open that are truly undecided to the given depth. Often these run into repeats, as a third possible exit of the tree.

One advantage of iteratively deepening the tree is that you can abandon it it situations where it truly gets out of hand, admitting that the result is unresolved rather than getting stuck. But you could also use information from the previous iteration for move ordering, to traverse the tree in the next iteration in a way to enhance the probability for quickly finding a new exit. E.g. by searching the sub-tree with the smallest remaining branching factor first.

[gbtami]

I don't understand what is interesting about Shogi. Almost nobody in Holland knows this game.

First try to play some crazyhouse game on FICS. You have to taste how the so called drop moves can change the dynamics of game. Shogi has other differences (some new figurine types etc.), but the main difference is the drop move IMO.