[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

computer-go: Alpha-Beta Search

To: computer-go@xxxxxxxxxxxxxxxxx
Subject: computer-go: Alpha-Beta Search
From: Patricia Hughes and David Elsdon <babel17@xxxxxxxxxx>
Date: Mon, 15 Nov 1999 23:01:19 +0100
References: <3.0.32.19991115114537.00cd63d0@xxxxxxxxxxxxxxxxx>
Reply-to: computer-go@xxxxxxxxxxxxxxxxx
Sender: owner-computer-go@xxxxxxxxxxxxxxxxx

The Knuth Paper to read is:

Knuth and Moore "An analysis of alpha-beta pruning" Artificial
Intelligence 6(4), 293-326, 1975.

Note that you will only get the reduction of the branch factor to the
square root of the branch factor if the search is perfectly ordered by
the goodness (according to the evaluation function) of the moves. So
provided your ordering is reasonably good most of the time you will get
fairly close to optimal pruning.

Cheers

David Elsdon

Follow-Ups:
- Re: computer-go: Alpha-Beta Search
  - From: Daniel Bump

References:
- Re: computer-go: extracting date to beat 9d from chess and draughts scene
  - From: Vincent Diepeveen

Prev by Date: Re: computer-go: Correct moves?
Next by Date: Re: computer-go: Correct moves?
Previous by thread: computer-go: Re: null move
Next by thread: Re: computer-go: Alpha-Beta Search
Index(es):
- Date
- Thread