Skip to main content
Share Your Experience: Take the 2024 Developer Survey
5 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 ...
Dennis Soemers's user avatar
  • 10.3k
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 ...
Keno's user avatar
  • 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 ...
Neil Slater's user avatar
  • 32.5k
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 ...
Jasper Citi's user avatar
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 ...
Sentry's user avatar
  • 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 ...
nbro's user avatar
  • 40.8k
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 ...
OmG's user avatar
  • 1,816
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 ...
maaartinus's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible