12

I've been interested for a while about a computer chess AI algorithms (and got the chance to work on one at some point) like Minimax, and as the core component of these algorithms is the so-called evaluation function to determine what is a good board configuration, and what is a bad one.

In other terms, given a configuration of your Chess board, how do you determine that it is to your advantage, and with what degree of confidence?

For example:

  • If you own the center, this is rather favorable.
  • If you have more pieces than your opponent, this is rather favorable.
  • If you lost your Queen, this is rather not favorable.
  • If you have a pawn that is close to being promoted this is favorable.
  • ...

So I would like to ask for some advice on how to create a good evaluation function, based on some expert knowledge about the Chess game in general. And if possible, a degree of favorability (say between 1 being very not favorable, to 100 being extremely favorable).

The idea in the end is to be able to create an algorithm that will look in the tree of possibilities up to a certain depth and evaluate what the most favorable configuration for next move is (taking into account several moves in the future) based on what is favorable to the player and not favorable to the opponent. But without a good evaluation function the algorithm is nothing.

  • I think this question would do well on StackOverflow. There are a lot of questions on there already regarding Chess AI – xaisoft May 10 '12 at 18:05
  • 2
    I thought to post it on SO before, but I'm almost sure it would be closed as not constructive or not a real question there. Maybe if I need more emphasis on the code itself, but I think for the evaluation function it requires knowledge about chess, not so much about code or algorithms. – Charles Menguy May 10 '12 at 23:36
7

Here's a good starting point. Material comparison is key (and easy), then you can tune that to consider positional aspects like open ranks/files/diagonals, pawn structure, etc.

http://chessprogramming.wikispaces.com/Evaluation

3

Adding up to the answer by @Wes Freeman, I would suggest looking up how does the best computer engine in the world, Stockfish, evaluate a given position. As the source code is open, you can do it for free. I think the file with the evaluation function you are looking for is this one.

2

I have a feeling I'm a little late on this answer but - I'm also in the process of making an engine. The source code is in Python (which is fairly easy to read, even if you don't know it) and is available here if you wish to read it. The list of currently active 'heuristics' (at the time of posting):

  • Farther developed (closer to the opposite side) pieces are better
  • Pawns closer to promotion are good
  • Kings are scored separately based on what phase the game is in (opening, midgame, endgame)
  • If the player has both bishops, that receives a bonus
  • If the player has castled, receive a bonus
  • Isolated pawns (pawns with nothing around them) are not good
  • Doubled pawns (two pawns on the same file with no gap between) are not good
  • Having all 8 pawns is not necessary a good thing and is penalized (they clutter the board and get in the way)
  • Have a look at this great evaluation function which is also used
  • Bishops with more pawns on the same color square as the bishop are penalized (they aren't as good in crowded situations)
  • Not yet implemented, but planned: Knights get a bonus in more crowded situations

In one of those points, I mentioned the 'phase' of the game (e.g. opening, midgame, endgame), and if you wish to include that in your engine, you'll probably run into the same problem as I did: there's no clear line separating those. My function that decides what phase the game is in uses a few things:

  • Amount of material on the board (as soon as any piece is killed, it marks the game as not in the opening)
  • Number of moves (less than 6 fullmoves is the opening, no matter what)
  • movement of the queens (if both queens have been moved, mark the game as midgame)

This answer may have been long, late and off-topic, but I hope it was helpful anyways.

1

I think chess programmers tend not to rely on the knowledge of strong chess players when designing their evaluation functions, but instead try out different elements, and then test them in games against other engines, and decide what to keep. Larry Kaufman talks a fair bit about his views on what a human's understanding is, but it sounds like both Rajlich and Dailey were very results oriented, and did not adopt Kaufman's ideas wholesale.

One article I found interesting was Zach Wegner comparing the evaluation functions of Rybka and Fruit. One of the areas where Rybka may have represented a step forward was in its incorporation of material imbalance tables based on specific combinations of pieces. Kaufman wrote an article on this as well.

http://www.top-5000.nl/ZW_Rybka_Fruit.pdf http://danheisman.home.comcast.net/~danheisman/Articles/evaluation_of_material_imbalance.htm

0

This link is the best starting point IMHO. I am using this as my starting point for my own chess program & finding it simple to understand and useful too.

https://chessprogramming.wikispaces.com/Simplified+evaluation+function

  • 2
    Could you please expand briefly on the contents of the link? – Pablo S. Ocal Jan 11 '15 at 10:50
0

In a nutshell, the standard approach to tuning a chess engine's parameters is to:

  1. Define the parameters
  2. Give the parameters nominal (starting) values
  3. Run the engine to see how it performs
  4. Tune the parameter values to try to improve its performance

Then repeat Steps 3 and 4 until you've reached your goal for performance.

The usual approach to doing this is to set up a laboratory where engines face off in engine tournaments. Multiple games are used in which the engine plays both colors. The main tournaments of interest involve running an engine with parameter value set A against the same engine with parameter value set B.

As you can probably guess, results from this approach are heavily dependent on:

  • The parameters chosen
  • How the parameters are specified
  • How the parameter values are varied throughout the testing
  • How the engines are run (limited ply-depth, limited time, sensitivity, etc)

This approach also consumes a lot of time.

A more recent (and innovative approach) was developed in 2010 by researchers using Genetic Algorithm techniques to a) specify the parameters, and b) tune the parameter values. The investigators first ran an engine with a starting, nominal set of parameter values against a set of grandmaster games to see if it could effectively choose the "best move". The "best move" was defined as the move the grandmaster made*. Wherever it failed to do so was recorded. Then, another parameter value set was tried, and relative performance vs the prior run determined.

