Author: Bert van den Akker
Date: 12:11:27 10/25/00
Go up one level in this thread
Here I give some theoreticaly numbers. Branche factor = (number of nodes visited for depth d ) / (number of nodes visited for depth d-1) With depth d I mean a search of d ply. Here are the formulas for perfect ordered search trees: v = number of moves from each node (number of moves possible fro a position in the search tree) d = search depth for d is odd minimum end nodes visited = v^((d+1)/2) + v^((d-1)/2) - 1 for d is even minimum end nodes visited = 2 * v^(d/2) - 1 These formulas come from Donald Knuth With v = 4 and d = 1 minimum end nodes visited = 4 With v = 4 and d = 2 minimum end nodes visited = 7 etc. The maximum end nodes visited = v^d The following calculations gives the minimum branching factor for brute force searching: Remember that in a search tree for chess of course v is not a constant factor so the numbers will be only an indication what you can expact: Hash tables and nullmove cutoff will have a lot of infuence on the branching factor because they cut large parts of the search tree. A program with hash tables and null moves can be up to 50 times faster!!!! v = 4 1 = 4 2 = 7 3 = 19 4 = 31 5 = 79 6 = 127 7 = 319 8 = 511 9 = 1279 10 = 2047 11 = 5119 12 = 8191 13 = 20479 14 = 32767 15 = 81919 16 = 131071 17 = 327679 18 = 524287 19 = 1310719 20 = 2097151 1 = 4 2 = 11 3 = 30 4 = 61 5 = 140 6 = 267 7 = 586 8 = 1097 9 = 2376 10 = 4423 11 = 9542 12 = 17733 13 = 38212 14 = 70979 15 = 152898 16 = 283969 17 = 611648 18 = 1135935 19 = 2446654 20 = 4543805 Branching factors 2 = 2.75 3 = 2.72727272727273 4 = 2.03333333333333 5 = 2.29508196721311 6 = 1.90714285714286 7 = 2.19475655430712 8 = 1.87201365187713 9 = 2.16590701914312 10 = 1.86153198653199 11 = 2.15735925842189 12 = 1.85841542653532 13 = 2.15485253482208 14 = 1.85750549565582 15 = 2.15413009481678 16 = 1.85724469908043 17 = 2.15392525240431 18 = 1.85717111802867 19 = 2.15386795899413 20 = 1.85715062285064 v = 36 1 = 36 2 = 71 3 = 1331 4 = 2591 5 = 47951 6 = 93311 7 = 1726271 8 = 3359231 9 = 62145791 10 = 120932351 11 = 2237248511 12 = 4353564671 13 = 80540946431 14 = 156728328191 15 = 2899474071551 16 = 5642219814911 17 = 104381066575871 18 = 203119913336831 19 = 3.75771839673139E+15 20 = 7.31231688012595E+15 1 = 36 2 = 107 3 = 1438 4 = 4029 5 = 51980 6 = 145291 7 = 1871562 8 = 5230793 9 = 67376584 10 = 188308935 11 = 2425557446 12 = 6779122117 13 = 87320068548 14 = 244048396739 15 = 3143522468290 16 = 8785742283201 17 = 113166808859072 18 = 316286722195903 19 = 4.07400511892729E+15 20 = 1.13863219990532E+16 Branching factors 2 = 2.97222222222222 3 = 13.4392523364486 4 = 2.80180806675939 5 = 12.9014643832216 6 = 2.79513274336283 7 = 12.8814723554797 8 = 2.79488096039565 9 = 12.8807589977275 10 = 2.79487210274715 11 = 12.8807347670465 12 = 2.79487180490385 13 = 12.8807339712951 14 = 2.79487179519157 15 = 12.8807339457832 16 = 2.79487179488182 17 = 12.8807339449799 18 = 2.79487179487211 19 = 12.8807339449549 20 = 2.7948717948718 BvdA
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.