Difference between revisions of "Branching factor"
m (typo) |
(Fixed typos and added a paragraph.) |
||
| Line 1: | Line 1: | ||
| − | In game theory the branching factor is the number of | + | In game theory ,the branching factor is the number of moves available for a player. In [[Hex]], the branching factor decreases by one with each move. At the beginning of a 13x13 game the branching factor is 169. |
| − | The branching factor of game gives an estimate of how efficient a brute force computer would be | + | The branching factor of a game gives an estimate of how efficient a brute force computer would be. The higher the branching factor is, the weaker will the Artificial Intelligence be. This is due to the number of positions to be analysed to perform in-depth search. In chess, the average branching factor is 40. It is more than 100 in Hex and more than 300 in 19x19 [[Go]]. It means that it is possible in chess to look 5 or 6 moves ahead and then choose the best to begin with, whereas it is hardly conceivable in Hex. Hence other ways have to be found to choose the right move. |
| + | |||
| + | The techniques of computing the [[mustplay region]], and of computing [[captured cell]]s and [[dominated cell|dominated move]]s (both of which can be excluded from consideration), can all be used to reduce the branching factor, in many cases drastically. | ||
== See also == | == See also == | ||
Revision as of 00:48, 12 September 2021
In game theory ,the branching factor is the number of moves available for a player. In Hex, the branching factor decreases by one with each move. At the beginning of a 13x13 game the branching factor is 169.
The branching factor of a game gives an estimate of how efficient a brute force computer would be. The higher the branching factor is, the weaker will the Artificial Intelligence be. This is due to the number of positions to be analysed to perform in-depth search. In chess, the average branching factor is 40. It is more than 100 in Hex and more than 300 in 19x19 Go. It means that it is possible in chess to look 5 or 6 moves ahead and then choose the best to begin with, whereas it is hardly conceivable in Hex. Hence other ways have to be found to choose the right move.
The techniques of computing the mustplay region, and of computing captured cells and dominated moves (both of which can be excluded from consideration), can all be used to reduce the branching factor, in many cases drastically.
