Article View: sci.logic
Article #414Re: "Solvability" (long & pedantic)
From: Hans Moravec
Date: Tue, 29 Sep 1992 09:29
Date: Tue, 29 Sep 1992 09:29
9 lines
986 bytes
986 bytes
Alpha-beta pruning with a good branch ordering function can evaluate a min-max tree of N nodes, while visiting only Sqrt[N] of them. My reference is a pamphlet written by Donald Knuth in the 1970s titled "Alpha Beta Prunes", but this is a widely known result. -- Hans Moravec
Technical Details
Message-ID:
<HPM.92Sep29042959@sheep.frc.ri.cmu.edu>Path:
arc1-ca.pugleaf.net!sparky!uunet!ogicse!das-news.harvard.edu!cantaloupe.srv.cs.cmu.edu!crabapple.srv.cs.cmu.edu!netnews.srv.cs.cmu.edu!hpmReferences:
<22964@optima.cs.arizona.edu>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!sparky!uunet!ogicse!das-news.harvard.edu!cantaloupe.srv.cs.cmu.edu!crabapple.srv.cs.cmu.edu!netnews.srv.cs.cmu.edu!hpm From: hpm@frc.ri.cmu.edu (Hans Moravec) Newsgroups: sci.logic,sci.math,rec.games.chess Subject: Re: "Solvability" (long & pedantic) Message-ID: <HPM.92Sep29042959@sheep.frc.ri.cmu.edu> Date: 29 Sep 92 09:29:59 GMT Article-I.D.: sheep.HPM.92Sep29042959 References: <22964@optima.cs.arizona.edu> Sender: news@cs.cmu.edu (Usenet News System) Reply-To: moravec@cs.cmu.edu Followup-To: sci.math Organization: Field Robotics Center, CMU Lines: 9 In-Reply-To: gudeman@cs.arizona.edu's message of 29 Sep 92 07:11:43 GMT Nntp-Posting-Host: sheep.frc.ri.cmu.edu