27

In many areas such as prediction and classification, ensemble methods tend to outperform individual methods. This made me wonder if it would make sense to pick a few of the top chess engines and work with them together to make a stronger one.

Let us assume the total amount of hardware is fixed to what people use for typical benchmarks, and that the time is fixed as well. In addition, we would not be changing the engines themselves to work together, but just making a wrapper around them that they are practically unaware of.

Hence my refined question:

How hard would it be to beat the number 1 engine in the world, by an ensemble of engines with fair resources?

1
  • Comments are not for extended discussion; this conversation has been moved to chat.
    – Brian Towers
    Jun 26 '20 at 10:23
24

The answer is "No".

If you have a defined fixed set of resources - CPUs, memory, cache, etc. - and you allow one engine to have full use of them then that engine is going to be able to analyse to a greater depth than if you take the same set of resources and split them in some way between several different engines. Inevitably the single engine analysing to a greater depth is going to perform better than several engines analysing to a much lesser depth.

1
  • Comments are not for extended discussion; this conversation has been moved to chat.
    – Brian Towers
    Jun 21 '20 at 18:45
16

No, an ensemble of chess engines won't beat the best one. The reason is simply because of hardware.

Let's take the strongest CPU engines right now to keep things simple. These are Stockfish, Komodo, Leela-CPU, Ethereal, Fire, and rofChade. Stockfish is the strongest. You have a four-core computer, running Stockfish. It's expected to beat all the other engines in a match on the same hardware.

If on the same four-core computer, you also simultaneously run Komodo, Leela-CPU, etc, then you are not just running inferior software, you are running inferior software on inferior hardware (because these engines will compete with each other for the same 4-cores). Therefore the ensemble loses.

It's true that each engine has its own strengths and weaknesses, but to fully exploit this, you need a human to look at the principal variations of each engine and select between them. This is why a human with access to all the engines is expected to outperform Stockfish alone in a correspondence chess match. But doing this requires human intervention; it doesn't work with engines only. You could conceivably write code that distinguishes between which engine is stronger in the current position, and this has been attempted, but it was never able to decisively beat the two original engines.

You are better off letting the best engine only play.

0
10

Though I am not able to test it myself, I am confident of the following conclusion:

An ensemble of engines should be able to beat the strongest individual engine

Here are my key assumptions:

  • Given typical time controls used for benchmarks, the time 'lost' by having a thin pre-evaluator before the engines would be negligible. As such we can say that the engines in the ensemble will effectively have the same sum of resources as the top engine.
  • Suppose the ensemble would want to run two engines at the same time, it would be able to give each of them half the resources.
  • Suppose the ensemble would want to run engines consecutively, it would be able to give each engine the full resources. The ramp-up time is assumed to be small enough if this is only done a few times during a game (but prohibitive if this would be done every move).

Also note that the ensemble would be able to contain a copy of the strongest engine itself. At time of writing the engines following the strongest engine are not far behind so this is not a critical point, but otherwise it would become a question of 'how much rating would an ensemble gain over its strongest member' which is significantly harder.

Scenario 1: Engines are stronger in different phases of the game

An easy 'win' here would be if one engine had a stronger (interaction with) an opening book, and another with an engame tablebase. However, even assuming all engines can use the best resources in these area with equal efficiency, then it is still commonly said that certain engines are 'strong in the opening' or 'good at endgames'.

Let me make an additional assumption here:

  • I assume that engines that are good at a certain phase, do not have a strong dependency on other phases to realize this.

So, the engine that would be good at endgames would not only be good at endgames it reached itself, but also at endgames that were reached by another engine.

Most straightforward solution: Identify a phase of the game, and let that be played by the engine which is strongest at it

In case we just distinguish between opening and endgame it would be trivial to define a wrapper for this, and there would be about 1 switch per game. Of course this could be extended if you have an engine which is 'great at pawn endgames' or 'very good at positional games' but at that point it would already become harder to identify which engine to choose without using significant resources.

Scenario 2: Engines can find critical continuations for critical moves

This scenario is what I was originally curious about. However, based on my assumptions the most straightforward way to get the opinion of several engines would be to let them run in parallel. Suppose we just use an ensemble of two engines given half the resources, then they would both be a bit weaker, let us make another assumption based on some references.

  • In a typical setting strength scales logarithmic to the available resources, and halving them reduces engine strength by 50-100 elo

Now that is significant, honestly it may be too much. Suppose we just put two engines against eachother with a 70 elo difference, the expected value would be about 60-40. That is a lot to make up for, but though I was unable to find any data on this, it may still be possible. Basically this just needs to result in 1 brilliant move or 1 averted blunder to swing an entire game. It would not be trivial to decide which engine to listen to on each move, but as engines typically can output some basic statistics (like their evaluation of all possible moves, and how deep they checked each one) it would probably not be too hard to make a reasonable and still lightweight decision.

