8

Every chess engine I've ever heard of (including all I found listed on Wikipedia) uses brute-force search with an evaluation function (minmax algorithm) to decide on its move.

This is not how most humans approach the game, employing general pattern recognition instead, so in principle, it would be possible for computers to do the same.

Is there any chess engine that does not rely on the brute-force approach to find its moves?

3
  • 9
    Magnus Carlsen. ;) Mar 18, 2014 at 13:40
  • 4
    Regarding the people who say modern engines aren't brute force because they prune moves... I think it is pretty clear that when a chess engine evaluates tens of millions of positions, it is using brute force, regardless of the eyebrows someone might draw on the algorithm.
    – Tony Ennis
    Sep 30, 2015 at 11:50
  • 1
    Modern engines can miss moves, eg. sacrifices where the payoff isn't until quite deep. I think this is probably because they get pruned and not examined deeply.
    – A passerby
    Sep 30, 2015 at 12:07

7 Answers 7

5

There were attempts back in the 1980s to write chess engines with knowledge bases that would pick candidate moves like humans, but they were unsuccessful. The problem is that human pattern matching is difficult to put into words, so creating the rules for the knowledge base was extremely difficult.

Training a neural network to pick candidate moves seems like a promising line of research. Here and here might be two pertinent papers. (FWIW, It is not my field of Comp Sci)

4

You might take a look at Giraffe which was recently in the news:

https://thestack.com/iot/2015/09/14/neural-network-chess-computer-abandons-brute-force-for-selective-human-approach/

The hype is that in 3 days it taught itself the game and reached IM level. On the other hand the research is at

http://arxiv.org/abs/1509.01549

1
  • Not exactly true... See my answer.
    – SmallChess
    Oct 1, 2015 at 1:21
4

I'd like add details to @Ian_Bush's answer on Giraffe.

In @Ian_Bush's answer, it's noted that Giraffe doesn't use brute-force computation. This is not right, because Giraffe is still an alpha-beta (nega-max) engine. The only difference to a standard engine is that the evaluation function is tuned automatically by deep-learning. Therefore, the engine learns how to play by itself.

Traditionally, engine programmer self-tunes parameters in an engine. I've done a lot myself. For example, how much weight should you give to a bishop and a knight? 3.0? 3.1? 3.2? It's hard to tell.

Giraffe approaches the problem in a much smarter way. It starts off with some initial values. The engine uses the gradient ascent algorithm to tune those values. We don't have to explicitly code how much weight a queen should be in the code. This is what we mean "learning". It doesn't mean that the engine can play chess without searching.

EDIT: Giraffe models the tree nodes as probability that they fall into the principal variatation. Check the paper for details. I personally don't believe this approach, and the paper shows little evidence how useful it would be.

3
  • 1
    Is it true that Giraffe use Stockfish eval as target? If so, it doesn't "learn chess" by itself, it just learns an approximation to Stockfish eval using a nnet on top of board features.
    – Fernando
    Nov 16, 2016 at 14:05
  • @Fernando Giraffe doesn't have anything to do with Stockfish, I believe.
    – SmallChess
    Nov 16, 2016 at 14:06
  • 1
    I'll read the entire paper, but on page 18 it says: We evaluated board representations by training neural networks to predict the output of Stock- fish’s evaluation function in a supervised fashion, given 5 million positions as input, in the board representation under evaluation. So, this is not learning by selfplay IMO.
    – Fernando
    Nov 16, 2016 at 14:51
2

Claude Shannon proposed two types of algorithms for creating chess engines. A "type A" engine examines all possible moves to some finite depth, minimaxes the tree, and then plays the move with the highest evaluation from the minimaxed tree (a.k.a. brute force). Type B engines limit their search to only a subset of possible moves based on some criteria. I believed he favoured Type B as more promising.

The engines that were created in the 1970's (eg. Hitech, Kaissa) tended to be pure brute force with no pruning or just alpha-beta, but people soon saw the value of pruning the tree of moves and lines that were unlikely to prove strong. Almost all recent engines prune the tree of lines that are clearly weaker (alpha-beta), and most engines use various types of forward pruning as well (futility, late move reduction, null move, razoring). In that sense, there aren't many engines that use pure brute force anymore.

In the 1970's, Botvinnik was working on an engine called Pioneer conceived around the notion of attack paths which would have been evaluation guided. It never reached the point where it could play a full game of chess.

In the 1990's, Chris Wittington spoke out in favour of using incorporating more chess knowledge, and created a program called Chess System Tal which was fairly strong for its time.

