how ply, sims, and branch impact the time to solution?

[danlangford]

so i have been running BMAI on the ButtonWeavers site. I am having it run on an old spare laptop using these settings for each run:

ply 3
max_sims 100
min_sims 5
maxbranch 400

i am going into fight mode and then ending with getaction.

if those above settings produced these results:

Time: 385sec
Sims: 7381825
Sims/Sec: 19,173.58
Mvs/Sms | 14.0/28.0 | 10.5/19.4 | 8.1/12.5 = 8152398

how much longer do you think it will take if i run the same command but with the following settings:

ply 3
max_sims 500
min_sims 10
maxbranch 5000

which are the default settings for sims and maxbranch. im wondering how in fact the sim and branching impact the overall runtime. and maybe that depends more on the size and attack options of the dice in play. any thoughts?
i could run some experiments. create a base line. fiddle with just sims or just branch and log my results. i may do that

[danlangford]

ok i understand that the time to solution depends greatly on hardware, current cpu load, and many other factors. so the questions should really be about number of simulations and moves per simulation i think. for some data gathering i am going to use these commands to start

game 3
fight
player 0 4 28
(4,4):5
8:5
20:1
(10,10):8
player 1 5 40
4:1
6:6
6:5
12:8
4:4
ply 1
max_sims 100
min_sims 5
maxbranch 400
getaction
quit

ply 1

stats 1/5-100/400/0.50 Time: 0.000000 s Sim: 392  Sims/Sec: 0.000000  Mvs/Sms | 14.0/28.0 = 392

ply 2

stats 2/5-100/400/0.50 Time: 1.000000 s Sim: 76740  Sims/Sec: 76740.000000  Mvs/Sms | 14.0/28.0 | 10.9/18.7 = 80231

ply 3

stats 3/5-100/400/0.50 Time: 41.000000 s Sim: 7312914  Sims/Sec: 178363.756098  Mvs/Sms | 14.0/28.0 | 11.1/18.5 | 7.9/13.0 = 8254492

ply 4

stats 4/5-100/400/0.50 Time: 1275.000000 s Sim: 340045724  Sims/Sec: 266702.528627  Mvs/Sms | 14.0/28.0 | 11.0/18.4 | 8.0/12.8 | 5.7/9.0 = 415727936

ply 5

stats 5/5-100/400/0.50 Time: 17316.000000 s Sim: -1643774495  Sims/Sec: -94928.072014  Mvs/Sms | 14.0/28.0 | 11.0/18.5 | 7.9/13.0 | 5.7/8.9 | 3.9/5.9 = 9534073856

(yes i let the ply 5 run for nearly 5 hours)

[pappde]

It's been a while, but I will try to recall how it worked. Key notes:

1. increasing "ply" will be exponential, since BMAI will evaluate an entire additional level of actions/states (think minmax algorithm).

2. the cost to evaluate a single state varies depending on the number of moves. Some game states may just have 2 valid moves, and some may have many more. For example, if I've reading the output correctly, there are 14 valid moves from the initial state.

3. as noted in earlier summary, BMAI will either simulate out the result of an action, or will expand and search the resulting game states (meaning ply +1)

4. the purpose of min/max_sims I believe is the minimum/maximum simulations to run from each possible valid move.

5. the purpose of maxbranch is to try to clamp the number of simulations to run from each possible valid move.

Example: (again, I may be remembering incorrectly)

• valid moves = 14
• maxbranch = 500
• desired simulations per move = 500/14 = 35
• clamp to min/max_simulations range of [5,100] = 35 effective sims/move

You can see that if you have a wide range of moves, you're not going to be able to spend much time on each one. This is certainly not great for high variance scenarios (e.g. a d20). In the following example, it will run 5 sims per move.

• valid moves = 50
• maxbranch = 100
• desired simulations per move = 100/50 = 2
• clamp to min/max_simulations range of [5,100] = 5

On the other end, if you have a narrow range of moves, then you will spend a lot of time on each one:

• valid moves = 2
• maxbranch = 500
• desired simulations per move = 500/2 = 250
• clamp to min/max_simulations range of [5,100] = 100 effective

COST
While maxbranch clearly is a key factor in the cost, it is exponential with the ply depth. For example, with ply3, cost probably looks more like O(M*N^3). E.g.:

• Cost = ply0moves * ply1moves * ply2moves * maxbranch

With ply2:

• Cost = ply0moves * ply1moves * maxbranch

Generally speaking, the number of valid moves should decrease with each step forward in the game state.

ASIDE:
Looks like 32-bit overflow in that output code (see ply 5 total Sim time case). Should change those variables to long/int64.