BFS of deterministic 2048 - nickjalbert/improved-funicular GitHub Wiki

Results by Andy, generated with contrib/max_score_calculator.py, using 100 different random seeds and showing stats per each depth over the 100 runs, using pruning for performance speedup:

Depth: 1
Max max tile: 3.08 mean, 2.0 med, 1.3090454537562863 std, 8 max
Max score: 1.72 mean, 0.0 med, 2.209434316742635 std, 8 max
total_state_action_pairs: 4.0 mean, 4.0 med, 0.0 std, 4 max

Depth: 2
Max max tile: 4.44 mean, 4.0 med, 1.251559027772962 std, 8 max
Max score: 4.44 mean, 4.0 med, 1.251559027772962 std, 8 max
total_state_action_pairs: 14.72 mean, 16.0 med, 1.8659046063504956 std, 16 max

Depth: 3
Max max tile: 4.44 mean, 4.0 med, 1.251559027772962 std, 8 max
Max score: 8.88 mean, 8.0 med, 2.503118055545924 std, 16 max
total_state_action_pairs: 47.8 mean, 48.0 med, 7.805126520435142 std, 64 max

Depth: 4
Max max tile: 8.88 mean, 8.0 med, 2.503118055545924 std, 16 max
Max score: 17.76 mean, 16.0 med, 5.006236111091848 std, 32 max
total_state_action_pairs: 128.88 mean, 132.0 med, 25.22589146095732 std, 228 max

Depth: 5
Max max tile: 8.88 mean, 8.0 med, 2.503118055545924 std, 16 max
Max score: 22.2 mean, 20.0 med, 6.25779513886481 std, 40 max
total_state_action_pairs: 320.48 mean, 320.0 med, 80.24618121755077 std, 840 max

Depth: 6
Max max tile: 8.88 mean, 8.0 med, 2.503118055545924 std, 16 max
Max score: 22.28 mean, 20.0 med, 6.280254771902179 std, 40 max
total_state_action_pairs: 634.12 mean, 632.0 med, 254.44053450659152 std, 2960 max

Depth: 7
Max max tile: 8.96 mean, 8.0 med, 2.599692289483509 std, 16 max
Max score: 26.84 mean, 24.0 med, 7.700285708985086 std, 48 max
total_state_action_pairs: 1218.32 mean, 1168.0 med, 886.9202769133199 std, 9844 max

Depth: 8
Max max tile: 8.96 mean, 8.0 med, 2.599692289483509 std, 16 max
Max score: 35.68 mean, 32.0 med, 10.082539362680425 std, 64 max
total_state_action_pairs: 2363.6 mean, 2104.0 med, 2789.1760790599055 std, 29928 max

Depth: 9
Max max tile: 17.76 mean, 16.0 med, 5.006236111091848 std, 32 max
Max score: 57.76 mean, 52.0 med, 16.26107007549009 std, 104 max
total_state_action_pairs: 4456.76 mean, 3722.0 med, 7879.871606974318 std, 82696 max

Depth: 10
Max max tile: 17.76 mean, 16.0 med, 5.006236111091848 std, 32 max
Max score: 57.8 mean, 52.0 med, 16.261611236282818 std, 104 max
total_state_action_pairs: 8352.92 mean, 6388.0 med, 20563.248388170585 std, 212828 max

Depth: 11
Max max tile: 17.76 mean, 16.0 med, 5.006236111091848 std, 32 max
Max score: 62.24 mean, 56.0 med, 17.51177889307652 std, 112 max
total_state_action_pairs: 15515.36 mean, 10592.0 med, 49311.1709200907 std, 506040 max

Depth: 12
Max max tile: 17.76 mean, 16.0 med, 5.006236111091848 std, 32 max
Max score: 71.2 mean, 64.0 med, 20.03197444087824 std, 128 max
total_state_action_pairs: 28449.56 mean, 17784.0 med, 109752.95376201233 std, 1120364 max

Depth: 13
Max max tile: 17.92 mean, 16.0 med, 5.199384578967018 std, 32 max
Max score: 75.96 mean, 68.0 med, 21.64066542414994 std, 136 max
total_state_action_pairs: 51161.88 mean, 28830.0 med, 229012.88107245302 std, 2329688 max

