A Go algorithm for chess programmers to try ?

[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

[RVisitor]

Vasik Rajlich has already written a Monte Carlo chess program using Rybka - he calls it the Rybka Randomizer. I have used it a lot but have not found it useful for generating analysis. In order to play many hundred games you have to set the time per move to such a low value that the moves and games it generates are meaningless.

[Daniel Mehrmann]

Hi Remi !

I'm working on a Go program as well. Thanks for share your ideas.

But i don't like to start with ELO in Go. There was no ELO, there is no ELO, there will be no ELO.

I think your 30 ky ranks, 1-9 amateur dan ranks, 1-9 pro-dan ranks should be enought to evaluate a playstrenght for a algorithm as well.

Your main problem is you need to evaluate thouands , millions, of games to create a elo based rating system. Also analyzing of dan player games wouldn't help any program today. They are currently just to stupid

But i'm working on it

BTW: Currently i'm improving my ky level: i reached 7 today

Best,
Daniel

[diep]

"I don't expect it would work that well for chess."

I agree with the above.

Over my dead body it can beat todays selective searchers.

"But if I were to go back to programming chess, I would try it."

This is total bullshit of course.
You are someone who likes to win bigtime.
I saw it in your eyes several times at world championships.
No freaking way to deny it.

You are NOT going to implement in Le Fous Fous (the crazy bishop) something that is in advance going to lose for you.

You hate losing more than any other game tree addicted nerd in France.
Don't deny the obvious please.

It just works for your go program, because your go program is THAT bad compared to objective human standards, and you didn't figure out a normal way to search in go yet.

As soon as go programs can play tactical without mistakes, then all this monte carlo nonsense (nonsense from game tree playing programs viewpoint seen) dies slowly as it keeps losing more and more against tactical more bugfree playing programs.

Currently search in go gets dominated by hard forward pruning in root, and using internal zobrist keys for repetition of 32 bits integers.

What do i need to say more to prove how infantile search is currently in go programs with respect to "not having a worst case by means of superdubious pruning".

In the land of the blind, one-eye is king (dutch saying).

For go it is possible to prune real accurately. Just use this search form:
in each given position divide all moves in 7 groups.

Group 1 is the seemingly best moves you want to try.
Group 2 is a bit less great.

and so on.

Now instead of the normal reduction of 1 on each position after making a move as we have in brute force search, you reduce simply the group number where the move belongs to from your search depth left.

In Qsearch you look first 4 ply to all moves that shut in groups that have 2 liberties or less. You extend infinitely all lines that close groups which have 1 liberty.

Now just make some go knowledge classifying those 7 groups and kick the hell out of your montecarlo method with it.

Best regards,
Vincent

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

[Rémi Coulom]

You are NOT going to implement in Le Fous Fous (the crazy bishop) something that is in advance going to lose for you.

I really believe it could work. Not Monte-Carlo chess, of course. But I was under the impression that using domain knowledge to prune or reduce late moves is a good idea. I am not following computer chess that much, but I believe some do it already. I think the algorithm in my paper would be a very good tool to design such pruning or reduction heuristics.

Rémi

[diep]

You are NOT going to implement in Le Fous Fous (the crazy bishop) something that is in advance going to lose for you.

I really believe it could work. Not Monte-Carlo chess, of course. But I was under the impression that using domain knowledge to prune or reduce late moves is a good idea. I am not following computer chess that much, but I believe some do it already. I think the algorithm in my paper would be a very good tool to design such pruning or reduction heuristics.

Rémi

Abstract:

"....A 19×19 Monte-Carlo program improved with these patterns reached the level of the strongest classical programs."

You seem total ignorant that your paper reports nothing new wasn't it that you combined it with monte carlo method. Remove the word "monte carlo" out of your paper and you basically claim something that already gets used for 30 years in computer chess.

Apart from that i'll have to dissappoint you that if in diep i just see tactics deeper, that it doesn't play better at all. Experiments showed a score reduction over 1000 games against other programs at slow time controls (40 in 2 hours), an experiment that has eaten quite some system time you can say, a score reduction of 20-25% against commercial programs.

that is about 140-200 of reduction in elostrength when just seeing tactics deeper last few plies.

In Go that still works because programs are tactical that pathetic bad as of today that all their mistakes still can be seen as tactical mistakes.

[Alessandro Scotti]

Hi Remi,
thanks a lot for sharing this paper, new things to try are always welcome!

[Dann Corbit]

Late move reductions are used by all of the strongest program.
If a mathematical approach can provide better candidates for reduction, then it may be better for some programs.

I have not read the paper yet, but I guess it will be interesting.

[Dan Andersson]

I'm having a blast reading papers covering UCT-MC and related papers on variations to Bandit search and MCMC (Markov Chain Monte Carlo).

MvH Dan Andersson

[Rémi Coulom]

I'm having a blast reading papers covering UCT-MC and related papers on variations to Bandit search and MCMC (Markov Chain Monte Carlo).

MvH Dan Andersson

This has become a hot topic in computer games. Out of 23 papers in the Amsterdam workshop, 7 deal with MC search. I predict it will be the dominating approach to the game of Go for many years, if not forever. The idea is very generic and already starts to have applications in other domains as well.

Rémi