Reply
 
LinkBack Thread Tools Display Modes
  #1   Report Post  
Old March 26th 04, 06:57 AM
sb
 
Posts: n/a
Default alpha - beta pruning still rules?

I've read somewhere that Fritz uses some more advanced algorithms that
what was used up until recently. Does it still use a/b-pruning. Are
there chess engines that "prove theorems" instead of just searching?
How are they doing (if they exist)?
  #2   Report Post  
Old March 26th 04, 11:47 AM
Mikko Nummelin
 
Posts: n/a
Default alpha - beta pruning still rules?

On Fri, 25 Mar 2004, sb wrote:

I've read somewhere that Fritz uses some more advanced algorithms that
what was used up until recently. Does it still use a/b-pruning. Are
there chess engines that "prove theorems" instead of just searching?
How are they doing (if they exist)?


All current chess algorithms are different variations of alpha-beta.
Common refinement to alpha-beta is use of either null-sized or fixed
sized aspiration windows, i.e. occasionally setting alpha-beta window
narrower (even to null-width!) than it would be theoretically justified
and seeing if that somehow happens to bring a satisfactory result. If it
fails low or high when that is not acceptable (the returned value is
outside the window), then a broader or full-width alpha-beta re-search is
made to grab the correct result. Some of these methods have different
names like "PVS" and "NegaScout".


Mikko Nummelin
  #3   Report Post  
Old March 26th 04, 02:23 PM
David Richerby
 
Posts: n/a
Default alpha - beta pruning still rules?

sb wrote:
I've read somewhere that Fritz uses some more advanced algorithms that
what was used up until recently. Does it still use a/b-pruning. Are
there chess engines that "prove theorems" instead of just searching?
How are they doing (if they exist)?


You're probably thinking of `proof number search'. I've been meaning to
read up about that for a while; a useful reference is L. Victor Allis's
Ph.D. thesis, `Searching for Solutions in Games and Artificial
Intelligence' which is available on-line at

http://www.cs.vu.nl/~victor/thesis.html

Another handy reference on alpha-beta variants is Aske Plaat's Ph.D.
thesis, `Research Search and Re-Search' at

http://www.cs.ualberta.ca/~jonathan/Grad/plaat.phd.ps


Dave.

--
David Richerby Beefy Atom Bomb (TM): it's like a
www.chiark.greenend.org.uk/~davidr/ weapon of mass destruction that's made
from a cow!
  #4   Report Post  
Old March 26th 04, 05:32 PM
Noah Roberts
 
Posts: n/a
Default alpha - beta pruning still rules?

sb wrote:
I've read somewhere that Fritz uses some more advanced algorithms that
what was used up until recently. Does it still use a/b-pruning. Are
there chess engines that "prove theorems" instead of just searching?
How are they doing (if they exist)?


In _Problem_solving_and_artificial_intelligence_ Lauriere talks about a
program called "ROBIN" that was able to formulate plans. It would
perceive a goal and then work back from that goal to find out what had
to be done to achieve it safely. This was done in the 70s and I can't
find any other reference to it.

Also check out work on Chunking theory. Here is the reference page to a
paper I recently wrote for a college english course (many of these are
available at citeseer):


[1] Lauričre, J. Problem Solving and Artificial Intelligence. Howlett,
J. translator. Hertfordshire, UK: Prentice Hall International; 1990.
501 p. Translation of 1987 edition.
[2] Finkelstein, L. and Markovitch, S. Learning to play chess
selectively by acquiring move patters. Computer Science Department.
Technion, Haifa, Israel. 22 p.
[3] George, M. and Schaeffer, J. Chunking for experience. Department
of Computing Science, University of Alberta. Edmonton, Alberta. 13 p.
[4] Gobet, F and Simon, H. A. Expert chess memory: Revisiting the
chunking hypothesis. Memory 1998; 6 (3): 225-255.
[5] Simon, H. A. and Schaeffer, J. The game of chess. Carnegie-Mellon
University and University of Alberta. 17 p. Available at
http://citeseer.ist.psu.edu/simon92game.html
[6] DeCoste, D. The future of chess-playing technologies and the
significance of Kasparov versus Deep Blue. Proceedings of the AAAI-97
Workshop on Deep Blue vs Kasparov: The Significance for Artificial
Intelligence , July 1997.
[7] Saariluoma, P and Laine, T. What do computer models of cognition
explain: A reply to Gobet. Scandinavian Journal of Psychology 2001; 42.
147-148
[8] Lassiter, G. D. The relative contributions of recognition and
search-evaluation processes to high-level chess performance: Comments on
Gobet and Simon. Psychological Science 2000 March; 11 (2). 172-173
[9] Gobet, F. and Simon, H. A. Reply to Lassiter. Psychological
Science 2000 March; 11 (2). 174
[10] Roberts, N. JunFa [Computer program]. Version 0.0.2. Yelm, WA:
Personal project program; 2003. Source file download
http://sourceforge.net/projects/xiangqi-engine/ . System Requirements:
Any PC and OS that can compile with the Gnu Compiler Collection.

In practice 99% of the chess engines that exist use some form of
alpha-beta. But there is research into other ways of "solving" chess
that involve both brute force algorithms and more 'abstract' (for lack
of a better word) AI. Brute force methods have, so far, shown
themselves to be more effective. That is why people who build
commercial engines or who want to beat other computers and/or GMs use
brute force. People attempting to study why humans are good at chess
and computers require so much more power to compete sometimes research
other ways to do it.

--
"I'm a war president. I make decisions here in the Oval Office
in foreign policy matters with war on my mind." - Bush

Reply
Thread Tools
Display Modes

Posting Rules

Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On


Similar Threads
Thread Thread Starter Forum Replies Last Post
going deep... Tommy rec.games.chess.computer (Computer Chess) 14 December 17th 03 08:01 AM
adjusting the window based on ttable Noah Roberts rec.games.chess.computer (Computer Chess) 11 November 5th 03 07:18 AM
Fail Soft Alpha Beta & Transpositions Orhan Öztürk rec.games.chess.computer (Computer Chess) 4 September 10th 03 04:58 PM
(Fail soft) alpha beta Delphi rec.games.chess.computer (Computer Chess) 7 September 7th 03 03:00 PM


All times are GMT +1. The time now is 03:46 AM.

Powered by vBulletin® Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
Copyright ©2004-2019 ChessBanter.
The comments are property of their posters.
 

About Us

"It's about Chess"

 

Copyright © 2017