Re: "Solvability" (long & pedantic)

Thread View: sci.logic

3 messages

[T] Back to Threads [V] Tree View [G] Group Articles

3 total messages Started by David Gudeman Tue, 29 Sep 1992 07:11

#413

Author: David Gudeman
Date: Tue, 29 Sep 1992 07:11

17 lines
1252 bytes

In article  <lcf2ctINN2te@coltexo.cs.utexas.edu> Donald A. Varvel writes:
]First of all, it is not necessary to visit every node in the game tree.
]Period.  Alpha-beta pruning yields the same result as min-max, provided
]each works with the same assumptions.  That is, an alpha-beta search
]of the entire game tree yields the same result as min-max, while cutting
]of many branches without analysis.  That's a minor point, though, since
]A-B doesn't promise an easy solution either.

It's been some time since I looked at this stuff, but as I recall,
search strategies that are still guaranteed to find the optimal
solution cannot be asymptotically better than breadth-first search
with the same cost function.  So alpha-beta pruning will do no better
than remove a polynomial number states from an exponential search
space.
-- 
					David Gudeman
gudeman@cs.arizona.edu

Re: "Solvability" (long & pedantic)

#414

Author: Hans Moravec
Date: Tue, 29 Sep 1992 09:29

9 lines
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

Re: "Solvability" (long & pedantic)

#429

Author: Robert Hyatt
Date: Wed, 30 Sep 1992 01:39

31 lines
2016 bytes

In article <22964@optima.cs.arizona.edu> gudeman@cs.arizona.edu (David Gudeman) writes:
>In article  <lcf2ctINN2te@coltexo.cs.utexas.edu> Donald A. Varvel writes:
>]First of all, it is not necessary to visit every node in the game tree.
>]Period.  Alpha-beta pruning yields the same result as min-max, provided
>]each works with the same assumptions.  That is, an alpha-beta search
>]of the entire game tree yields the same result as min-max, while cutting
>]of many branches without analysis.  That's a minor point, though, since
>]A-B doesn't promise an easy solution either.
>
>It's been some time since I looked at this stuff, but as I recall,
>search strategies that are still guaranteed to find the optimal
>solution cannot be asymptotically better than breadth-first search
>with the same cost function.  So alpha-beta pruning will do no better
>than remove a polynomial number states from an exponential search
>space.
>-- 
>					David Gudeman

Alpha-beta with good move ordering reduces the size of the minimax
tree to nearly the square root of the size of the minimax tree.  alpha
beta does not guarantee to find the shortest path to a win, but it will
find the best score.  If you make the path length part of the scoring
function, then even this complaint fades away.  breadth-first is not
appropriate to alpha-beta.....  it works with minimax DEPTH-FIRST game
trees only.  

Bob Hyatt

-- 
!Robert Hyatt                    Computer and Information Sciences   !
!hyatt@cis.uab.edu               University of Alabama at Birmingham !

Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads