|
|
|
Object |
![[[An]] analysis of move ordering on the](http://digitool.Library.McGill.CA:80/exlibris/dtl/u3_1/dtle/www_r_eng/icon/ico_pdf.gif "[[An]] analysis of move ordering on the") |
|
[[An]] analysis of move ordering on the... - PDF Document (6 M) |
|
|
| Title |
An analysis of move ordering on the efficiency of alpha-beta search / |
| Creator |
Thé, Eric |
| Date |
1992 |
| Abstract |
Move ordering is important to alpha-beta tree search efficiency since a well-ordered minimax game tree precipitates more cutoffs than a randomly ordered tree. The use of move ordering heuristics is shown to be a valuable addition to the alpha-beta algorithm. Eight different move ordering heuristics are described and implemented on a skeleton chess program. The relative gains in search performance are observed for each individual heuristic as well as for combinations of heuristics. It is shown that when searching minimax game trees to a depth of 6 to 9 plies with well-chosen "killer" heuristics, reductions in search time and tree size exceed 80% on average. The effectiveness of move ordering heuristics is dependent on the depth of search and the scoring function used. With increased search depths, it is shown that the use of transposition tables to order moves becomes progressively more effective. Inversely, the use of Schaeffer's history heuristic is shown to be less effective with deeper searches. The use of a simple material-based chess scoring function is seen to have a strong influence on the performance of the capturing moves heuristic. It is observed that in this context, the ordering of captures improves search performance for materially unstable positions only. |
| Subject |
Computer Science. |
| Degree |
Master of Science |
| Department |
School of Computer Science. |
| Rights |
All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
| URL of this record |
http://digitool.Library.McGill.CA:80/R/-?func=dbin-jump-full&object_id=56753&silo_library=GEN01
|
| PID |
56753 |
| Number of Downloads |
104 |
| Related collections |
|
