how to solve it

everyone should know the work of George Pólya on how to solve problems

  • Marvin Minsky (in Steps Toward Artificial Intelligence)

wiki

example: how to solve 4x4 dark hex?

  • solve a simpler problem ?

simple dark hex

  • restriction of dark hex

    • first stone must touch own edge

    • each subsequent stone must touch own previous stone

    • must reach other side within 4 moves

    • can we solve this ?

notation: label SDH strategies by 1st move
*p1   * * * *        p1              p2
       ~ ~ ~ ~    D+ C+ B+ A+    d-      a+
        ~ ~ ~ ~                   c-      b+
         ~ ~ ~ ~                   b-      c+
          ~ ~ ~ ~    A- B- C- D-    a-      d+
           * * * *
p1 minimax win probability matrix ?
     a- b- c- d-  a+ b+ c+ d+
 A-  ?  1  ?  ?   ?  1  1  1      D+ C+ B+ A+
 B-                                c-       b+
 C-                                 b-       c+
 D-                                  A- B- C- D-
 A+
 B+
 C+
 D+

what should we assume if player sees opponent stone?
  minimax ?  equiprobable ?
eg: A-a- .5 if p2 plays minimax = equiprob. {d-,a+}
eg: A-d- .25 if p2 moves 2,3 uniform {left/right}
expanding matrix entries
A-- move 2 towards opponent -
A-+   "  "    "       "     +

     a- c-  d-  a+-  a++
A--  ?  0   0    1   .5
A-+  ?  1  .5    1    0

so if p2 plays a- and sees a stone at A-,
then p2 minimax is equiprob {d-, a++}, 1p win rate .25