| View previous topic :: View next topic |
| Author |
Message |
Vincent Diepeveen
Joined: 09 Mar 2006 Posts: 1738 Location: The Netherlands
|
Post subject: Re: A Go algorithm for chess programmers to try ? Posted: Sun Jun 03, 2007 2:05 pm |
|
|
"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 |
|
|
| Back to top |
|
 |
|
| Subject |
Author |
Date/Time |
A Go algorithm for chess programmers to try ? |
Rémi Coulom |
Sat Jun 02, 2007 8:32 pm |
Re: A Go algorithm for chess programmers to try ? |
RVisitor |
Sat Jun 02, 2007 8:44 pm |
Re: A Go algorithm for chess programmers to try ? |
Daniel Mehrmann |
Sat Jun 02, 2007 8:57 pm |
Re: A Go algorithm for chess programmers to try ? |
Vincent Diepeveen |
Sun Jun 03, 2007 2:05 pm |
Re: A Go algorithm for chess programmers to try ? |
Rémi Coulom |
Sun Jun 03, 2007 2:18 pm |
Re: A Go algorithm for chess programmers to try ? |
Vincent Diepeveen |
Sun Jun 03, 2007 2:48 pm |
Re: A Go algorithm for chess programmers to try ? |
Dann Corbit |
Tue Jun 05, 2007 6:58 pm |
Re: A Go algorithm for chess programmers to try ? |
Dan Andersson |
Wed Jun 06, 2007 7:21 am |
Re: A Go algorithm for chess programmers to try ? |
Rémi Coulom |
Wed Jun 06, 2007 7:37 am |
Re: A Go algorithm for chess programmers to try ? |
Dan Andersson |
Wed Jun 06, 2007 7:58 am |
Re: A Go algorithm for chess programmers to try ? |
Alessandro Scotti |
Tue Jun 05, 2007 5:54 pm |
Re: A Go algorithm for chess programmers to try ? |
Gerd Isenberg |
Wed Jun 06, 2007 1:50 pm |
Re: A Go algorithm for chess programmers to try ? |
Rémi Coulom |
Wed Jun 06, 2007 2:40 pm |
Re: A Go algorithm for chess programmers to try ? |
Gerd Isenberg |
Wed Jun 06, 2007 6:05 pm |
Re: A Go algorithm for chess programmers to try ? |
Rémi Coulom |
Wed Jun 06, 2007 6:21 pm |
|
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
|
|