Skip to content

Latest commit

 

History

History
1336 lines (1131 loc) · 51.8 KB

notes.org

File metadata and controls

1336 lines (1131 loc) · 51.8 KB
Raw

Notes

<2021-03-29 Mon 16:43>

Me vs 3-ply

main.run_game( (main.MinimaxPlayer(depth = 3), main.HumanPlayer() ) )
['I11', 'J11', 'J12', 'K10', 'L14', 'K12', 'SE SE ', 'L14', 'NW W N ', 'I10', 'J9', 'I9', 'W SE ']
          1111111111
 1234567890123456789
A+++++++++++++++++++
B+++++++++++++++++++
C+++++++++++++++++++
D+++++++++++++++++++
E+++++++++++++++++++
F+++++++++++++++++++
G+++++++++++++++++++
H+++++++++++++++++++
I+++++++++++++++++++
J+++++++++++++++++++
K+++++++++++++++++++
L++++++++++●++++++++
M+++++++++++++++++++
N+++++++++++++++++++
O+++++++++++++++++++
Side to move: Right
Moves made: 13
Ball at: [11 10]

I’ve lost one step of ground

3-ply vs plodding player

main.run_game( (main.MinimaxPlayer(depth = 3), main.PloddingPlayer() ) )
['I11', 'H9', 'SE ', 'J11', 'W ', 'J9', 'I8', 'W ', 'H11', 'J7', 'N E E ', 'H11', 'W ', 'H9', 'W ', 'H7', 'I6', 'W ', 'J9', 'H5', 'S E E ', 'J9', 'W ', 'J7', 'W ', 'J5', 'I4', 'W ', 'H7', 'J3', 'N E E ', 'H7', 'W ', 'H5', 'W ', 'H3', 'I2', 'W ', 'J5', 'H1', 'S E E ', 'J5', 'W ', 'J3', 'W ', 'J1', 'W ']
          1111111111
 1234567890123456789
A+++++++++++++++++++
B+++++++++++++++++++
C+++++++++++++++++++
D+++++++++++++++++++
E+++++++++++++++++++
F+++++++++++++++++++
G+++++++++++++++++++
H○++++++++++++++++++
I+++++++++++++++++++
J+++++++++++++++++++
K+++++++++++++++++++
L+++++++++++++++++++
M+++++++++++++++++++
N+++++++++++++++++++
O+++++++++++++++++++
Side to move: Right
Moves made: 47
Ball at: [ 9 -1]

Right has won

PloddingPlayer wins! It’s exploiting that when the board looks like this (next picture), everything looks the same to 3-ply, so it decides to help PloddingPlayer because that’s the last move it considers.

          1111111111
 1234567890123456789
A+++++++++++++++++++
B+++++++++++++++++++
C+++++++++++++++++++
D+++++++++++++++++++
E+++++++++++++++++++
F+++++++++++++++++++
G+++++++++++++++++++
H○++++++++++++++++++
I+++++++++++++++++++
J++○●+++++++++++++++
K+++++++++++++++++++
L+++++++++++++++++++
M+++++++++++++++++++
N+++++++++++++++++++
O+++++++++++++++++++
Side to move: Left
Moves made: 44
Ball at: [9 3]

Introducing alpha-beta

main.run_game( (main.MinimaxPlayer(depth = 3), main.MinimaxPlayer(depth =3) ) )
['I11', 'K11', 'J12', 'K12', 'K13', 'L13', 'L14', 'M14', 'M15', 'N15', 'N14', 'K14', 'L15', 'N13', 'M11', 'L10', 'K10', 'K9', 'J9', 'J8', 'I8', 'I9']

22 moves in 2502 seconds

(19 moves in 1580 seconds)

main.run_game( (main.NegamaxABPlayer(depth = 3), main.NegamaxABPlayer(depth =3) ) )

No presorting

['I11', 'K11', 'J12', 'K12', 'K13', 'L13', 'L14', 'M14', 'M15', 'N15', 'N14', 'K14', 'L15', 'N13', 'M11', 'L10', 'K10', 'K9', 'J9']

19 moves in 1680 seconds

So alpha-beta is slightly slower? Is it actually ever pruning?

It seems to be pruning one step away from the nodes, but never before

But at least the two move lists match

Number of calls

Let P1 = main.run_game( (main.NegamaxPlayer(depth = 3), main.NegamaxPlayer(depth =3) ) )

Let P2 = main.run_game( (main.NegamaxABPlayer(depth = 3), main.NegamaxABPlayer(depth =3) ) ) which does not presort moves

Let P3 = main.run_game( (main.NegamaxABPlayer(depth = 3), main.NegamaxABPlayer(depth =3) ) ) which presorts moves using a 2-ply search

Let P4 = main.run_game( (main.NegamaxABPlayer(depth = 3), main.NegamaxABPlayer(depth =3) ) ) which presorts moves using a 1-ply search, i.e. it’s likely to have a jump 1st in that list

First move I11

P1: 35656 calls, 9.03 secs
P2: 5563 calls, 9.60 secs
P3: 6387 calls, 10.93 secs
P4: 5587 calls, 11.98 secs

2nd move K11
P1: 68518 calls, 27.02 secs (this is cumulative)
p2: 9490 calls, 28.839 secs
P3: 10862 calls, 32.82 secs
P4: 9523 calls, 37.481 secs (longer because more programs were running at same time?)

3rd move J12
P1: 125696 calls, 64.2721 secs
P2: 117663 calls, 68.58 secs
P3: 119831 calls, 74.72 secs
P4: 117706 calls, 88.9686 secs


4th move K12
P1: 148448 calls, 106.67 secs
P2: 16389 calls, 111.23 secs
P3: 18841 calls, 118.05 secs,
P4: 16435 calls, 138.09 secs

P3 needed slightly more calls because it was doing a more advanced pre-sort

The number of call needed for A-B seemed to oscillate depending on whose turn it was

The pre-orderings used by P2, P3, P4 were very similar. e.g. for move 4, they were

['F8', 'F9', 'F10', 'F11', 'F12', 'G8', 'G9', 'G10', 'G11', 'G12', 'G13', 'H8', 'H9', 'H11', 'H12', 'H13', 'H14', 'I8', 'I9', 'I10', 'I12', 'I13', 'I14', 'J8', 'J9', 'J10', 'J11', 'J13', 'J14', 'K9', 'K10', 'K12', 'K13', 'K14', 'L9', 'L10', 'L11', 'L12', 'L13', 'L14', 'M9', 'M10', 'M11', 'M12', 'M13', 'SE ']
['F8', 'F9', 'F10', 'F11', 'F12', 'G8', 'G10', 'G11', 'G12', 'G13', 'H8', 'H11', 'H12', 'H13', 'I8', 'I10', 'I12', 'I13', 'J8', 'J9', 'J10', 'J11', 'J12', 'J13', 'K10', 'K12', 'K13', 'L11', 'L12', 'L13', 'M10', 'M11', 'M12', 'M13', 'SE ', 'SE SW ', 'L10', 'G9', 'H9', 'I9', 'K9', 'L9', 'M9']
['F8', 'F9', 'F10', 'F11', 'F12', 'G8', 'G9', 'G10', 'G11', 'G12', 'G13', 'H8', 'H9', 'H11', 'H12', 'H13', 'H14', 'I8', 'I9', 'I10', 'I12', 'I13', 'I14', 'J8', 'J9', 'J10', 'J11', 'J13', 'J14', 'K9', 'K10', 'K12', 'K13', 'K14', 'L9', 'L10', 'L11', 'L12', 'L13', 'L14', 'M9', 'M10', 'M11', 'M12', 'M13', 'SE ']

It was weird how AB could use an order of magnitude fewer calls and still take the same amount of time. I need to profile it

4-ply vs 4-ply

main.run_game( (main.NegamaxABPlayer(depth = 4), main.NegamaxABPlayer(depth =4) ) )
          1111111111
 1234567890123456789
A+++++++++++++++++++
B+++++++++++++++++++
C+++++++++++++++++++
D+++++++++++++++++++
E+++++++++++++++++++
F+++++++++++++++++++
G+++++++++++++++++++
H+++++++++●+++++++++
I+++++++++++++++++++
J+++++++++++++++++++
K+++++++++++++++++++
L+++++++++++++++++++
M+++++++++++++++++++
N+++++++++++++++++++
O+++++++++++++++++++
Side to move: Left
Moves made: 0
Ball at: [7 9]

