ChessUSA.com TalkChess.com
Hosted by Your Move Chess & Games
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

A Go algorithm for chess programmers to try ?
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions Flat
View previous topic :: View next topic  
Author Message
Vincent Diepeveen



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

PostPost subject: Re: A Go algorithm for chess programmers to try ?    Posted: Sun Jun 03, 2007 2:05 pm Reply to topic Reply with quote

"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
View user's profile Send private message Send e-mail Visit poster's website MSN Messenger
Display posts from previous:   
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
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions

 
Jump to:  
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