Search-algorithm

[lara]

Hi,
first of all, I would like to thank you for excepting me to your board =)!

I'm writing on my diploma thesis and one topic deals with searching algorithm in computer games (especially chess).
So here's my question: I read a lot about minimax, alpha-beta, SSS*, Dual*, MTD(f), but which kind of search-algorithm do you use nowadays for your programs? Which one is best for you?
Which algorithm has made the best success?

Hopefully I'm at the right place!
Thanks a lot for your help!
Greetings, Lara

[zamar]

As far as I know, all high-level chess engines use Principal Variation Search (PVS) usually combined with aspiration window.

It's explained in here for example:
http://chessprogramming.wikispaces.com/ ... ion+Search

Make sure you fully understand NegaMax before reading it though.

[MattieShoes]

I think you're right, PVS/Negascout for most strong engines but I think there are some strong engines floating around that use mtd(f) too...

[Gerd Isenberg]

As mentioned, NegaScout aka PVS as alpha-beta enhancement is probably most common. Further important enhancements are related to various forward pruning techniques like Null Move Pruning, eventually Multi-Cut and Hyatt's Razoring. Quite common nowadays seems Late Move Reduction to reduce effective branching factor even more.

[Bill Rogers]

Unless the gentleman is accquainted with all these related terms he needs to get back to the basics as a starting point and that is Alpha-beta search. From there all the other improvements mentioned were discovered or made.
I don't know if Bruce Morlands chess page is still available but it can give one of the best descriptions of how most of it works in a step by step mode.
Bill

[Bill Rogers]

Sorry Gerd
I was first traind on Bruces page and without thinking I always refer to it and did not mean to dispute you recommendation. Both references are good.
Bill

[Gerd Isenberg]

Sorry Gerd
I was first traind on Bruces page and without thinking I always refer to it and did not mean to dispute you recommendation. Both references are good.
Bill

Thanks, Bill. We'll try to refer Bruce (backlinks) in cpw and to keep links up to date.

http://web.archive.org/web/200404032117 ... /index.htm

Gerd

[Sven]

Unless the gentleman is accquainted with all these related terms he needs to get back to the basics as a starting point and that is Alpha-beta search.

Just in case you meant the author of this thread when writing "the gentleman", you may have missed that "his" name is Lara which is probably a female name.

Sven

[Bill Rogers]

[lara]

No problem

Thanks a lot for your help and links!
I'll have a look at it, perhaps there will be some more questions