Branching factor - Revision history

Selinger: Copy-editing

2023-01-25T23:47:23Z

Copy-editing

Selinger: Fixed typos and added a paragraph.

2021-09-12T00:48:22Z

Fixed typos and added a paragraph.

Selinger: typo

2021-09-11T21:18:24Z

typo

Halladba: category -> computer hex

2007-12-12T11:50:54Z

category -> computer hex

Halladba: a tiny explanation on a reason wy hex is hard to compute efficiently

2007-11-19T11:12:24Z

a tiny explanation on a reason wy hex is hard to compute efficiently

New page

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.

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.

== See also ==

[[Computer Hex]]

@@ Line 1: / Line 1: @@
-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.
+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 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 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.
-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.
+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 ==

@@ 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 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 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 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.
 == See also ==

← Older revision		Revision as of 11:50, 12 December 2007
Line 6:		Line 6:

	[[Computer Hex]]		[[Computer Hex]]
		+	[[category:Computer Hex]]