Applying static evaluator to current position:
0.5
Initial score is 0
['G11', 'H11', 'I11', 'F8', 'F9', 'F10', 'F11', 'F12', 'G8', 'G10', 'G12', 'H8', 'H12', 'I8', 'I10', 'I12', 'J8', 'J9', 'J10', 'J11', 'J12', 'G9', 'H9', 'I9']
New best move is G11 which has score of 0.5
New best move is H11 which has score of 0.6111111111111112
['H11']
Duration of game so far is 83.52776503562927 seconds
          1111111111
 1234567890123456789
A+++++++++++++++++++
B+++++++++++++++++++
C+++++++++++++++++++
D+++++++++++++++++++
E+++++++++++++++++++
F+++++++++++++++++++
G+++++++++++++++++++
H+++++++++●○++++++++
I+++++++++++++++++++
J+++++++++++++++++++
K+++++++++++++++++++
L+++++++++++++++++++
M+++++++++++++++++++
N+++++++++++++++++++
O+++++++++++++++++++
Side to move: Right
Moves made: 1
Ball at: [7 9]

Applying static evaluator to current position:
0.5
Initial score is 0
['F8', 'F9', 'F10', 'F11', 'F12', 'F13', 'G8', 'G9', 'G10', 'G11', 'G12', 'H8', 'H9', 'I8', 'I9', 'I10', 'I11', 'I12', 'J8', 'J9', 'J10', 'J11', 'J12', 'J13', 'E ', 'H12', 'G13', 'H13', 'I13']
New best move is F8 which has score of 0.2777777777777778
New best move is F9 which has score of 0.2777777777777778
New best move is F10 which has score of 0.2777777777777778
New best move is F11 which has score of 0.2777777777777778
New best move is F12 which has score of 0.2777777777777778
New best move is F13 which has score of 0.2777777777777778
New best move is G8 which has score of 0.2777777777777778
New best move is G9 which has score of 0.38888888888888884
New best move is G10 which has score of 0.38888888888888884
New best move is G11 which has score of 0.38888888888888884
New best move is H9 which has score of 0.38888888888888884
New best move is I9 which has score of 0.38888888888888884
New best move is I10 which has score of 0.38888888888888884
New best move is I11 which has score of 0.38888888888888884
['H11', 'I11']
Duration of game so far is 302.7638237476349 seconds
          1111111111
 1234567890123456789
A+++++++++++++++++++
B+++++++++++++++++++
C+++++++++++++++++++
D+++++++++++++++++++
E+++++++++++++++++++
F+++++++++++++++++++
G+++++++++++++++++++
H+++++++++●○++++++++
I++++++++++○++++++++
J+++++++++++++++++++
K+++++++++++++++++++
L+++++++++++++++++++
M+++++++++++++++++++
N+++++++++++++++++++
O+++++++++++++++++++
Side to move: Left
Moves made: 2
Ball at: [7 9]

Applying static evaluator to current position:
0.5
Initial score is 0
['H12', 'SE ', 'F8', 'F9', 'F10', 'F11', 'F12', 'F13', 'G8', 'G10', 'G11', 'G12', 'G13', 'H8', 'H13', 'I8', 'I10', 'I12', 'I13', 'J8', 'J11', 'J12', 'J13', 'K10', 'K11', 'K12', 'K13', 'E ', 'E SW ', 'J10', 'G9', 'H9', 'I9', 'J9', 'K9']
New best move is H12 which has score of 0.5555555555555556

['H11', 'I11', 'H12']
Duration of game so far is 1340.3641250133514 seconds
          1111111111
 1234567890123456789
A+++++++++++++++++++
B+++++++++++++++++++
C+++++++++++++++++++
D+++++++++++++++++++
E+++++++++++++++++++
F+++++++++++++++++++
G+++++++++++++++++++
H+++++++++●○○+++++++
I++++++++++○++++++++
J+++++++++++++++++++
K+++++++++++++++++++
L+++++++++++++++++++
M+++++++++++++++++++
N+++++++++++++++++++
O+++++++++++++++++++
Side to move: Right
Moves made: 3
Ball at: [7 9]

Applying static evaluator to current position:
0.5
Initial score is 0
['I12', 'G12', 'SE ', 'F8', 'F9', 'F10', 'F11', 'F12', 'F13', 'F14', 'G8', 'G9', 'G10', 'G11', 'G13', 'H8', 'H9', 'I8', 'I9', 'I10', 'J8', 'J9', 'J10', 'J11', 'J12', 'J14', 'K9', 'K10', 'K11', 'K12', 'E ', 'H13', 'I13', 'J13', 'K13', 'G14', 'H14', 'I14']
New best move is I12 which has score of 0.4444444444444444
['H11', 'I11', 'H12', 'I12']
Duration of game so far is 2437.7154240608215 seconds
          1111111111
 1234567890123456789
A+++++++++++++++++++
B+++++++++++++++++++
C+++++++++++++++++++
D+++++++++++++++++++
E+++++++++++++++++++
F+++++++++++++++++++
G+++++++++++++++++++
H+++++++++●○○+++++++
I++++++++++○○+++++++
J+++++++++++++++++++
K+++++++++++++++++++
L+++++++++++++++++++
M+++++++++++++++++++
N+++++++++++++++++++
O+++++++++++++++++++
Side to move: Left
Moves made: 4
Ball at: [7 9]

Applying static evaluator to current position:
0.5
Initial score is 0
['G12', 'J12', 'E ', 'E SW ', 'E SW N ', 'F8', 'F9', 'F10', 'F11', 'F12', 'F13', 'F14', 'G8', 'G11', 'G13', 'G14', 'H8', 'H13', 'H14', 'I8', 'I13', 'I14', 'J8', 'J11', 'J13', 'J14', 'K9', 'K11', 'K12', 'K13', 'K14', 'SE ', 'SE N ', 'SE N SW ', 'G10', 'I10', 'J10', 'K10', 'G9', 'H9', 'I9', 'J9']
New best move is G12 which has score of 0.5555555555555556
New best move is J12 which has score of 0.5555555555555556
^C

I was running other programs at the same time, which maybe made it slower. But not much slower.

Profiling

cProfile.run("main.run_game( (main.NegamaxABPlayer(depth = 3), main.NegamaxABPlayer(depth =3) ) )")

Turned off preordering

Ran for 8 moves—855 secs, a little slower

Results:

Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        9    0.000    0.000    0.000    0.000 <__array_function__ internals>:2(amax)
        9    0.000    0.000    0.000    0.000 <__array_function__ internals>:2(amin)
        1    0.000    0.000  855.241  855.241 <string>:1(<module>)
        9    0.000    0.000    0.000    0.000 _asarray.py:14(asarray)
        9    0.000    0.000    0.000    0.000 arrayprint.py:1124(__init__)
       18    0.000    0.000    0.000    0.000 arrayprint.py:1132(__call__)
        9    0.000    0.000    0.001    0.000 arrayprint.py:1473(_array_str_implementation)
        9    0.000    0.000    0.000    0.000 arrayprint.py:358(_get_formatdict)
        9    0.000    0.000    0.000    0.000 arrayprint.py:365(<lambda>)
        9    0.000    0.000    0.001    0.000 arrayprint.py:409(_get_format_function)
        9    0.000    0.000    0.001    0.000 arrayprint.py:461(wrapper)
        9    0.000    0.000    0.001    0.000 arrayprint.py:478(_array2string)
        9    0.000    0.000    0.001    0.000 arrayprint.py:516(array2string)
        9    0.000    0.000    0.000    0.000 arrayprint.py:60(_make_options_dict)
        9    0.000    0.000    0.000    0.000 arrayprint.py:65(<dictcomp>)
       18    0.000    0.000    0.000    0.000 arrayprint.py:695(_extendLine)
        9    0.000    0.000    0.000    0.000 arrayprint.py:709(_formatArray)
     27/9    /0.000/    0.000    *0.000*    0.000 arrayprint.py:718(recurser)
