Branching factor

From HexWiki
Jump to: navigation, search

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.

See also

Computer Hex