TalkChess.com
Hosted by Your Move Chess & Games

 A Go algorithm for chess programmers to try ? Goto page 1, 2  Next
Author Message
Rémi Coulom

Joined: 24 Apr 2006
Posts: 350

 Posted: Sat Jun 02, 2007 8:32 pm    Post subject: A Go algorithm for chess programmers to try ? 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
Guest

 Posted: Sat Jun 02, 2007 8:44 pm    Post subject: Re: A Go algorithm for chess programmers to try ? 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

Joined: 08 Mar 2006
Posts: 762
Location: Germany

 Posted: Sat Jun 02, 2007 8:57 pm    Post subject: Re: A Go algorithm for chess programmers to try ? 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
Vincent Diepeveen

Joined: 09 Mar 2006
Posts: 1738
Location: The Netherlands

Posted: Sun Jun 03, 2007 2:05 pm    Post subject: Re: A Go algorithm for chess programmers to try ?

"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

 Rémi Coulom wrote: 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

Joined: 24 Apr 2006
Posts: 350

Posted: Sun Jun 03, 2007 2:18 pm    Post subject: Re: A Go algorithm for chess programmers to try ?

 diep wrote: 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
Vincent Diepeveen

Joined: 09 Mar 2006
Posts: 1738
Location: The Netherlands

Posted: Sun Jun 03, 2007 2:48 pm    Post subject: Re: A Go algorithm for chess programmers to try ?

Rémi Coulom wrote:
 diep wrote: 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
Guest

 Posted: Tue Jun 05, 2007 5:54 pm    Post subject: Re: A Go algorithm for chess programmers to try ? Hi Remi, thanks a lot for sharing this paper, new things to try are always welcome!
Dann Corbit

Joined: 08 Mar 2006
Posts: 5125
Location: Redmond, WA USA

 Posted: Tue Jun 05, 2007 6:58 pm    Post subject: Re: A Go algorithm for chess programmers to try ? 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

Joined: 08 Mar 2006
Posts: 440

 Posted: Wed Jun 06, 2007 7:21 am    Post subject: Re: A Go algorithm for chess programmers to try ? 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

Joined: 24 Apr 2006
Posts: 350

Posted: Wed Jun 06, 2007 7:37 am    Post subject: Re: A Go algorithm for chess programmers to try ?

 Dan Andersson wrote: 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
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 All times are GMTGoto page 1, 2  Next Page 1 of 2

 Jump to: Select a forum Computer Chess Club Forums----------------Computer Chess Club: General TopicsComputer Chess Club: Tournaments and MatchesComputer Chess Club: Programming and Technical DiscussionsComputer Chess Club: Engine Origins Other Forums----------------Chess Thinkers ForumForum Help and Suggestions
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

Powered by phpBB © 2001, 2005 phpBB Group
Enhanced with Moby Threads