Depth: 14
Max max tile: 17.92 mean, 16.0 med, 5.199384578967018 std, 32 max
Max score: 76.04 mean, 68.0 med, 21.802715427212288 std, 136 max
total_state_action_pairs: 90447.44 mean, 45860.0 med, 453677.200415633 std, 4604320 max

Depth: 15
Max max tile: 17.92 mean, 16.0 med, 5.199384578967018 std, 32 max
Max score: 80.48 mean, 72.0 med, 23.014986421894765 std, 144 max
total_state_action_pairs: 157166.84 mean, 71966.0 med, 860588.4576451704 std, 8719704 max

runtime: 1427.847 seconds
num random seeds: 100

Results by Andy for a single random seed (42), generated with contrib/max_score_calculator.py, with pruning for performance speedup:

Depth: 1
Max max tile: 4
Max score: 4
total_state_action_pairs: 4

Depth: 2
Max max tile: 4
Max score: 4
total_state_action_pairs: 12

Depth: 3
Max max tile: 4
Max score: 8
total_state_action_pairs: 36

Depth: 4
Max max tile: 8
Max score: 16
total_state_action_pairs: 100

Depth: 5
Max max tile: 8
Max score: 20
total_state_action_pairs: 248

Depth: 6
Max max tile: 8
Max score: 20
total_state_action_pairs: 484

Depth: 7
Max max tile: 8
Max score: 24
total_state_action_pairs: 892

Depth: 8
Max max tile: 8
Max score: 32
total_state_action_pairs: 1704

Depth: 9
Max max tile: 16
Max score: 52
total_state_action_pairs: 3080

Depth: 10
Max max tile: 16
Max score: 52
total_state_action_pairs: 5880

Depth: 11
Max max tile: 16
Max score: 56
total_state_action_pairs: 10420

Depth: 12
Max max tile: 16
Max score: 64
total_state_action_pairs: 17988

Depth: 13
Max max tile: 16
Max score: 68
total_state_action_pairs: 30208

Depth: 14
Max max tile: 16
Max score: 68
total_state_action_pairs: 48352

Depth: 15
Max max tile: 16
Max score: 72
total_state_action_pairs: 76136

Depth: 16
Max max tile: 16
Max score: 80
total_state_action_pairs: 118472

Depth: 17
Max max tile: 16
Max score: 100
total_state_action_pairs: 183960

Depth: 18
Max max tile: 32
Max score: 132
total_state_action_pairs: 276396

Depth: 19
Max max tile: 32
Max score: 136
total_state_action_pairs: 412604

Depth: 20
Max max tile: 32
Max score: 144
total_state_action_pairs: 607604

runtime: 75.277 seconds

Results generated by Nick for single random seed: 42

$ python contrib/depth_limited_search.py

DFS with Depth Limit 20 and random seed 42

Depth: 1:
	Max Tile: 4
	Max Score: 4
	Total State Action Pairs: 3
	Depth Time: 0.0 sec
Depth: 2:
	Max Tile: 4
	Max Score: 4
	Total State Action Pairs: 13
	Depth Time: 0.0 sec
Depth: 3:
	Max Tile: 4
	Max Score: 8
	Total State Action Pairs: 46
	Depth Time: 0.0 sec
Depth: 4:
	Max Tile: 8
	Max Score: 16
	Total State Action Pairs: 142
	Depth Time: 0.0 sec
Depth: 5:
	Max Tile: 8
	Max Score: 20
	Total State Action Pairs: 375
	Depth Time: 0.1 sec
Depth: 6:
	Max Tile: 8
	Max Score: 20
	Total State Action Pairs: 834
	Depth Time: 0.4 sec
Depth: 7:
	Max Tile: 8
	Max Score: 24
	Total State Action Pairs: 1670
	Depth Time: 1.5 sec
Depth: 8:
	Max Tile: 8
	Max Score: 32
	Total State Action Pairs: 3265
	Depth Time: 6.3 sec
Depth: 9:
	Max Tile: 16
	Max Score: 52
	Total State Action Pairs: 6153
	Depth Time: 39.7 sec
Depth: 10:
	Max Tile: 16
	Max Score: 52
	Total State Action Pairs: 11614
	Depth Time: 421.1 sec
Depth: 11:
	Max Tile: 16
	Max Score: 56
	Total State Action Pairs: 21444
	Depth Time: 4983.8 sec
Depth: 12:
	Max Tile: 16
	Max Score: 64
	Total State Action Pairs: 38435
	Depth Time: 65397.4 sec