Difference between revisions of "Branching factor"
(a tiny explanation on a reason wy hex is hard to compute efficiently) |
(Copy-editing) |
||
| (3 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
| − | In game theory the branching factor is the number of | + | In game theory, the '''branching factor''' is the number of possible moves available to a player at any given point in the game. 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 | + | The branching factor of a game can provide an estimate of how efficient a brute-force computer algorithm would be. The higher the branching factor, the weaker search-based algorithms will be due to the large number of positions that must be analyzed. In chess, the average branching factor is 40, while in Hex it is over 100, and in 19x19 [[Go]], it is over 300. This means that in chess, it is possible to look 5 or 6 moves ahead and then choose the best move to make, while in Hex, this is hardly conceivable. Therefore, other methods must be used to choose the right move. |
| + | |||
| + | To counter this problem, a number of techniques can be used. Methods such as computing the [[mustplay region]], computing [[captured cell]]s, and computing [[dominated cell|dominated moves]] can be used to reduce the number of moves that must be considered. This often leads to drastic reductions in the branching factor. | ||
== See also == | == See also == | ||
[[Computer Hex]] | [[Computer Hex]] | ||
| + | [[category:Computer Hex]] | ||
Latest revision as of 23:47, 25 January 2023
In game theory, the branching factor is the number of possible moves available to a player at any given point in the game. 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 can provide an estimate of how efficient a brute-force computer algorithm would be. The higher the branching factor, the weaker search-based algorithms will be due to the large number of positions that must be analyzed. In chess, the average branching factor is 40, while in Hex it is over 100, and in 19x19 Go, it is over 300. This means that in chess, it is possible to look 5 or 6 moves ahead and then choose the best move to make, while in Hex, this is hardly conceivable. Therefore, other methods must be used to choose the right move.
To counter this problem, a number of techniques can be used. Methods such as computing the mustplay region, computing captured cells, and computing dominated moves can be used to reduce the number of moves that must be considered. This often leads to drastic reductions in the branching factor.