567136990/1884177  /390.914/    0.000  *791.233*    0.000 copy.py:128(deepcopy)
536990171   /39.844/    0.000   *39.844*    0.000 copy.py:182(_deepcopy_atomic)
30146818/1884177  /161.185/    0.000  *787.313*    0.000 copy.py:200(_deepcopy_list)
 30146816   /12.870/    0.000   *18.299*    0.000 copy.py:242(_keep_alive)
        9    0.000    0.000    0.000    0.000 fromnumeric.py:2584(_amax_dispatcher)
        9    0.000    0.000    0.000    0.000 fromnumeric.py:2589(amax)
        9    0.000    0.000    0.000    0.000 fromnumeric.py:2709(_amin_dispatcher)
        9    0.000    0.000    0.000    0.000 fromnumeric.py:2714(amin)
       18    0.000    0.000    0.000    0.000 fromnumeric.py:70(_wrapreduction)
       18    0.000    0.000    0.000    0.000 fromnumeric.py:71(<dictcomp>)
        9    0.000    0.000    0.002    0.000 main.py:113(pretty_print_details)
  1260319    0.506    0.000    0.506    0.000 main.py:141(increment)
        8    0.004    0.000    *0.977*    0.122 main.py:149(get_man_moves)
    20011   48.742    0.002  *556.412*    0.028 main.py:165(get_nearby_man_moves)
77981/20018    3.687    0.000  *294.203*    0.015 main.py:192(get_ball_moves)
   831599    3.410    0.000    *3.410*    0.000 main.py:249(is_on_board)
        8    0.000    0.000    1.055    0.132 main.py:254(get_all_moves)
    20011    0.060    0.000  850.614    0.043 main.py:259(get_all_nearby_moves)
        1    0.003    0.003  855.241  855.241 main.py:300(run_game)
   562834    0.529    0.000    0.529    0.000 main.py:336(score) i.e. LocationEvaluator's score
        2    0.000    0.000    0.000    0.000 main.py:415(__init__)
582827/360    2.734    0.000  *853.844*    2.372 main.py:421(score) i.e. NegamaxABPlayer's score
        9    0.030    0.003  854.176   94.908 main.py:463(make_move)
  1884178    2.217    0.000  793.450    0.000 main.py:48(__init__)
        1    0.000    0.000    0.000    0.000 main.py:61(<listcomp>)
       15    0.000    0.000    0.000    0.000 main.py:62(<listcomp>)
  1884177    1.784    0.000  795.234    0.000 main.py:67(copy)
        9    0.001    0.000    0.002    0.000 main.py:75(pretty_string_details)
        9    0.000    0.000    0.000    0.000 {built-in method _thread.get_ident}
        1    0.000    0.000  855.241  855.241 {built-in method builtins.exec}
629314809   /51.399/    0.000   51.399    0.000 {built-in method builtins.id}
       27    0.000    0.000    0.000    0.000 {built-in method builtins.issubclass}
      171    0.000    0.000    0.000    0.000 {built-in method builtins.len}
        9    0.000    0.000    0.000    0.000 {built-in method builtins.locals}
  1164950    0.260    0.000    0.260    0.000 {built-in method builtins.max}
      301    0.006    0.000    0.006    0.000 {built-in method builtins.print}
        9    0.000    0.000    0.000    0.000 {built-in method numpy.array}
       18    0.000    0.000    0.000    0.000 {built-in method numpy.core._multiarray_umath.implement_array_function}
        9    0.000    0.000    0.000    0.000 {built-in method time.time}
        9    0.000    0.000    0.000    0.000 {method 'add' of 'set' objects}
