Determining values for piece-square tables.

[Rein Halbersma]

I consider each game a series of matches (=the positions) between two teams of players, with a known result. The teams of players are the evaluation features.

With the Bradley-Terry model, you can calculate the ratings for each individual player, i.e. you directly get the evaluation weights for each feature.

It's a direct application of Remi Couloms result for go to chess. The method is insanely powerful.

Michael Buro did the same in Othello with his GLEM methode.

http://www.cs.ualberta.ca/~mburo/ps/glem.pdf
This is different from the generalized Bradley-Terry model I use. GLEM is supervised learning of game outcome with logistic regression. The Bradley Terry model is also used to learn weights of linear features, but not from the same kind of data. The Bradley-Terry models allows to learn from the preference of one position (or move) over others.

To be more concrete, in GLEM you learn from data such as "this is a won position, and I have a knight on e4, a pawn on e3, ... and my opponent has a knight on f6,...". This is in the temporal-difference spirit, where you try to match the quick heuristic value provided by the evaluation function with a more accurate value obtained by a deeper search or the actual outcome of a real game. With the Bradley-Terry model, you can learn from data such as "moving the knight to c3 is preferred to moving the knight to a3". Gian-Carlo uses the same idea in another different way, but it is still different from GLEM.

Rémi

Tnx for the explanation. So with GLEM you (logistically) fit position values as a linear function of features and with the BT-model you fit moves as basically the same function of features? Is that an accurate summary? In your experience, which method is the most accurate?

[Rémi Coulom]

Tnx for the explanation. So with GLEM you (logistically) fit position values as a linear function of features and with the BT-model you fit moves as basically the same function of features? Is that an accurate summary? In your experience, which method is the most accurate?

If you wish to understand better what I did, here is my paper:
http://remi.coulom.free.fr/Amsterdam2007/

Modern Go algorithms are completely different from chess algorithms. They have no evaluation function. So I cannot answer your question about which is more accurate, because they are not comparable with my experiments.

Maybe Gian-Carlo can answer your question better, as he used these algorithms for a chess evaluation function.

Rémi

[Gian-Carlo Pascutto]

Maybe Gian-Carlo can answer your question better, as he used these algorithms for a chess evaluation function.

Rémi

In the Go paper, you know a "match" result because "one move" is preferred over "all other moves". This "move" consists of a set of "features" for which you compute the "ratings".

In chess, I don't consider moves but positions for one player. So the features are now the evaluation features of one side.

Instead of a move winning over all others, it's always one position winning over over another position. All (white/black) positions in a game are considered to have won against all (black/white) positions in a game if (white/black) won the game.

GLEM looks quite different. The key there is discovering feature combinations, which the method above won't do.

[bob]

For a long time I've had piece-square tables in my engine that I had "temporarily" borrowed from other engines. This has prevented me from releasing my engine, because I want to release an engine that's entirely my own work (and definitely avoid releasing an engine that infringes on other people's copyrights).
I've begun a complete rewrite from the ground up, and have no intention of borrowing tables again, so my question is: how do people come up with these values in the first place?

I'm pretty mediocre at chess myself, and have very little book knowledge about chess, so any guesstimates I make will most likely be way off, and I would imagine that even a Grand Master's estimates would be off by a fair amount. So are there any suggestions on how I can go about determining those values? Or information I might be able to use in the process? Testing my values will be quite a task since I don't have a cluster like Bob's -- I'll just have to run tests while I'm at work or sleeping -- so, obviously, the closer I can get my initial estimates, the better.

I just make reasonable assumptions, and then test them by playing games and looking at what happens. If a knight ends up on the edge of the board, out of play, and that costs you a game, you probably don't have the values tuned very well yet...

Now that I've got my plain alpha-beta search (plus qsearch) up and going for my rewrite and after watching it play some games (and playing some against it myself), I'm starting to think just making reasonable assumptions (maybe even some not-so-reasonable assumptions) may give more improvement over material-only than I originally thought. I had assumed that the search alone would give it at least somewhat decent looking play, but it's just flinging its pieces around all over the place (as long as their not in immediate danger of being captured). But after seeing it do that, and thinking on it, I'm not sure why I expected it to do much else. On my last engine, I put borrowed piece-square tables in right from the get-go, so with it I never saw that problem.
I haven't fully tested my search yet though (except the qsearch, which I wrote before the main search), so it's entirely possible that a broken search is part of the problem.

Here is my take on this, I have used this quote pretty often in talks on computer chess:

The mere presence of a feature is more important than the actual value you add to the score. Just adding _something_ to the score when you have a passed pawn is a good thing. If you make the score proportional to the rank of the pawn, it is a better thing. But you get most of the "bang for the buck" from just having the term. Fine-tuning the values is something that can be done later.