+- Ludii Forum (https://ludii.games/forums)
+-- Forum: Questions (https://ludii.games/forums/forumdisplay.php?fid=13)
+--- Forum: About Ludii (https://ludii.games/forums/forumdisplay.php?fid=14)
+--- Thread: Estimation of branching factor (/showthread.php?tid=1416)
Estimation of branching factor - Michael - 12-27-2022
Someone asked Ludii to calculate the BF of Lielow, and got this:
Quote:Avg. number of decisions per trial = 25.99411723013679.It says the average BF is about 123. Someone else pointed out that the game cannot possibly offer more than 8 different decisions (one per direction to jump in) per stack, of which there are 8 per player, so that puts a cap on the BF at 64. What's happening when Ludii is comming up with 123? Are nondecisions somehow involved? My best guess is that every level in a stack is counted as a possibility when a piece is added to the bottom of a stack as a consequence. But that's a wild guess.
Avg. branching factor per trial = 123.40724495764664.
Estimated game-tree complexity ~= 10^55.
Statistics collected over 28218 random trials.
RE: Estimation of branching factor - dale walton - 01-01-2023
A related question:
Game complexity seems to be generated as the branching factor raised to the power of the number of moves.
A more accurate approach might be to estimate the game complexity directly and then derive the average branching per move and/or turn from it:
This could be done by counting the choices at each "decision" and subtracting one (forced moves) to give the number of decisions, then taking the binary log (say to 8 places by table) and keeping a running total of the log values. At the end divide the tally by the number of trials completed to give an average game complexity base 2 exponent and multiply this by the factor needed to convert it to the base 10 exponent.
Also keep a similar running total for the number of moves and turns for each game in the trials.
Then divide to yield average branching.
Does this make sense?
Another count of interest is how many decision owner turnovers per game: ie count of when the owner of a decision with more than one choice is followed by a decision of more than one choice by a different player (ignoring all forced moves.) Compared to the average turn count, this gives an indication of how many forced turns there are per game.