Kasparov, Anand and Tord Romstad have all noted that Hiarcs seems to have a more detailed evaluation than many of the top engines whose strength comes from a fast search.

2

Its sort of debatable if you can call a heuristic based search and evaluate approach as brute-force. Most of top-tier chess engines today follow a rules-based approach to evaluate a position and a rules based search function to prune moves.

This is actually not guaranteed to pick the "global optimal" move, however these moves are good enough for purpose. In this sense most chess engines are using an approximation on the global optimum and actually getting by.

To date, we haven't many chess engines succeed at the top level using a different approach, at least not on cheap hardware.

0

I heard, I think it was GM Matthew Sadler on his Silicon Road channel, of grandmasters running Leela at zero or very low depth to test only how good its neural network board evaluation is. This is in spirit less "brute force" and more "understanding" (although training the neural net took a lot of computation!).

Discussion at Leela mailing list: If restricted to a "human number of nodes" to evaluate, who wins? Leela or GM?

There was a claim that Leela with 1 node or 10 nodes of evaluation (effectively no search at all) played at 2300 Elo or IM level. For comparison, Stockfish on a laptop can search 1M+ nodes/sec.

-2

Basically all of them!

Chess engines really only use brute-force when:

  • told to
  • are analysing positions (problem solving)
  • Looking for a checkmate (problem solving, not when playing against, like "find the mate in N" style problems)

Otherwise they have a "selective search", this will consider all the possible moves for a given board layout, but only explore a handful of them. An engine may switch to brute-force though if it rates two moves very similarly (more than one strong move) or if it cannot find a move it likes (no strong moves).

They also tend to brute-force as a last line of defense, if you've seen a checkmate chances are it can see it coming and it will want to try really hard to draw, and cannot find a way out (the "Horizon effect" is a problem with engines, suppose it is going to loose it's queen, and it's been capped to only go 4 plays deep; if it can trade pawns and postpone that loss of the queen for 4 moves it will think it has saved the queen, in the process it'll loose at least 1 pawn (as the next move brings the horizon from before closer) and the weight it places on saving the queen may mean it sacrifices some defense, for nothing if the death goes over the horizon).

It will also brute-force when the selective search isn't very useful. This is why engines take longer when they have like 3 pieces left. They have to brute-force because the selection algorithm cannot rate a move. The selection algorithm is great during the midgame because it can be like "Oohh, doing this with the pawn blocks his [whatever] and backs up my [whatever] and [whatever] which I have a lesser number defending than attacking" - for instance.

If you have a king in the middle of the board there are 8 moves, the selective search will be like "None of these do anything useful, I can't tell".

You can think of the selective search as having two parts, it is tactical in the sense of it'll try and spot tactical moves, it will ignore the weight of the pieces involved usually because a queen not a part of any strategy is not worth more than a pawn vital to it. It is also strategic in that it'll explore moves that bolster a defense, and open up later to potential attacks.

The engine then does the same from your point of view, and back and forth and back and forth.

Something called a transposition table is a big list of things it has thought about, that way if it ends up considering something it has already done, it knows and doesn't have to re-evaluate it.

UNLESS (selective :)) it gets there a different way, or wants to explore further. Suppose for example it discovers that your ... rook is essential to an impending attack, the engine may re-evaluate a line when it discovers this. The previous weight it put on that rook (eg 5 points, how important it is to you) might be an under-estimate.

The selective search can also backtrack, like say its considering a bishop moving right into enemy territory, to the move selector it is not important that it can be taken easily. Say it discovers that strategically that is a superb move! It may then backtrack to try and find a way to protect that square to get that bishop there. Suppose it involves a pawn to do so.

The brute-force method would consider the line involving that pawn move, and (by brute force) the bishop move too, and the same stuff that rates the board position (the selective search itself) will say "this is good" so the board rates that variation highly, both find it.

It's very hard to rate a position using the brute-force method, this is why the selective search works so well.

The brute-force from the starting position might find that famous mate-in-4 that involves a queen f7 covered by a bishop, and if it were to rate that highly (I'VE FOUND A CHECKMATE! JOB DONE! PLAY!) it'd be wrong because black will obviously counter. The selective search rates a position (for further evaluation) because it is appears to be good. This means when it is considering your response it can decide what would be good for you....

So the stuff that the selective search uses to rate things is used by the brute-force one anyway because "found a checkmate involving this move" is not enough to say that move is good.

Hence What are the first moves chosen (White), by brute force chess engines?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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