593515459   /49.483/    0.000   49.483    0.000 {method 'append' of 'list' objects}
        9    0.000    0.000    0.000    0.000 {method 'copy' of 'dict' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        9    0.000    0.000    0.000    0.000 {method 'discard' of 'set' objects}
        9    0.000    0.000    0.000    0.000 {method 'format' of 'str' objects}
1134273980   /85.539/    0.000   85.539    0.000 {method 'get' of 'dict' objects}
       27    0.000    0.000    0.000    0.000 {method 'items' of 'dict' objects}
    77990    0.013    0.000    0.013    0.000 {method 'keys' of 'dict' objects}
       18    0.000    0.000    0.000    0.000 {method 'reduce' of 'numpy.ufunc' objects}
        9    0.000    0.000    0.000    0.000 {method 'rstrip' of 'str' objects}
    20027    0.017    0.000    0.017    0.000 {method 'update' of 'dict' objects}
    20001    0.004    0.000    0.004    0.000 {method 'values' of 'dict' objects}

Hmm. We spent 390/855 secs inside deepcopy and 161 secs inside of deepcopy_list, not counting whatever they called. That’s why we spend 795 secs (cumulative) inside Board’s copy method.

Let’s fix that.

Also, we spent literally half a second in the static eval, despite calling it half a million times. Even multiplying that by 10 (i.e. no alpha-beta), that’s still 5 seconds out of 855.

So calling it a million times takes a second.

Adjusting the copy() method

Which had a big effect—an order of magnitude as fast

main.run_game( (main.NegamaxABPlayer(depth = 3), main.NegamaxABPlayer(depth =3) ) )

After 22 moves, it had taken 405 seconds, not 2502 seconds

End of game:

217602 calls
['I11', 'K11', 'J12', 'K12', 'K13', 'L13', 'L14', 'M14', 'M15', 'N15', 'N14', 'K14', 'L15', 'N13', 'M11', 'L10', 'K10', 'K9', 'J9', 'J8', 'I8', 'I9', 'SE W NW E SW ', 'L7', 'N7', 'M6', 'N6', 'M7', 'N8', 'M8', 'N9', 'M9', 'N10', 'N5', 'O4', 'J7', 'I7', 'I6', 'H6', 'H5', 'G5', 'G4', 'F4', 'F3', 'E3', 'E2']
Duration of game so far is 1134.6323010921478 seconds
          1111111111
 1234567890123456789
A+++++++++++++++++++
B+++++++++++++++++++
C+++++++++++++++++++
D+++++++++++++++++++
E+○○++++++++++++++++
F++○○+++++++++++++++
G+++○○++++++++++++++
H++++○○+++++++++++++
I+++++○○++++++++++++
J++++++○++++++++++++
K+++++++●+○○○+○+++++
L++++++○+++++○+○++++
M+++++○○○○++++○+++++
N++++○○○○○○+++++++++
O+++○+++++++++++++++
Side to move: Left
Moves made: 46
Ball at: [10  7]

And then Left committed suicide!?

['I11', 'K11', 'J12', 'K12', 'K13', 'L13', 'L14', 'M14', 'M15', 'N15', 'N14', 'K14', 'L15', 'N13', 'M11', 'L10', 'K10', 'K9', 'J9', 'J8', 'I8', 'I9', 'SE W NW E SW ', 'L7', 'N7', 'M6', 'N6', 'M7', 'N8', 'M8', 'N9', 'M9', 'N10', 'N5', 'O4', 'J7', 'I7', 'I6', 'H6', 'H5', 'G5', 'G4', 'F4', 'F3', 'E3', 'E2', 'NW ']

Total: 1186 seconds

More profiling

numpy does not speed it up That is, it takes 51.5 ns to access a number in a 2d list, and 49.4 ns to access a string, but it takes 244 ns to access a number in a 2d numpy array

Let’s profile and stop it after 8 moves

cProfile.run("main.run_game( (main.NegamaxABPlayer(depth = 3), main.NegamaxABPlayer(depth =3) ) )")
^C         11101517 function calls (10385145 primitive calls) in 74.622 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        9    0.000    0.000    0.000    0.000 <__array_function__ internals>:2(amax)
        9    0.000    0.000    0.000    0.000 <__array_function__ internals>:2(amin)
        1    0.000    0.000   74.622   74.622 <string>:1(<module>)
        9    0.000    0.000    0.000    0.000 _asarray.py:14(asarray)
        9    0.000    0.000    0.000    0.000 arrayprint.py:1124(__init__)
       18    0.000    0.000    0.000    0.000 arrayprint.py:1132(__call__)
        9    0.000    0.000    0.001    0.000 arrayprint.py:1473(_array_str_implementation)
        9    0.000    0.000    0.000    0.000 arrayprint.py:358(_get_formatdict)
        9    0.000    0.000    0.000    0.000 arrayprint.py:365(<lambda>)
        9    0.000    0.000    0.001    0.000 arrayprint.py:409(_get_format_function)
        9    0.000    0.000    0.001    0.000 arrayprint.py:461(wrapper)
        9    0.000    0.000    0.001    0.000 arrayprint.py:478(_array2string)
        9    0.000    0.000    0.001    0.000 arrayprint.py:516(array2string)
        9    0.000    0.000    0.000    0.000 arrayprint.py:60(_make_options_dict)
        9    0.000    0.000    0.000    0.000 arrayprint.py:65(<dictcomp>)
       18    0.000    0.000    0.000    0.000 arrayprint.py:695(_extendLine)
        9    0.000    0.000    0.000    0.000 arrayprint.py:709(_formatArray)
     27/9    0.000    0.000    0.000    0.000 arrayprint.py:718(recurser)
        9    0.000    0.000    0.000    0.000 fromnumeric.py:2584(_amax_dispatcher)
        9    0.000    0.000    0.000    0.000 fromnumeric.py:2589(amax)
        9    0.000    0.000    0.000    0.000 fromnumeric.py:2709(_amin_dispatcher)
        9    0.000    0.000    0.000    0.000 fromnumeric.py:2714(amin)
       18    0.000    0.000    0.000    0.000 fromnumeric.py:70(_wrapreduction)
       18    0.000    0.000    0.000    0.000 fromnumeric.py:71(<dictcomp>)
        9    0.000    0.000    0.002    0.000 main.py:114(pretty_print_details)
  1336613    0.364    0.000    0.364    0.000 main.py:142(increment)
        8    0.003    0.000    0.028    0.004 main.py:150(get_man_moves)
    20981   *54.685*    0.003   61.681    0.003 main.py:166(get_nearby_man_moves)
83823/20988    2.902    0.000    9.047    0.000 main.py:225(get_ball_moves)
   896828    3.652    0.000    3.652    0.000 main.py:282(is_on_board)
        8    0.000    0.000    0.032    0.004 main.py:287(get_all_moves)
    20981    0.050    0.000   70.787    0.003 main.py:292(get_all_nearby_moves)
        1    0.002    0.002   74.622   74.622 main.py:338(run_game)
   632929    0.639    0.000    0.639    0.000 main.py:374(score)
        2    0.000    0.000    0.000    0.000 main.py:453(__init__)
653892/373    2.831    0.000   74.524    0.200 main.py:463(score)
  2007207    1.178    0.000    7.888    0.000 main.py:49(__init__)
        9    0.025    0.003   74.585    8.287 main.py:510(make_move)
  2007206    6.710    0.000    6.710    0.000 main.py:60(<listcomp>)
        1    0.000    0.000    0.000    0.000 main.py:62(<listcomp>)
       15    0.000    0.000    0.000    0.000 main.py:63(<listcomp>)
  2007206    1.251    0.000    9.139    0.000 main.py:68(copy)
        9    0.001    0.000    0.002    0.000 main.py:76(pretty_string_details)
        9    0.000    0.000    0.000    0.000 {built-in method _thread.get_ident}
        1    0.000    0.000   74.622   74.622 {built-in method builtins.exec}
        9    0.000    0.000    0.000    0.000 {built-in method builtins.id}
       27    0.000    0.000    0.000    0.000 {built-in method builtins.issubclass}
      171    0.000    0.000    0.000    0.000 {built-in method builtins.len}
        9    0.000    0.000    0.000    0.000 {built-in method builtins.locals}
  1307054    0.295    0.000    0.295    0.000 {built-in method builtins.max}
      312    0.006    0.000    0.006    0.000 {built-in method builtins.print}
        9    0.000    0.000    0.000    0.000 {built-in method numpy.array}
       18    0.000    0.000    0.000    0.000 {built-in method numpy.core._multiarray_umath.implement_array_function}
        9    0.000    0.000    0.000    0.000 {built-in method time.time}
        9    0.000    0.000    0.000    0.000 {method 'add' of 'set' objects}
        8    0.000    0.000    0.000    0.000 {method 'append' of 'list' objects}
        9    0.000    0.000    0.000    0.000 {method 'copy' of 'dict' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        9    0.000    0.000    0.000    0.000 {method 'discard' of 'set' objects}
        9    0.000    0.000    0.000    0.000 {method 'format' of 'str' objects}
       27    0.000    0.000    0.000    0.000 {method 'items' of 'dict' objects}
    83832    0.011    0.000    0.011    0.000 {method 'keys' of 'dict' objects}
       18    0.000    0.000    0.000    0.000 {method 'reduce' of 'numpy.ufunc' objects}
        9    0.000    0.000    0.000    0.000 {method 'rstrip' of 'str' objects}
    20997    0.013    0.000    0.013    0.000 {method 'update' of 'dict' objects}
    20971    0.003    0.000    0.003    0.000 {method 'values' of 'dict' objects}

get_nearby_man_moves() takes 54 of 74 moves

That method (I found) takes twice as long as get_man_moves(), but that’s OK, because else the branching would be horrible.

I wonder if there’s a way to use bit arrays to find all the spaces within two steps of a pieces.

Removing if’s in the method (and using equivalent expressions) didn’t help

But redoing the method worked. Instead of picking a square, and checking whether it’s within 2 steps of a piece, we first find a piece, and then do every space within 2 steps

The new method is called test. On a blank board, it’s faster:

    In [4]: %timeit b.get_all_moves()
1.18 ms ± 27.1 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

In [5]: %timeit b.get_all_nearby_moves()
2.75 ms ± 35.9 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [6]: %timeit b.test()
1.33 ms ± 40.7 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Instead we randomly put men on the board:

In [13]: b.pretty_print()
+○+++++○○++++○+++++
++++++++++++++○+○++
++○++++++++++++○+++
++++++○++○++++++○+○
++○++++++++++++++○○
++++++○+++++++○++++
+++++++○+++++++++++
○++○++○++●++○+++○○+
+++++++++++○○+○++++
+++++○+++++++++○○++
+++++○+++++++++++++
+○++++++++++++○++++
++++++○○+○++++++++○
++++○++++++○+○○○+++
++++++++○++++++++++

It’s still faster:

In [15]: %timeit b.get_all_nearby_moves()
3.01 ms ± 90.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [17]: %timeit b.test()
1.37 ms ± 23.1 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

We put the men in a corner:

In [20]: b.pretty_print()
○○○○○○+++++++++++++
○○○○○○+++++++++++++
○○○○○○+++++++++++++
○○○○○○+++++++++++++
○○○○○○+++++++++++++
○○○○○○+++++++++++++
+++++++++++++++++++
+++++++++●+++++++++
+++++++++++++++++++
+++++++++++++++++++
+++++++++++++++++++
+++++++++++++++++++
+++++++++++++++++++
+++++++++++++++++++
+++++++++++++++++++

Still faster:

In [23]: %timeit b.get_all_nearby_moves()
2.34 ms ± 43.6 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [24]: %timeit b.test()
546 µs ± 15.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Profiling confirms it—I stopped after 8 moves

cProfile.run("main.run_game( (main.NegamaxABPlayer(depth = 3, test = True), main.NegamaxABPlayer(depth =3, test
   ...:  = True) ) )")
   ^C         12224399 function calls (11520265 primitive calls) in 23.849 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        9    0.000    0.000    0.000    0.000 <__array_function__ internals>:2(amax)
        9    0.000    0.000    0.000    0.000 <__array_function__ internals>:2(amin)
        1    0.000    0.000   23.849   23.849 <string>:1(<module>)
        9    0.000    0.000    0.000    0.000 _asarray.py:14(asarray)
        9    0.000    0.000    0.000    0.000 arrayprint.py:1124(__init__)
       18    0.000    0.000    0.000    0.000 arrayprint.py:1132(__call__)
        9    0.000    0.000    0.001    0.000 arrayprint.py:1473(_array_str_implementation)
        9    0.000    0.000    0.000    0.000 arrayprint.py:358(_get_formatdict)
        9    0.000    0.000    0.000    0.000 arrayprint.py:365(<lambda>)
        9    0.000    0.000    0.000    0.000 arrayprint.py:409(_get_format_function)
        9    0.000    0.000    0.001    0.000 arrayprint.py:461(wrapper)
        9    0.000    0.000    0.001    0.000 arrayprint.py:478(_array2string)
        9    0.000    0.000    0.001    0.000 arrayprint.py:516(array2string)
        9    0.000    0.000    0.000    0.000 arrayprint.py:60(_make_options_dict)
        9    0.000    0.000    0.000    0.000 arrayprint.py:65(<dictcomp>)
       18    0.000    0.000    0.000    0.000 arrayprint.py:695(_extendLine)
        9    0.000    0.000    0.000    0.000 arrayprint.py:709(_formatArray)
     27/9    0.000    0.000    0.000    0.000 arrayprint.py:718(recurser)
        9    0.000    0.000    0.000    0.000 fromnumeric.py:2584(_amax_dispatcher)
        9    0.000    0.000    0.000    0.000 fromnumeric.py:2589(amax)
        9    0.000    0.000    0.000    0.000 fromnumeric.py:2709(_amin_dispatcher)
        9    0.000    0.000    0.000    0.000 fromnumeric.py:2714(amin)
       18    0.000    0.000    0.000    0.000 fromnumeric.py:70(_wrapreduction)
       18    0.000    0.000    0.000    0.000 fromnumeric.py:71(<dictcomp>)
        9    0.000    0.000    0.002    0.000 main.py:114(pretty_print_details)
  1324494    0.354    0.000    0.354    0.000 main.py:142(increment)
        8    0.002    0.000    0.028    0.003 main.py:150(get_man_moves)
    20824    *3.922*   0.000   11.039    0.001 main.py:193(test)
