TalkChess.com

[Rémi Coulom]

Hi,

I have developed an efficient algorithm for move evaluation in my Go program that, I believe, might be interesting to you. It can be used to learn move ordering heuristics from a database of sample good moves. It can also provide a probability distribution over legal moves in a previously unseen position. Maybe chess programmers would like to try it, as it could be used to improve move ordering heuristics, or late-move reduction/pruning.

This algorithm improved my Go program by about 600 Elo points. I don't expect it would work that well for chess. But if I were to go back to programming chess, I would try it.

Here is the paper:
http://remi.coulom.free.fr/Amsterdam2007/

Title: Computing Elo Ratings of Move Patterns in the Game of Go

Abstract: Move patterns are an essential method to incorporate domain knowledge into Go-playing programs. This paper presents a new Bayesian technique for supervised learning of such patterns from game records, based on a generalization of Elo ratings. Each sample move in the training data is considered as a victory of a team of pattern features. Elo ratings of individual pattern features are computed from these victories, and can be used in previously unseen positions to compute a probability distribution over legal moves. In this approach, several pattern features may be combined, without an exponential cost in the number of features. Despite a very small number of training games (652), this algorithm outperforms most previous pattern-learning algorithms, both in terms of mean log-evidence (-2.69), and prediction rate (34.9%). A 19x19 Monte-Carlo program improved with these patterns reached the level of the strongest classical programs.

You may also be interested in this paper, because it explains in details the algorithm that I use in bayeselo:
http://remi.coulom.free.fr/Bayesian-Elo/
This algorithm was also described in a paper by David R. Hunter, cited on the page of bayeselo, but I believe that the description in my paper should be understandable by a much wider audience.

Also, it would be cool if someone would write a Monte-Carlo chess program. I do not have the motivation to do it, but I would be extremely curious to see the result. It would not be very strong, but would certainly have an interesting playing style.

Rémi