Eval()
I'm learning a new programming language, and what better idea is there than to experiment with programs for chess?
So I dived among other things into the world of the chess engines.
I always found it very troublesome that a chess engine didn't explain to me how it acquired its value of the best move. It is nice that you are +70 centipawns ahead, but how much is contributed by mobility and how much by king safety? I found a good open source engine (hattip to mr. Z) and I changed it so that is writes now down the analysis parameters in a database. The next step is two write a program that can show the positions from the database and the development of the parameters during the game.
The goal is to get a hunch how the tipping point of a game is reached. Which parameters are adding together and break the draw margin at the end? How does move 7 contribute to this?
What I noticed is that especially the evaluation function of chess engines is still in its infancy. Even the great ones suffer from this.
Maybe the evaluation function is not so important. That is the case when you have to choose between two or more good moves that both don't break the draw margin. If chess is a draw, then there comes a moment that deeper calculation doesn't make enough difference anymore. On the other hand, if one side continues to make the best move while the other side makes suboptimal moves, the draw margin might be broken in the end. Especially the pawn moves, which are irreversible might play a key role here. Better (deeper) calculation means in that case longer games, but the endresult might be decisive anyway.
There is a trade off between a good evaluation function that is slow and a bad evaluation function that is fast. Since fast means more ply and more ply outweights the quality of the evaluation function (as long as it is not totally brain dead).
No matter how fast the search algorithm is, there comes a moment you hit a barrier. With my hardware in combination with Houdini I can look ahead 22 plies within a reasonable time. But every ply deeper doubles the time.
To some degree, time and space are interchangable. Tempi manifest themselves as a geometrical pattern. If you can make use of an evaluation that implicit looks ahead a few more plies at the end of the search tree that might give a considerable edge against other engines.
But that is not my main goal. I just want to understand more of it. In the hope that I eventually find something usefull that I can transfer to OTB play.
The problem with evaluation is that you actually want to be able to estimate the value of two things that are seemingly different. In mainstream chess engines this is done by expressing everything in the same unit, in centipawns. You get a fixed bonus if you move your knight to e5 and a penalty if it is at a1. The values are determined in an empyric way. A lot of these values (like the knight bonuses for squares for instance) are static values regardless of the actual position on the board. A knight on c6 gets you a bonus, no matter if it is actually doing something there or totally out of play. The main problem is that actually apples and oranges are compared. How do you express kingsafety in terms of a passer on the sixth rank? Both are converted to centipawns but the course of exchange is arbitrary. These parameters are not the same in the endgame and the middlegame. To overcome this programmers of chess engines make use of tapered evaluation.
The question is, can we find a common base to convert these properties? What do all those positonal elements as knight outposts, king safety, moblity, rook on the 7th rank, open diagonals, centralization, gaining space etc. have in common? If you read my blog carefully, you will see that that is already appointed somewhere. That common noumer is piece activity.
In order to be active a piece must do something. There are three different things that a piece can do:
- A piece can attack another piece.
- A piece can take squares away from another piece, thus limiting its possibillities.
- A pawn can promote.
This way you can replace the 100 or so commonly used parameters by only 3 parameters. 100 parameters can never be coherent. Overtime programmers will have to make adjustments and exceptions. Creating an unstable monstrum along the way.
If these 3 parameters are maximized, you will find that the pieces will move towards a certain goal all by themselves, without additional programming. The following things will happen automaticly on the board solely by optimizing these 3 parameters:
- Optimize the own possibilities while minimizing the possibilities of the enemy.
- Weave a mating net
- Attack weak pawns
- Chase the king
- Put your knight on an outpost
- Put your rooks on active files
- Centralise your pieces
- Make positional sacrifices
- etc., etc.
But that is for later.
i dont know how deep you are in chessprogramming. Maybe you already know what i have to say. My chessprogram (1982 in Algol 60 on ~ 200 punchcards ) did use some "dirt" of the movegenerator as eval. #movepossible ~ activity
ReplyDelete#taking moves ~ activity
#controlled squares (+1 or above on a square) ~ activity/space
There are engines with many evaluation factors : http://users.telenet.be/chesslogik//cyclone.htm
A human dont need to evaluate a position, he need to be able to compare positions which are "a like". you calculate only a few moves, many aspects of the evaluation remains about the same.
usually you look at a sequence of moves and you judge the demage and the positive stuff this sequence does ( seems to do ).
I'm fairly new to chessprogramming.
ReplyDeleteWell, I wrote a chessprogram once based on genetic algorithms. I could teach it the chess rules within an evening. The illegal moves died out and the legal moves were passed on in the DNA to posterity. But I was more interested in genetic algorithms by then than in chess programming.
Cyclone is a good example of what I mean. It has 150 incoherent parameters which you must finetune by hand empirically.
From a practical point of view that is good enough of course. But I'm talking about a theoretical point of view here.
Not to frown upon mainstream chess programming but in an attempt to learn something that might be useful for OTB play. Since I'm not able to calculate 150 parameters OTB that is no option. But for positional purposes I might be able to count one: piece activity.
Of course I don't know beforehand if this is going to lead somewhere. But it's interesting enough to try my hand.
There had been these algorithms of Berliner and others. I thinks its only important to "calculate" the differences/changes each move; Moving Ng1 to f3 does mean 3 squares are not protected / controlled... by the knight anymore and 8 other squares become protected / controlled. The difference is ~ +5 for the knight and -2 for the pawn at f2... but pawnmove are not that important ( lets say 50%) so the activity gain is ~4
ReplyDeleteSomething of this type is still to manage at OTB.
Just came to my mind: You dont need to finetune by hand. You need a "large" set of "relevant" positions ( dead ones if you start evaluating only dead positions for example ). You calculate an evaluation of each by a good engine ( dont need to calculate that long ) and then the finetuning is "just" a multilinear regression ( + ...)
ReplyDelete