82649/20832    2.833    0.000    8.931    0.000 main.py:225(get_ball_moves)
   883681    3.641    0.000    3.641    0.000 main.py:282(is_on_board)
        8    0.000    0.000    0.030    0.004 main.py:287(get_all_moves)
    20824    0.081    0.000   20.060    0.001 main.py:297(test_get_all_nearby_moves)
        1    0.002    0.002   23.849   23.849 main.py:338(run_game)
   621864    0.634    0.000    0.634    0.000 main.py:374(score)
        2    0.000    0.000    0.000    0.000 main.py:453(__init__)
642670/371    2.799    0.000   23.780    0.064 main.py:463(score)
  1985688    1.175    0.000    7.850    0.000 main.py:49(__init__)
        9    0.023    0.003   23.815    2.646 main.py:510(make_move)
  1985687    6.675    0.000    6.675    0.000 main.py:60(<listcomp>)
        1    0.000    0.000    0.000    0.000 main.py:62(<listcomp>)
       15    0.000    0.000    0.000    0.000 main.py:63(<listcomp>)
  1985687    1.249    0.000    9.098    0.000 main.py:68(copy)
        9    0.001    0.000    0.002    0.000 main.py:76(pretty_string_details)
        9    0.000    0.000    0.000    0.000 {built-in method _thread.get_ident}
        1    0.000    0.000   23.849   23.849 {built-in method builtins.exec}
        9    0.000    0.000    0.000    0.000 {built-in method builtins.id}
       27    0.000    0.000    0.000    0.000 {built-in method builtins.issubclass}
      171    0.000    0.000    0.000    0.000 {built-in method builtins.len}
        9    0.000    0.000    0.000    0.000 {built-in method builtins.locals}
  1284614    0.290    0.000    0.290    0.000 {built-in method builtins.max}
      287    0.006    0.000    0.006    0.000 {built-in method builtins.print}
        9    0.000    0.000    0.000    0.000 {built-in method numpy.array}
       18    0.000    0.000    0.000    0.000 {built-in method numpy.core._multiarray_umath.implement_array_function}
        9    0.000    0.000    0.000    0.000 {built-in method time.time}
  1260442    0.135    0.000    0.135    0.000 {method 'add' of 'set' objects}
        8    0.000    0.000    0.000    0.000 {method 'append' of 'list' objects}
        9    0.000    0.000    0.000    0.000 {method 'copy' of 'dict' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        9    0.000    0.000    0.000    0.000 {method 'discard' of 'set' objects}
        9    0.000    0.000    0.000    0.000 {method 'format' of 'str' objects}
       27    0.000    0.000    0.000    0.000 {method 'items' of 'dict' objects}
    82658    0.011    0.000    0.011    0.000 {method 'keys' of 'dict' objects}
       18    0.000    0.000    0.000    0.000 {method 'reduce' of 'numpy.ufunc' objects}
        9    0.000    0.000    0.000    0.000 {method 'rstrip' of 'str' objects}
    20840    0.011    0.000    0.011    0.000 {method 'update' of 'dict' objects}
    20814    0.003    0.000    0.003    0.000 {method 'values' of 'dict' objects}

Now it’s 3.9 out of 23.8 seconds

4-ply vs PloddingPlayer

Without the improvement to get_nearby_man_moves, it took 4314 seconds to do 21 moves.

['H11', 'I11', 'E ', 'J9', 'H13', 'SW ', 'J11', 'W ', 'J9', 'K11', 'E ', 'K12', 'E ', 'K9', 'J13', 'SW NW ', 'J9', 'K9', 'E ', 'L7', 'J11']

With that improvement (and during a Zoom call), it took 2002 seconds

['H11', 'I11', 'E ', 'J9', 'H13', 'SW ', 'J11', 'W ', 'J9', 'K11', 'E ', 'K12', 'E ', 'K9', 'J13', 'SW NW ', 'J9', 'K9', 'E ', 'L7', 'J11']

Moves 22 and 23 happened at 3179 seconds, which was a long delay. I didn’t think this was a complicated position:

['H11', 'I11', 'E ', 'J9', 'H13', 'SW ', 'J11', 'W ', 'J9', 'K11', 'E ', 'K12', 'E ', 'K9', 'J13', 'SW NW ', 'J9', 'K9', 'E ', 'L7', 'J11']
Duration of game so far is 2002.8510048389435 seconds
          1111111111
 1234567890123456789
A+++++++++++++++++++
B+++++++++++++++++++
C+++++++++++++++++++
D+++++++++++++++++++
E+++++++++++++++++++
F+++++++++++++++++++
G+++++++++++++++++++
H++++++++++++○++++++
I+++++++++++++++++++
J+++++++++●○+○++++++
K++++++++○++○+++++++
L++++++○++++++++++++
M+++++++++++++++++++
N+++++++++++++++++++
O+++++++++++++++++++
Side to move: Right
Moves made: 21
Ball at: [9 9]

Maybe it was the Zoom call.

Move 24 at 4013 seconds. Move 26 at 4238 seconds. Move 28 at 4737 seconds.

Now it’s move 39 after 8754 seconds.

['H11', 'I11', 'E ', 'J9', 'H13', 'SW ', 'J11', 'W ', 'J9', 'K11', 'E ', 'K12', 'E ', 'K9', 'J13', 'SW NW ', 'J9', 'K9', 'E ', 'L7', 'J11', 'SW ', 'L9', 'W ', 'L7', 'M9', 'E ', 'M10', 'E ', 'M7', 'L11', 'SW NW ', 'L7', 'M7', 'E ', 'N5', 'L9', 'SW ', 'N7']
Duration of game so far is 8754.058206796646 seconds
          1111111111
 1234567890123456789
A+++++++++++++++++++
B+++++++++++++++++++
C+++++++++++++++++++
D+++++++++++++++++++
E+++++++++++++++++++
F+++++++++++++++++++
G+++++++++++++++++++
H++++++++++++○++++++
I+++++++++++++++++++
J++++++++++○+○++++++
K+++++++++++○+++++++
L++++++++○+○++++++++
M+++++++++○+++++++++
N++++○●○++++++++++++
O+++++++++++++++++++
Side to move: Right
Moves made: 39
Ball at: [13  5]

8754/19 moves (because only half of them are 4-ply) is 460 seconds per move. That’s a little too slow. I admit that 4-ply doesn’t lose to PloddingPlayer, but it doesn’t show any genius in beating it either.

Meanwhile, 3-ply is making one move every 15 seconds (on average); see next section.

['H11', 'I11', 'E ', 'J9', 'H13', 'SW ', 'J11', 'W ', 'J9', 'K11', 'E ', 'K12', 'E ', 'K9', 'J13', 'SW NW ', 'J9', 'K9', 'E ', 'L7', 'J11', 'SW ', 'L9', 'W ', 'L7', 'M9', 'E ', 'M10', 'E ', 'M7', 'L11', 'SW NW ', 'L7', 'M7', 'E ', 'N5', 'L9', 'SW ', 'N7', 'W ', 'N5', 'N3', 'E ', 'M6', 'E ', 'M7', 'N9', 'NW S ', 'N7', 'E E N W ', 'L9', 'I14', 'E ', 'I12', 'E ', 'J9', 'L13', 'N W ', 'J11', 'W ', 'J9', 'K9', 'E ', 'SW ', 'L9', 'M9', 'E ', 'N7', 'L11', 'SW ', 'N9', 'W ', 'N7', 'M8', 'E ', 'O11', 'E ', 'M9', 'N11', 'M13', 'E ', 'N11', 'N13', 'NE W W ', 'L11', 'M13', 'E ', 'L11', 'L13', 'SE W W NW ', 'L9', 'S ', 'N9', 'N7', 'E ', 'N9', 'N11', 'W ', 'N9', 'M13', 'E ', 'E NE W W ', 'L11', 'K12', 'E ', 'N E N W S ', 'J13', 'W ', 'J11', 'K13', 'E ', 'K14', 'E ', 'K11', 'J15', 'S NW SW ', 'L11', 'W ', 'L9', 'M11', 'E ', 'M12', 'E ', 'M9', 'L13', 'S NW SW ', 'N9', 'W ', 'N7', 'M9', 'E ', 'M10', 'E ']
Duration of game so far is 64686.82395482063 seconds
          1111111111
 1234567890123456789
A+++++++++++++++++++
B+++++++++++++++++++
C+++++++++++++++++++
D+++++++++++++++++++
E+++++++++++++++++++
F+++++++++++++++++++
G+++++++++++++++++++
H+++++++++++++++++++
I+++++++++++++++++++
J++++++++++++++○++++
K+++++++++++++++++++
L++++++++++++○++++++
M++++++++○○+++++++++
N++○++++++●+++++++++
O++++++++++○++++++++
Side to move: Right
Moves made: 133
Ball at: [13  9]

64686/66 is about 980 seconds per move. I’ve stopped it, since the players aren’t getting anywhere, although they aren’t oscillating

3-ply vs 3-ply, but faster now

main.run_game( (main.NegamaxABPlayer(depth = 3), main.NegamaxABPlayer(depth =3) ) )
104274 calls
['I11', 'K11', 'J12', 'K12', 'K13', 'L13', 'L14', 'M14', 'M15', 'N15', 'N14', 'K14', 'L15', 'N13', 'M11', 'L10', 'K10', 'K9', 'J9', 'J8', 'I8', 'I9', 'SE W NW E SW ', 'L7', 'N7', 'M6', 'N6', 'M7', 'N8', 'M8', 'N9', 'M9', 'N10', 'N5', 'O4', 'J7', 'I7', 'I6', 'H6', 'H5', 'G5', 'G4', 'F4', 'F3', 'E3', 'E2', 'NW ']
Duration of game so far is 711.1409401893616 seconds
          1111111111
 1234567890123456789
A+++++++++++++++++++
B+++++++++++++++++++
C+++++++++++++++++++
D●++++++++++++++++++
E++○++++++++++++++++
F+++○+++++++++++++++
G++++○++++++++++++++
H+++++○+++++++++++++
I++++++○++++++++++++
J+++++++++++++++++++
K+++++++++○○○+○+++++
L++++++○+++++○+○++++
M+++++○○○○++++○+++++
N++++○○○○○○+++++++++
O+++○+++++++++++++++
Side to move: Right
Moves made: 47
Ball at: [3 0]

Right has won

And it was running 4-ply vs PloddingPlayer at the same time, which might have made it slower. (Although I thought I had multiple cores?)

711/47 = 15 seconds per move

To do

Profile 3-ply (or 4-ply) when they’re working on a harder position, not just on the initial position

Does 4-ply get faster if we presort?

Neural network

25^6 is large enough?

https://www.tensorflow.org/tutorials/keras/classification

4-ply mistake

Starting here
A+++++++++++++++++++
B+++++++++++++++++++
C+++++++++++++++++++
D+++++++++++++++++++
E+++++++++++++++++++
F+++++++++++++++++++
G+++++++++++++++++++
H+++++++++++++++++++
I+++++++++++++++++++
J+++++++++●○+○++++++
K+++++++++++++++++++
L+++++++++++++++++++
M+++++++++++++++++++
N+++++++++++++++++++
O+++++++++++++++++++

I suspect 4-ply moves here:

A+++++++++++++++++++
B+++++++++++++++++++
C+++++++++++++++++++
D+++++++++++++++++++
E+++++++++++++++++++
F+++++++++++++++++++
G+++++++++++++++++++
H+++++++++++++++++++
I+++++++++++++++++++
J+++++++++++●○++++++
K+++++++++++++++++++
L+++++++++++++++++++
M+++++++++++++++++++
N+++++++++++++++++++
O+++++++++++++++++++

3-ply vs me

If I go first, I can exploit 3-ply’s fatal flaw and win.

Suppose I go second:

['I11', 'J11', 'J12', 'L12', 'K13', 'SE ', 'M15', 'K13', 'SE ', 'M15', 'J12', 'I11', 'I10', 'H10', 'H9', 'G9', 'G8', 'H8', 'G11', 'I8', 'K9', 'L9', 'L10', 'N15', 'W NE ', 'L15', 'J14', 'F8', 'E8', 'L8', 'F10', 'L13', 'W NW E SE ', 'G11', 'F11', 'H10', 'G13', 'H11', 'W SE S NE SE N NE ', 'I14', 'H12', 'I13', 'W N E ', 'G13', 'W W NE ', 'E11', 'W ', 'E9', 'W ', 'E7', 'W ', 'E5', 'W ', 'E3', 'W ', 'E1', 'W ']
Duration of game so far is 1276.214420080185 seconds
          1111111111
 1234567890123456789
A+++++++++++++++++++
B+++++++++++++++++++
C+++++++++++++++++++
D+++++++++++++++++++
E+++++++++++++++++++
F+++++++++++++++++++
G+++++++○+++++++++++
H+++++++++++++++++++
I+++++++++○+++++++++
J++++++++++○++++++++
K+++++++++++++++++++
L+++++++○+++++++++++
M+++++++++++++++++++
N+++++++++++++++++++
O+++++++++++++++++++
Side to move: Right
Moves made: 57
Ball at: [ 4 -1]

Right has won

I struggled a bit. 3-ply is better than me at seeing where multijump combinations go, although maybe I would improve with a physical board. I tried to put as many pieces to my left as possible. Eventually I was able to exploit 3-ply’s fatal flaw.

One more time:

['I11', 'G9', 'SE ', 'I11', 'F9', 'J11', 'W NE ', 'H11', 'F11', 'H10', 'F10', 'H9', 'F12', 'H8', 'I8', 'H7', 'I7', 'H6', 'I6', 'H5', 'I5', 'H4', 'I4', 'H3', 'I3', 'H2', 'W ']
Duration of game so far is 202.07085180282593 seconds
          1111111111
 1234567890123456789
A+++++++++++++++++++
B+++++++++++++++++++
C+++++++++++++++++++
D+++++++++++++++++++
E+++++++++++++++++++
F++++++++○○○○+++++++
G++++++++○++++++++++
H●++++++++++++++++++
I++○○○○○○+++++++++++
J+++++++++++++++++++
K+++++++++++++++++++
L+++++++++++++++++++
M+++++++++++++++++++
N+++++++++++++++++++
O+++++++++++++++++++
Side to move: Right
Moves made: 27
Ball at: [7 0]

Right has won

I managed to grab the initiative faster and build a long straight chain.

3-ply vs 4-ply

main.run_game( ( main.NegamaxABPlayer(depth =4), main.NegamaxABPlayer(depth = 3) ) )

Result:

['H11', 'E ', 'H13', 'E ', 'H15', 'E ', 'H17', 'E ', 'G19', 'NE ']
Duration of game so far is 22.531296014785767 seconds
          1111111111
 1234567890123456789
A+++++++++++++++++++
B+++++++++++++++++++
C+++++++++++++++++++
D+++++++++++++++++++
E+++++++++++++++++++
F+++++++++++++++++++
G+++++++++++++++++++
H+++++++++++++++++++
I+++++++++++++++++++
J+++++++++++++++++++
K+++++++++++++++++++
L+++++++++++++++++++
M+++++++++++++++++++
N+++++++++++++++++++
O+++++++++++++++++++
Side to move: Left
Moves made: 10
Ball at: [ 5 19]

Left has won

3-ply’s fatal flaw

OK, try the other way

main.run_game( ( main.NegamaxABPlayer(depth =3), main.NegamaxABPlayer(depth = 4) ) )

Without A-B, it takes 173 seconds to make 5 moves. (i.e. 3 with 3-ply and 2 with 4-ply) With A-B, it takes 39 seconds (33.9 if no other program running)

But 3-ply’s fatal flaw does it in again.

['I11', 'I9', 'SE ', 'J11', 'H9', 'H8', 'G8', 'I8', 'W NW E S W ', 'I6', 'W ', 'I4', 'W ', 'H2', 'NW ']
Duration of game so far is 462.3921060562134 seconds
          1111111111
 1234567890123456789
A+++++++++++++++++++
B+++++++++++++++++++
C+++++++++++++++++++
D+++++++++++++++++++
E+++++++++++++++++++
F+++++++++++++++++++
G●++++++++++++++++++
H+++++++++++++++++++
I+++++++++++++++++++
J+++++++++++++++++++
K+++++++++++++++++++
L+++++++++++++++++++
M+++++++++++++++++++
N+++++++++++++++++++
O+++++++++++++++++++
Side to move: Right
Moves made: 15
Ball at: [6 0]

3-ply vs 1-ply

main.run_game( ( main.NegamaxABPlayer(depth =3), main.NegamaxABPlayer(depth = 1) ) )
['I11', 'K13', 'M15', 'O17', 'SE SE SE ', 'O19', 'N17', 'N19', 'L14', 'M19', 'J12', 'O16', 'H10', 'O15', 'F8', 'O13', 'D6', 'O12', 'B4', 'O11', 'A2', 'O10', 'A1', 'O9', 'A3', 'O8', 'B1', 'N11', 'B2', 'O7', 'B3', 'O6', 'C1', 'O5', 'C2', 'N8', 'C3', 'O4', 'A4', 'O3', 'C4', 'O2', 'A5', 'N5', 'B5', 'O1', 'C5', 'N2', 'A6', 'O14', 'B6', 'M11', 'C6', 'M8', 'A7', 'M5', 'B7', 'N1', 'C7', 'M2', 'A8', 'O18', 'B8', 'N18', 'C8', 'M18', 'A9', 'M17', 'B9', 'L19', 'C9', 'N10', 'A10', 'N9', 'B10', 'M10', 'C10', 'M9', 'A11', 'L9', 'B11', 'N6', 'C11', 'M6', 'A12', 'L6', 'B12', 'N3', 'C12', 'M3', 'A13', 'M1', 'B13', 'L3', 'C13', 'L18', 'A14', 'L17', 'B14', 'K19', 'C14', 'N15', 'E ']
Duration of game so far is 66.30910515785217 seconds
          1111111111
 1234567890123456789
A○○○○○○○○○○○○○○+++++
B○○○○○○○○○○○○○○+++++
C○○○○○○○○○○○○○○+++++
D+++++○+++++++++++++
E+++++++++++++++++++
F+++++++○+++++++++++
G+++++++++++++++++++
H+++++++++○+++++++++
I+++++++++++++++++++
J+++++++++++○+++++++
K++++++++++++++++++○
L++○++○++○++++○++○○○
M○○○+○○+○○○○+++++○○○
N○○○+○○+○○○○+++○++++
O○○○○○○○○○○○○○○○○○○○
Side to move: Right
Moves made: 103
Ball at: [13 19]

Left has won

Once 3-ply sees that it has a win in 1 move, it realizes that any of its moves give it a win in 3, so it doesn’t pick the move that gives it a win in 1. Eventually the board gets so clogged that it has to move in order to win.

Probably I should fix this, i.e. make it prefer a win in 1 move over a win in 3. But it doesn’t seem like a big problem right now, unless there are positions in which it would repeat forever.

The same thing happens the other way:

main.run_game( ( main.NegamaxABPlayer(depth =1), main.NegamaxABPlayer(depth = 3) ) )
['J12', 'I9', 'L14', 'K7', 'N16', 'M5', 'O18', 'N3', 'O19', 'N2', 'N19', 'F8', 'M19', 'D6', 'O16', 'B4', 'O15', 'A2', 'O13', 'A1', 'O12', 'A3', 'O11', 'B1', 'O10', 'B2', 'O9', 'B3', 'O8', 'C1', 'N11', 'C2', 'N8', 'C3', 'O14', 'A4', 'M11', 'C4', 'O2', 'A5', 'O1', 'B5', 'N1', 'C5', 'M2', 'A6', 'O17', 'B6', 'N18', 'C6', 'N17', 'A7', 'M18', 'B7', 'M17', 'C7', 'L19', 'A8', 'N10', 'B8', 'N9', 'C8', 'M10', 'A9', 'O7', 'B9', 'O6', 'C9', 'O5', 'A10', 'N7', 'B10', 'N6', 'C10', 'N5', 'SW SW SW W ']
Duration of game so far is 113.03985595703125 seconds
          1111111111
 1234567890123456789
A○○○○○○○○○○+++++++++
B○○○○○○○○○○+++++++++
C○○○○○○○○○○+++++++++
D+++++○+++++++++++++
E+++++++++++++++++++
F+++++++○+++++++++++
G+++++++++++++++++++
H+++++++++++++++++++
I+++++++++++++++++++
J+++++++++++○+++++++
K+++++++++++++++++++
L+++++++++++++○++++○
M+○+++++++○○+++++○○○
N++++○○○○○○○++++○○○○
O○○++○○○○○○○○○○○○○○○
Side to move: Left
Moves made: 76
Ball at: [13 -1]

Right has won

2-ply vs 3-ply

main.run_game( ( main.NegamaxABPlayer(depth =2), main.NegamaxABPlayer(depth = 3) ) )
['J12', 'I9', 'SW ', 'K7', 'SW ', 'M5', 'SW ', 'N3', 'W ', 'M1', 'NW ']
Duration of game so far is 6.175920248031616 seconds
          1111111111
 1234567890123456789
A+++++++++++++++++++
B+++++++++++++++++++
C+++++++++++++++++++
D+++++++++++++++++++
E+++++++++++++++++++
F+++++++++++++++++++
G+++++++++++++++++++
H+++++++++++++++++++
I+++++++++++++++++++
J+++++++++++○+++++++
K+++++++++++++++++++
L+++++++++++++++++++
M+++++++++++++++++++
N+++++++++++++++++++
O+++++++++++++++++++
Side to move: Right
Moves made: 11
Ball at: [11 -1]

Right has won

Seems like 2-ply was helping it along

main.run_game( ( main.NegamaxABPlayer(depth =3), main.NegamaxABPlayer(depth = 2) ) )
['I11', 'SE ', 'K13', 'SE ', 'M15', 'SE ', 'N17', 'E ', 'M19', 'NE ']
Duration of game so far is 1.4620428085327148 seconds
          1111111111
 1234567890123456789
A+++++++++++++++++++
B+++++++++++++++++++
C+++++++++++++++++++
D+++++++++++++++++++
E+++++++++++++++++++
F+++++++++++++++++++
G+++++++++++++++++++
H+++++++++++++++++++
I+++++++++++++++++++
J+++++++++++++++++++
K+++++++++++++++++++
L+++++++++++++++++++
M+++++++++++++++++++
N+++++++++++++++++++
O+++++++++++++++++++
Side to move: Left
Moves made: 10
Ball at: [11 19]

Left has won

2-ply vs 1-ply

main.run_game( ( main.NegamaxABPlayer(depth =2), main.NegamaxABPlayer(depth = 1) ) )
['J12', 'L14', 'N16', 'O18', 'O19', 'N19', 'M19', 'O16', 'O15', 'O13', 'O12', 'O11', 'O10', 'O9', 'O8', 'N11', 'O7', 'O6', 'O5', 'N8', 'O4', 'O3', 'O2', 'N5', 'O1', 'N2', 'O14', 'M11', 'M8', 'M5', 'N1', 'M2', 'O17', 'N18', 'N17', 'M18', 'M17', 'L19', 'N10', 'N9', 'M10', 'M9', 'L9', 'N6', 'M6', 'L6', 'N3', 'M3', 'M1', 'L3', 'L18', 'L17', 'K19', 'N15', 'N14', 'N13', 'N12', 'M16', 'M15', 'M14', 'M13', 'M12', 'L16', 'L15', 'K16', 'K9', 'N7', 'K6', 'N4', 'L2', 'L1', 'K3', 'J19', 'K15', 'J16', 'M7', 'L8', 'L7', 'K8', 'K7', 'J7', 'M4', 'L4', 'K4', 'K2', 'K1', 'J4', 'J1', 'I19', 'J15', 'I16', 'L13', 'L12', 'L11', 'L10', 'K13', 'K12', 'K11', 'K10', 'J13', 'I13', 'I7', 'L5', 'I4', 'I1', 'H19', 'K18', 'K17', 'H16', 'K14', 'H13', 'H7', 'K5', 'H4', 'H1', 'G19', 'J18', 'J17', 'G16', 'J14', 'G13', 'J11', 'J10', 'I10', 'G10', 'N ', 'J9', 'J8', 'I9', 'I8', 'G7', 'J6', 'J5', 'G4', 'J3', 'J2', 'G1', 'F19', 'I18', 'I17', 'F16', 'I15', 'I14', 'I12', 'I11', 'F13', 'F7', 'I6', 'I5', 'F4', 'I3', 'I2', 'F1', 'E19', 'H18', 'H17', 'E16', 'H15', 'H14', 'E13', 'H12', 'H11', 'H10', 'G10', 'E10', 'N ', 'H9', 'H8', 'G9', 'G8', 'E7', 'H6', 'H5', 'E4', 'H3', 'H2', 'E1', 'D19', 'G18', 'G17', 'D16', 'G15', 'G14', 'G12', 'G11', 'D13', 'D7', 'G6', 'G5', 'D4', 'G3', 'G2', 'D1', 'C19', 'F18', 'F17', 'C16', 'F15', 'F14', 'C13', 'F12', 'F11', 'F10', 'E10', 'C10', 'N ', 'F9', 'F8', 'E9', 'E8', 'C7', 'F6', 'F5', 'C4', 'F3', 'F2', 'C1', 'B19', 'E18', 'E17', 'B16', 'E15', 'E14', 'E12', 'E11', 'B13', 'B7', 'E6', 'E5', 'B4', 'E3', 'E2', 'B1', 'A19', 'D18', 'D17', 'A16', 'D15', 'D14', 'A13', 'D12', 'D11', 'D10', 'C10', 'A10', 'D9', 'D8', 'A7', 'D6', 'D5', 'A4', 'D3', 'D2', 'A1', 'C18', 'C17', 'B18', 'B17', 'A18', 'A17', 'C15', 'C14', 'B15', 'B14', 'A15', 'A14', 'C12', 'C11', 'SE ']
Duration of game so far is 19.230502128601074 seconds
          1111111111
 1234567890123456789
A○++○++○++○++○○○○○○○
B○++○++○+++++○○○○○○○
C○++○++○++○+○○○○○○○○
D○○○○○○○○○○○+○○○○○○○
E○○○○○○○○○○○○+○○○○○○
F○○○○○○○○○○○○○+○○○○○
G○○○○○○○○○○○○○○+○○○○
H○○○○○○○○○○○○○○○+○○○
I○○○○○○○○○○○○○○○○+○○
J○○○○○○○○○○○○○○○○○+○
K○○○○○○○○○○○○○○○○○○+
L○○○○○○○○○○○○○○○○○○○
M○○○○○○○○○○○○○○○○○○○
N○○○○○○○○○○○○○○○○○○○
O○○○○○○○○○○○○○○○○○○○
Side to move: Right
Moves made: 269
Ball at: [11 19]

Left has won

Uh, that was weird.

main.run_game( ( main.NegamaxABPlayer(depth =1), main.NegamaxABPlayer(depth = 2) ) )
['J12', 'L14', 'N16', 'O18', 'O19', 'N19', 'M19', 'O16', 'O15', 'O13', 'O12', 'O11', 'O10', 'O9', 'O8', 'N11', 'O7', 'O6', 'O5', 'N8', 'O4', 'O3', 'O2', 'N5', 'O1', 'N2', 'O14', 'M11', 'M8', 'M5', 'N1', 'M2', 'O17', 'N18', 'N17', 'M18', 'M17', 'L19', 'N10', 'N9', 'M10', 'M9', 'L9', 'N6', 'M6', 'L6', 'N3', 'M3', 'M1', 'L3', 'L18', 'L17', 'K19', 'N15', 'N14', 'N13', 'N12', 'M16', 'M15', 'M14', 'M13', 'M12', 'L16', 'L15', 'K16', 'K9', 'N7', 'K6', 'N4', 'L2', 'L1', 'K3', 'J19', 'K15', 'J16', 'M7', 'L8', 'L7', 'K8', 'K7', 'J7', 'M4', 'L4', 'K4', 'K2', 'K1', 'J4', 'J1', 'I19', 'J15', 'I16', 'L13', 'L12', 'L11', 'L10', 'K13', 'K12', 'K11', 'K10', 'J13', 'I13', 'I7', 'L5', 'I4', 'I1', 'H19', 'K18', 'K17', 'H16', 'K14', 'H13', 'H7', 'K5', 'H4', 'H1', 'G19', 'J18', 'J17', 'G16', 'J14', 'G13', 'J11', 'J10', 'I10', 'G10', 'N ', 'J9', 'J8', 'I9', 'I8', 'G7', 'J6', 'J5', 'G4', 'J3', 'J2', 'G1', 'F19', 'I18', 'I17', 'F16', 'I15', 'I14', 'I12', 'I11', 'F13', 'F7', 'I6', 'I5', 'F4', 'I3', 'I2', 'F1', 'E19', 'H18', 'H17', 'E16', 'H15', 'H14', 'E13', 'H12', 'H11', 'H10', 'G10', 'E10', 'N ', 'H9', 'H8', 'G9', 'G8', 'E7', 'H6', 'H5', 'E4', 'H3', 'H2', 'E1', 'D19', 'G18', 'G17', 'D16', 'G15', 'G14', 'G12', 'G11', 'D13', 'D7', 'G6', 'G5', 'D4', 'G3', 'G2', 'D1', 'C19', 'F18', 'F17', 'C16', 'F15', 'F14', 'C13', 'F12', 'F11', 'F10', 'E10', 'C10', 'N ', 'F9', 'F8', 'E9', 'E8', 'C7', 'F6', 'F5', 'C4', 'F3', 'F2', 'C1', 'B19', 'E18', 'E17', 'B16', 'E15', 'E14', 'E12', 'E11', 'B13', 'B7', 'E6', 'E5', 'B4', 'E3', 'E2', 'B1', 'A19', 'D18', 'D17', 'A16', 'D15', 'D14', 'A13', 'D12', 'D11', 'D10', 'C10', 'A10', 'D9', 'D8', 'A7', 'D6', 'D5', 'A4', 'D3', 'D2', 'A1', 'C18', 'C17', 'B18', 'B17', 'A18', 'A17', 'C15', 'C14', 'B15', 'B14', 'A15', 'A14', 'C12', 'B12', 'C11', 'SE ']
Duration of game so far is 19.5760760307312 seconds
          1111111111
 1234567890123456789
A○++○++○++○++○○○○○○○
B○++○++○++++○○○○○○○○
C○++○++○++○+○○○○○○○○
D○○○○○○○○○○○+○○○○○○○
E○○○○○○○○○○○○+○○○○○○
F○○○○○○○○○○○○○+○○○○○
G○○○○○○○○○○○○○○+○○○○
H○○○○○○○○○○○○○○○+○○○
I○○○○○○○○○○○○○○○○+○○
J○○○○○○○○○○○○○○○○○+○
K○○○○○○○○○○○○○○○○○○+
L○○○○○○○○○○○○○○○○○○○
M○○○○○○○○○○○○○○○○○○○
N○○○○○○○○○○○○○○○○○○○
O○○○○○○○○○○○○○○○○○○○
Side to move: Left
Moves made: 270
Ball at: [11 19]

Left has won

Ditto