Difference between revisions of "Branching factor"

From HexWiki
Jump to: navigation, search
m (category -> computer hex)
(Copy-editing)
 
(2 intermediate revisions by the same user not shown)
Line 1: Line 1:
In game theory the branching factor is the number of move avaible for a player. In [[Hex]] the branching factor decreases by one each move. At the beginning of a 13x13 game the branching factor is 169.
+
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 gives an estimate of how efficient a brutal force computer would be, the higher the branching factor is the weaker will be the Artificial Intelligence. 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 find to choose the right move.
+
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 ==

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.

See also

Computer Hex