Possible alternate solution: Run engines in parallel and pick the best move each time.

Again this could be extended, a simple way would be to have 3 engines, and pick the move that 2 of them give, but I am not sure if splitting the resources even thinner would be worth it. Another interesting idea might be to give the strongest member of the ensemble the most resources, and have it being sanity checked by the member which is best at this. In this case the main engine might only lose 10 elo points due to reduced resources so 'making up for it' could be a lot easier. But again, it will remain tricky to select the right move.

A final thought would be if engines use CPU and GPU, then perhaps the strenght of individual engines may not scale down too much in each of these resources, so a mix where engine one gets 80cpu+20gpu and engine2 gets 20cpu+80gpu may leave the individual engines nearly as strong as when they had full resourses.

Conclusion

Especially when engines can be run one at a time, it should be able to get better performance, though there must also be ways to get better outcomes by running multiple in parallel. However, this is not trivial.

Taking the ensemble concept really to the next level would likely be possible with small changes in the engines, for example not only providing the expected value of a score, but also how confident they feel about their evaluation.

2
  • Comments are not for extended discussion; this conversation has been moved to chat.
    – Brian Towers
    Jun 21 '20 at 18:45
  • iirc, an ensemble only uses final data from each engine, and does not consider the position of the board by itself: if it looks at the board, or chooses lines to send to analyze for different engines, then strictly speaking, it would be a whole new engine in itself. Sep 8 at 4:41
7

Nope, at some point a legal move is selected as best move. Who ever makes that decision can't be better than the best engine. Otherwise there is a new best engine.

2
  • 2
    This question sounds rather like a chess-flavoured version of the interesting number paradox. Jun 23 '20 at 14:56
  • @richard I am not confident enough to say that it is unrelated, but I have looked at the interesting number paradox and don't see how the solution would map to this question yesterday
7

The answer is more complicated than you want to try to make it. Any definitive "yes" or "no" answer begs the questions of the conditions of the match, the hardware used, and the difference in strength of the players involved. Instead of answering your question directly, here I plan to go through the thought processes needed which guide the creation of a particular kind of ensemble engine which would be able to beat the "strongest" engine. The alternative is actually answering your question, which in my experience no one actually knows the answer to.

Also, if you're not familiar with the open source Leela Chess Zero (Lc0) Neural Network (NN) engine, that should be your first topic of investigation. It was inspired by the infamous well-marketed, closed source, unavailable to the general public, and was the icebreaker for the Neural Network techniques AlphaZero (A0), which has some papers that you also might want to explore to understand.

Neural networks have introduced new frontiers which previously have only been roughly explored for the past 10-15 years. Only in the past 3 years have they become adequate to be able to "beat" old approaches which involve human programmed chess-specific evaluations, and heuristic driven alpha-beta search, like the open source engine Stockfish. Given that the hardware requirements for pure neural network engines are more Graphics Card-oriented while the requirements for an engine like Stockfish are CPU-oriented, hardware is a huge factor in making your ensemble.

When you finally have settled down on what hardware you've decided to use, then you can think about which engines are strongest by testing them out. After that, you need to code an approach to ensemble which engines you want to use to try to beat it. Keep in mind that many of today's engine's strength rely very heavily on their search, so any diversion of resources from deep search will limit your ensemble's search depth.

A Leela (but technically not Leela Chess "Zero" since it is using non-"Zero human knowledge" games) network named "Antifish" was brought to life, which was trained on several millions of Leela games and Stockfish games. Hypothetically, the network would "know" how to beat Stockfish since it has seen many of the games which involve Stockfish showing weakness. Antifish may be "stronger" against Stockfish, but does not compare the same way strength-wise against engines of a similar kind like Komodo and Ethereal. Also, the network hypothetically performs better relative to Stockfish at less time given since the training set was highly polluted with Stockfish blunders at lower time controls. Antifish may have once performed well against Stockfish, however it is out of date and potentially is weaker. Antifish is what we call an "adversarial" network, specifically trained to exploit weakness in Stockfish at lower time controls, and even though it may be stronger than certain versions of Stockfish, it is not "objectively better" (debatable term) at chess in general.

I bring this up because it is possible that we could use Leela's Antifish NN at the root of search just to help guess what some other Leela network should start searching. To my knowledge, this "network ensemble" has not been done yet, and the resulting engine may actually be able to beat Stockfish better even though Antifish and the other network we might use could be weaker.

Also, there is a fork of Lc0 that allows an "auxengine" to suggest moves to Lc0. "Leelafish" is technically an ensemble of both Stockfish and Lc0, and actually could be stronger than its parts. It is a work in progress currently and communication between the two engines only goes one way.

