Viability of 4 player chess engines

Question

I got into a discussion with a friend recently about the viability of 4 player chess engines. He claimed that they would be impossible to create at anywhere near the level of modern chess engines.

I'm by no means an expert on engines, but I do understand some of the concepts behind them to a degree. Here's my take, and I'd appreciate some more knowledgeable input on where my logic is wrong.

Taking an average branching factor of 35 in normal chess, I'll give 4 player a branching factor on average of 130. I reached this by taking the normal average of 35, and adding the maximum number of extra moves outside the usual 64 square board from bishops, rooks, and queens, resulting in 107. Then you'd need extra headroom for the other pieces, because even if they can't take advantage of the extra squares, there is generally more open space on the board in this variation, allowing for more legal moves. However, the number that should be used for that is kinda tricky for me to figure out, so I've taken a guess with an extra 23 moves to round it to 130.

For a branching factor of 130, you get similar number of positions after 18 moves as a branching factor of 35 after 24.65 moves (about 112 undecillian), this will be brought up again later. This was reached by using log(35, 130^18).

With regards to pruning, in my opinion it would be far more effective in four player chess, as an increased number of pieces that can attack you means there are far more effective strategies against you, and far more moves you can make would result in very low evaluation. I'm not sure how having four players would impact the search tree though, as alpha beta pruning uses an adversarial search tree, but I'm not going to worry about that too much.

Modern engines certainly have the capabilities to calculate forward 25 moves with pruning, and as I think the pruning factor would be increased in 4 player chess, I believe looking forward 18 moves with pruning is certainly feasible.

I realise this is all a massive approximation and my logic may be completely wrong on many counts, but what are your thoughts on the viability of effective 4 player chess engines?

As a side note, I'm aware that this question may be toeing the line with subjectivity rules, but I do think it should provide technical and theoretical insight on the nature of engines from those more experienced in them, which aids in the site's goal of learning. As such though, please include justifications in answers like how I've done in my post to avoid purely opinion based discussion.

Answer 1

Which version of four-player chess are you interested in? There's some discussion at the Wikipedia page for four-player chess. A key question is whether or not it's effectively a two-player game (e.g. with each pair of players opposite each other playing for the same team).

If it's a game between two teams, I don't see any obstacle to developing a strong engine (given sufficient time and resources) - it has been done for many chess variants and other games.

For a game involving more than two independent players, everything immediately becomes much more murky. For multi-player games, it can be very hard to define what is an optimal strategy, or the value of a position, or anything like that. You would often be in a position where none of the players has a way of guaranteeing not to lose - if any one player is ganged up on by all the others, that player is at a severe disadvantage. Sometimes it's possible to define a scoring method in such a way that the notion of an optimal strategy still exists, but (unlike in a two-player game) you can be disadvantaged by an opponent deviating from the optimal strategy.

Answer 2

First, I agree with James Martin that the question is difficult to answer for a free-for-all four-player chess because even the definition of optimal strategy becomes unclear. So I’m going to assume that we are talking about a two-versus-two variant and focus on the branching factor aspect.

The short answer is, I think it’s totally possible to build an engine on the level of modern chess engines if you use the right kind of engine.

For traditional game engines like Stockfish, the large branching factor is indeed a significant obstacle. This was the main reason why humans remained unbeaten in Go two decades after Kasparov was defeated by Deep Blue. Until AlphaGo came along. It used a very different kind of architecture that heavily relied on deep neural networks. It used two neural networks: the “policy network” proposed the next moves to play and the “value network” estimated the position. Then came AlphaZero, which taught itself to play chess, shogi and Go from scratch without any human supervision, and for each of those games became the strongest player among all humans and computer engines. It used a different but similar architecture. Thanks to the policy network, AlphaZero didn’t need to evaluate nearly as many positions as traditional chess engines did (there’s a nice graph in the middle of the article about AlphaZero). You could imagine the policy network as an intuition that allows the engine to “feel” which moves look promising and not waste any time looking at the vast majority of moves.

Since then Stockfish has been updated and it is now the strongest chess engine once again. But Leela Chess Zero, an open-source successor to AlphaZero, is a close second. In the Top Chess Engine Championship, it won in seasons 15 and 17 (2019–2020) and has been the runner-up every season but once since then. The difference in strength is minimal. On 2024-05-10, TCEC estimated Stockfish to have 3659 ELO vs 3630 ELO by LCZero.

To sum up, neural network based chess engines have played at a level very close to (sometimes above) that of traditional chess engines for the past several years. And for them, the branching factor is not a problem. The average branching factor for Go is 250, and AlphaZero was able to completely dominate the game. So my intuition is that if you train an AlphaZero-like chess engine for a chess variant with a branching factor of 130, it would feel totally comfortable there.