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 

The evaluation value and value returned by minimax search
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions Flat
View previous topic :: View next topic  
Author Message
Joona Kiiski



Joined: 18 Jan 2009
Posts: 545
PostPost subject: Re: The evaluation value and value returned by minimax searc    Posted: Sun Mar 11, 2012 12:20 pm Reply to topic Reply with quote
diep wrote:

If just 1% of the effort put in computerchess would be put in computer-go, you also easily beat of course any go player with todays hardware that also gets used for computerchess.


Just of course it requires a few talented game tree searchers to work in that field, and those guys want to get paid a salary.

What most people do not realize is that in go it's much easier to prune moves, so getting very big search depths there is pretty easy with todays hardware.

Now that said, realize how all search algorithms are total tuned and invented for computerchess.

Name me 1 search algorithm not yet invented/used before by some computerchess researcher that was invented in Go/Shogi or even checkers/draughts.

It all has been invented in chess as the most briliant guys worked on computerchess and not computer-go. That won't quickly change either.

Some stronger go players who also wrote a go program have estimated they need around a 30 ply search depth to get to the world top level tactics in go, not counting of course ladders.

However this is possible to achieve in go, even without reductions and no forward pruning and just nullmove you already get 15 ply.


Sorry, but your writing is complete crap and disinformation. You don't seem to understand much about the subject.

In chess, even a very simple program with material + PSQT plays quite strong chess. And even better, the strentgh of the program continues to increase steadily when increasing the thinking time / processing power.
Why? Because deep search is able to figure out many things by itself.

Some examples:
- When one have a strong king attack, in 14 plies one either delivers mate or wins material. So king safety evaluation is useful, but not essential.
- Passed pawns usually either get promoted or captured or one wins material based on the threat of the promotion. So passed pawn evaluation is helpful, but again it's not a necessity.
- In checkers one can quite complex heuristics to evaluate value of each piece, but in the end pieces promote to kings or not. So I assume that very deep search + very simple evaluation is able to produce a strong checkers program (practically in all variants)

NOTE:
- I didn't write that king safety or passed pawn evaluation or many other features are useless, but that in chess and checkers (I don't know about shogi, but I assume that it also holds there) when one has a substantial non-material advantage, deep search is in 99% of cases able to show a way how to capitalize that advantage into material advantage. And it's often the best way to play! Playing passively when having a non-material advantage, is usually a wrong way to go.
- It's the nature of these games that tactically complicated positions tend to resolve to simple ones in deep search and that's why even very basic evaluation function works okay (See Fruit 1.0).

But now let's talk about Go. Most people (including you) think that the high-branching factor is a problem. That's not the case. If you can give me a very good evaluation function, I'll write you a high-dan level engine in a month! But I believe that even a high-level evaluation function+minimax is not good enough to write a world champion level program,
because even that evaluation would be imperfect in many ways. The difference compared to most games in Go is that:
- When one side has a substantial advantage in one side of the board (let's say he's very thick in one side of the board), it often becomes disadvantageous to play on that region for a very long time (> 50 plies). If you misevaluate the thickness in root, you'll also misevaluate the thickness in all relevant lines in the whole search tree! And thickness is only one example of these kind of advantages. Aji or dead groups are also very long term advantages which can easily take >100 plies to capitalize into concrete territorial advantage.

So IMO the fundamental difference that is overlooked by most people is:
- Chess, Checkers, Shogi, Othello, ... are kind of "self-resolving" games. Misevaluating something is okay, because deep search is able to correct that (fx. showing that optically dangerous looking king attack is in reality worthless).
- Go is not a "self-resolving" game. If evaluation function is misevaluating the value of thickness or dead group in one side of the board, deep search is not able to correct you, because the optimal play does not happen on that region for a very long time.

Quote:

Name me 1 search algorithm not yet invented/used before by some computerchess researcher that was invented in Go/Shogi or even checkers/draughts.


"Invented" is a pretty strong word. But recently MCTS/UCB has become very popular, because of its applications in computer go

Regards,
Joona
_________________
Joona Kiiski
Back to top
View user's profile Send private message
Display posts from previous:   
Subject Author Date/Time
The evaluation value and value returned by minimax search Ma Chao Fri Mar 09, 2012 11:51 am
      Re: The evaluation value and value returned by minimax searc Joona Kiiski Fri Mar 09, 2012 12:06 pm
            Re: The evaluation value and value returned by minimax searc Pio Korinth Fri Mar 09, 2012 9:51 pm
            Re: The evaluation value and value returned by minimax searc Vincent Diepeveen Sun Mar 11, 2012 5:34 am
            Re: The evaluation value and value returned by minimax searc Vincent Diepeveen Sun Mar 11, 2012 5:58 am
                  Re: The evaluation value and value returned by minimax searc Joona Kiiski Sun Mar 11, 2012 12:20 pm
                        Re: The evaluation value and value returned by minimax searc Vincent Diepeveen Sun Mar 11, 2012 2:41 pm
                              Re: The evaluation value and value returned by minimax searc Joona Kiiski Sun Mar 11, 2012 3:44 pm
                                    Re: The evaluation value and value returned by minimax searc Vincent Diepeveen Sun Mar 11, 2012 3:47 pm
                                          Re: The evaluation value and value returned by minimax searc Joona Kiiski Sun Mar 11, 2012 3:51 pm
                                                Re: The evaluation value and value returned by minimax searc Vincent Diepeveen Sun Mar 11, 2012 3:55 pm
                                                      Re: The evaluation value and value returned by minimax searc Marco Costalba Sun Mar 11, 2012 4:04 pm
                                                            Re: The evaluation value and value returned by minimax searc Vincent Diepeveen Sun Mar 11, 2012 4:10 pm
                                                                  Re: The evaluation value and value returned by minimax searc Joona Kiiski Sun Mar 11, 2012 5:03 pm
                        Re: The evaluation value and value returned by minimax searc Vincent Diepeveen Sun Mar 11, 2012 2:43 pm
                        Re: The evaluation value and value returned by minimax searc Uri Blass Sun Mar 11, 2012 3:07 pm
                              Re: The evaluation value and value returned by minimax searc Vincent Diepeveen Sun Mar 11, 2012 3:23 pm
                                    Re: The evaluation value and value returned by minimax searc Joona Kiiski Sun Mar 11, 2012 3:47 pm
                                          Re: The evaluation value and value returned by minimax searc Vincent Diepeveen Sun Mar 11, 2012 3:50 pm
                                                Re: The evaluation value and value returned by minimax searc Joona Kiiski Sun Mar 11, 2012 3:52 pm
                              Re: The evaluation value and value returned by minimax searc Joona Kiiski Sun Mar 11, 2012 3:42 pm
      Re: The evaluation value and value returned by minimax searc Han Chengye Sat Mar 10, 2012 2:22 am
            Re: The evaluation value and value returned by minimax searc Marco Costalba Sat Mar 10, 2012 12:48 pm
      Re: The evaluation value and value returned by minimax searc Ralph Stoesser Sat Mar 10, 2012 11:12 pm
            Re: The evaluation value and value returned by minimax searc Vincent Diepeveen Sun Mar 11, 2012 6:27 am
      Re: The evaluation value and value returned by minimax searc Vincent Diepeveen Sun Mar 11, 2012 5:09 am
      Re: The evaluation value and value returned by minimax searc Vincent Diepeveen Sun Mar 11, 2012 5:27 am
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