In essence, ensembling engines could lead to something stronger, or it could not. But what is important to note that any conglomeration of engine suggestions or two-way communication between engines costs computational resources, and that cost could be too high. It might just be better to merge every good idea into a single engine, technically no longer making it an "engine ensemble."

3

Yes

If the engines are learning engines, rather than stateless deterministic evaluators, then I think it is obvious that an ensemble would be stronger, for the same reason that I think a team of human chess players will, on average, beat all of the individuals in the team in a matchup. The hard part is deciding which move to use when multiple engines produce an answer. For this to work, I think the engines would need to offer a move, a score, and a confidence value. You would then choose the move with the highest score * confidence product.

Rationale

Ensemble methods are common in machine learning circles because it is nearly impossible to produce an optimal algorithm for every possible scenario. It is much better to train likely scenarios and let sub-algorithms (like, a forest of decision trees, for instance) specialize on subsets of the scenarios with good generalization properties.

Clearly, AlphaZero is better than all other engines thus far, but note that it is a kind of jack-of-all-trades. What if someone tried to train "specialist" variants of AlphaZero which focus on particular strategies, even at the expense of not being the strongest general player? Remember that AlphaZero has not and cannot possibly explore the majority of the chess space, because that is infeasible. And its play style is ultimately guided by the luck of the plays it has already encountered. It is possible that a more narrowly focused algorithm could beat it if it could force a game state which AlphaZero rarely played, but it played many times. Now, repeat this for a large number of "specialists", and you then have a team of experts that can activate based on a variety of board states. Individually, they would all be worse than AlphaZero over a large number of games, but collectively, they could beat it because over a narrow set of games, they might consistently beat it (even if they themselves were mere instantiations of AlphaZero, but with a different training regimen).

In this architecture, each specialist would know how much it "likes" the current board state, and would use that to determine its "confidence" in the proposed move. This would cause the specialist with the most experience in the current board state to generally control the game.

From a computational complexity perspective, the ensemble would be smarter because it stores more information than the solo system, so it has more weights to optimize over a broader swath of the game space. This is obviously not a rigorous argument, by any means, but perhaps it is helpful.

1
  • Comments are not for extended discussion; this conversation has been moved to chat.
    – Brian Towers
    Jun 21 '20 at 18:48
2

Will note that engine strength is not strictly transitive, as in A<B, B<C, but "not A<C" is consistent. Minimax is the strongest "engine" by brute-force, and as such we assume your question does not include minimax. As such it is unclear what is meant by "number 1 engine".

On the other hand, it is relatively trivial to produce an engine ensemble using strictly weaker engines, that, as an ensemble, is strictly stronger.

Let S denote a strong engine. Let V denote an engine that is marginally (but consistently) stronger than S. Let O denote an engine that makes the same moves as V, but strongly blunders the opening. We can define a similar M for the middlegame, and a E for endgame.

Note that an equally weighted ensemble of {O, M, E} is equal to V, but V is stronger than S, so the ensemble is stronger than S. Also note that each of O, M, E are weaker than S, so the ordering of strength is satisfied.

Note that the strict definition of "opening, middlegame, endgame" does not matter, as long as "regular progression" is maintained, and most critically, is well-defined. Note that the requirement of S being "marginally better" than V is such that for each of O, M, E in isolation, we can still expect the "blundering move" of each engine to be made, since the transition into each stage of the game is to be expected for engines of similar strength.

Obviously, it is problematic to define an engine which is "number one" but includes a clause of "stronger than number one" in its definition, but the point being is that in the space of engines with respect to strength (given some board position), transitivity of strength is not a total order, and thus several arguments in response to the original question above are not strictly correct.

New contributor
k.c. sayz 'k.c sayz' is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
4
  • will quickly note the very amazing observation that the ensemble engine is a linear combination, meaning that the operational details of each of O, M, E are not specified. meaning that its a ensemble proper Oct 14 at 20:04
  • another observation being that, O, M, E all require computational resources equal or less than V, meaning that the ensemble is as well defined as V itself. meaning that though the piecewisely constructed engine may be "improper", it is still well-defined! Oct 14 at 20:06
  • however, if your engine is not deterministic, and the method of non-deterministic move generation is not specified, then the above analysis might not be completely formal, as, for example, the engine E might mate the engine S early on; thus "marginally better" Oct 14 at 23:00
  • I am not qualified to judge if this is actual proof for the situation, or whether a critical assumption is made which does not hold well in practice, but definitely gave +1 for the analysis! yesterday
0

It depends on the parallelizability of the best chess engine. If the engine has not be implemented to efficiently run on many distributed computers and coordinate the results, then an alternative engine could theoretically exploit that.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.