6
votes
Which algorithms can we use on games with high branching factors (e.g. Connect6)?
Typically, Monte-Carlo Tree Search (MCTS) actually is the go-to "solution" for such problems with large branching factors. I can understand that "vanilla" MCTS may still have unsatisfactory ...
- 10.5k
4
votes
Accepted
Is the 'direction' considered, when determining the branching factor in bidirectional search?
If I am correct, the branching factor is the maximum number of successors of any node
You are correct, they should also be the immediate ones:
If 11 is the goal state and I start going backwards, is ...
- 575
3
votes
Accepted
Why was Go a harder game for an AI to master than Chess?
The branching factor is important, as it limits the effectiveness of search.
However, the branching factor in chess is already too high to effectively search without techniques that reduce the size ...
- 33.3k
3
votes
Accepted
How to deal with huge branching factors in real-time?
As you mentioned in the question, you cannot solve all problems with decision trees. Decision trees usually works well in a turn-based game with a good heuristic function, but in RTS games takes a ...
- 166
2
votes
Accepted
Why is the effective branching factor used for measuring performance of a heuristic function?
I also walked into that trap the first few times. The difference is the following:
$N$ is the number of expanded nodes
$b^*$ is the effective branching factor
$b^*$ depends on the depth $d$ of the ...
- 136
1
vote
Accepted
What is the space complexity of breadth-first search?
The space complexity of the breadth-first search algorithm is $O(b^d$) in the worst case, and it corresponds to the largest possible number of nodes that may be stored in the frontier at once, where ...
- 41.4k
1
vote
Why is the effective branching factor used for measuring performance of a heuristic function?
As you found $N$ is the number of nodes that are expanded. The cost of expansion of each node is equal to the number of children of that node. Hence, we use $b^*$ for each node. In other words, the ...
- 1,836
1
vote
Are leaf nodes included in the calculation of average branching factor for search trees?
I'd say that the leaves per se count, too, but only if they're real leaves, like e.g., checkmate positions in chess.
Such a node has really no children and no further calculation is needed. Unlike ...
- 563
Only top scored, non community-wiki answers of a minimum length are eligible