Then, a programmatic approach to combining the parameter values was tried, using the Genetic Algorithm principle of survival of the "fittest". Here, "fittest" means the one that generates output that most closely matches the ideal. (It also happens to be a pun on the statistical technique of "least squares fit" regression, a technique used to judge the quality of the approximation.)

Only after engine parameters have been found that can mimic a GM reasonably well does the actual engine tournament phase begin. In this phase, different parameter value sets are once again pitted against each other, this time directly. Genetic Algorithm improvement techniques are applied to generate successively better generations of the engine.

In this research project, 36 parameters were used, including all of the material values of the pieces, and many of the more common strategic evaluation criteria, such as backward pawns, weak squares, bishop pair, and so on. However, the researchers added some new parameters, such as "king pressure", "mobility" values for each kind of piece, rook on a file adjacent to the king, rook on a semi-open file, rook attacking the king on the a-/b-/g-/h-file, separation between a passed pawn and the defending king, and more.

Unfortunately, the researchers don't elaborate on how they came up with this suite of parameters, and what alternate parameters they may have tested and rejected. It would be reasonable to assume that they began with a much larger set, and determined (through trial and error) which ones had the greatest effect on performance, and which ones were either insignificant or derivative, and so could be dropped.

If this sounds like it might be useful, you can find the research here.

*A caveat about a phase of the approach that the researchers used is in order. In his Introduction to Understanding Chess Move by Move, John Nunn chose "...hard fought games between strong grandmasters..." to illustrate his themes. He then adds:

Readers may be quite surprised to see the number of question marks that adorn the games in this book. Surely, you might think, with just thirty games to select, it should have been easy to find some sound games. However, I can assure you that it was not. ... it is possible to find fault with virtually any complex, hard-fought game... I have never felt that my play was anywhere near completely accurate, so I personally don't find these revelations distressing. However, some may find it hard to admit that chess as played by human beings is less accurate than previously thought.

The point that Dr Nunn raises suggests that the researchers' initial approach to setting the engine parameters by requiring them to imitate grandmaster moves may be flawed because human play is flawed. In fact, it's well established that engines already play better than humans.

Therefore, perhaps a better approach to setting the initial parameters would be to match a new engine against a superior existing engine.

0

There is a nice website at:

https://hxim.github.io/Stockfish-Evaluation-Guide/

It gives you an introduction on how the Stockfish functions work.

enter image description here

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.