Virtual piece drops in bughouse

[ianfab]

Support for dropping of pieces not in hand yet is required for four-player variants in order to

• [x] consider potential drops in search

Split out from #64.

[antoyo]

Is this to avoid having to send a game state from one game to the other? Or will you also add a command to send a partner's game state?

[ianfab]

For a proper tree search in bughouse there are basically two options:

1. Treat the game as perfect information and run a combined search on both boards.
2. Treat the flow of pieces as some kind of source and run the search only on the board state of a single board.

Since 1. is infeasible for this project (and actually not even desirable if the engine should be able to play with any partner), the search needs to be able to traverse nodes where a piece is dropped that is not in hand yet. In which case this will be allowed is then another question (based on partner communication, deterministic, randomized, etc.), but the handling of virtual piece drops is required in any case. Only as soon as that works, the engine can tell which pieces it needs and which pieces its opponent should not get.

In principle I already implemented that a while ago, see https://github.com/ianfab/Fairy-Stockfish/tree/bughouse_virtual, but it needs some improvement, because the engine plays weaker due to worrying about too many virtual mate threats. Furthermore, it did not seem to be stable yet, but I did not have much time to test it or work on it recently, so contributions are very welcome.

[catask]

Just an idea, is there a way to determine how strong a potential drop would be? For instance if a potential drop would result in a -3 position then it would be beneficial to continue moving rather than sit for a piece to defend that potential drop.

[ianfab]

Yes, that definitely needs to be done when searching potential drops. In the above mentioned branch borrowing a piece that is not in hand costs twice the value of the piece plus roughly the value of a minor piece, so a drop that does not massively improve the position is evaluated as bad.

Nevertheless, that is not sufficient to limit drops, since as soon as the engine finds mate, the penalty does not matter any more. Therefore I additionally limited the total number of pieces that can be borrowed and also tried to evaluate checkmates while having a piece debt different from normal checkmates. So managing the piece drops is quite tricky.

However, the core thing is to get a first stable and reasonably strong version that has the ability to consider virtual drops in its search, after that it is much easier to play around with the restrictions to further improve it.

[jrwats]

Firstly, apologies for being completely unfamiliar with the codebase, and possibly talking nonsense. I was just happy to see there was an engine that even supported bughouse

1. Treat the game as perfect information and run a combined search on both boards. Since 1. is infeasible for this project

Wait, why is this infeasible? I assume the reason is technical (or prohibitively "hard" to code up?) like "Because the engine isn't setup to explore both boards?"

When it comes to "correctness", I think treating the game as though there were only 2 players controlling both boards (i.e. perfect communication / hive mind) makes a ton of sense for constructing the strongest engine

In my (naïve) mind, the decision tree should be Is your team up on time?

• No
  • Base case - Your team can't sit
    • Explore tree where the teammate lowest on time moves AND receives no new drops
    • Also Explore tree where the teammate with more time moves IFF it's his turn.
• Yes
  • Explore trees where board A makes N moves before a single move is made on board B (and vice versa). This is where it gets difficult. Make N too large and the tree explored on either board is too shallow. We're essentially increasing the tree exponentially by doing a search this way. For every "normal move" on a single board's minimax tree, multiply that by the number of possible moves at N-ply depth for board B. I'd guess the engine gets weaker after N goes higher than 3 due to the game tree not being able to be explored nearly as deeply. Perhaps smart memoization could help out here?

[ianfab]

The reason why I said that having a combined board representation is infeasible for this project is mainly that it is very hard to maintain the engine when the state representation of the supported games can be so different. I think for a dedicated bughouse fork of Stockfish this could be a perfectly valid approach, and theoretically it even has to be the better approach, it just does not fit the design of this fork.

From a game theoretical perspective I think the trickiest situation is when different sides are to move on the two boards, because then the action space contains moves from both sides (when treating it as a two player game). However, if I am not mistaken, it can never be advantageous to move first in such a position, assuming that the other side can react instantaniously and mutual checkmates on the two boards lead to a draw. The reasoning behind this is that worst case you can reach a transposition of the game state that would have occured if you moved first. If this conclusion is correct, then you can just assume that the side that is down on the clock always moves first, which simplifies the problem a lot.

Now that we eliminated this problem, we only need to reason about situations where the same side is to move on both boards.

• On the first ply you can choose on which board to play, so you need to search moves on either board.
• On the second ply you only search moves by the side that is down time.
• On the third ply again one side (the side that is up time) is to move on both boards. Same as on first ply...

This way one should easily be able to construct a single search tree that can be minimaxed the standard way. This of course does not consider that the engine can not move instantaneously and that the time up/down situation can flip while thinking. However, I think this can be anticipated by analyzing the clock situation before starting thinking and if you are only very minimally up on the clock do a short search assuming you are up time, and then start a search assuming you are down time. If you see that the difference is huge, then make the best move of the first search immediately, and otherwise continue searching assuming you are down time.

I hope this all makes sense. However, although I find this very interesting theoretically, as mentioned this is not really feasible to do as part of this project. Here we can just try to be pragmatic and find good heuristics to approximate such a smart combined player by two interacting players. Unfortunately I however currently do not have much time to work on bughouse either way, so if anyone is interested to contribute (e.g., starting by testing and debugging my experimental branch mentioned in this thread), that would be very welcome.

[jrwats]

Thanks for taking the time on the informative answer!

The reason why I said that having a combined board representation is infeasible for this project is mainly that it is very hard to maintain the engine when the state representation of the supported games can be so different

That's what I suspected (and feared), but that makes sense.

However, if I am not mistaken, it can never be advantageous to move first in such a position, assuming that the other side can react instantaneously and mutual checkmates on the two boards lead to a draw

I don't think there is such a thing as "mutual checkmate" in bughouse. Some player makes their move first. But I believe you're correct when say

it can never be advantageous to move first in such a position

Unfortunately I however currently do not have much time to work on bughouse either way, so if anyone is interested to contribute (e.g., starting by testing and debugging my experimental branch mentioned in this thread), that would be very welcome.

I'll let you know when I get time! I'm working on a bughouse-only app, and intend to have a handful of bots in there to play against.

[ianfab]

I don't think there is such a thing as "mutual checkmate" in bughouse. Some player makes their move first. But I believe you're correct when say

To my knowledge some bughouse applications treat checkmates that occur on the same move as draws, but I do not remember which ones. However, as you mentioned, even without that assumption the conclusion should still be valid in most positions, at least unless there is a mate in 1 on both boards.

I'll let you know when I get time! I'm working on a bughouse-only app, and intend to have a handful of bots in there to play against.

Thanks, sounds interesting. Apart from Fairy-Stockfish a few other well-known bughouse engines are Sunsetter, Sjeng, and TJchess. However, I think none of these is in active development, and Fairy-Stockfish is much stronger than all of them in Crazyhouse, so I would assume that with improved partner communication it should normally also be able to far surpass them in bughouse. Recently there also has been an interesting work on a NN bughouse engine, see https://github.com/TimSchneider42/lazybug/blob/master/report/report.pdf.

[ianfab]

Was implemented in 4a4eccc, remaining potential improvements were moved to a new issue.