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.