Looks like your dp()
function recurses very deeply. Consider that a call to dp(3)
can evaluate all 65536 possible bitboards in sequence with your ^
, while with your &~
a call to dp(k)
will only evaluate bitboards numerically before k
. Notice that you're filling in mat
in order in main()
; if you only depend on bitboards numerically before k
, you won't recurse very deeply.
EDIT: As for fixing this problem, you might think of dynamic programming as being of shortest paths in a directed acyclic graph. The trouble is that you don't have an acyclic graph here. You're doing depth-first search to find shortest paths here, which doesn't...work. Try replacing it with something like breadth-first search or Dijkstra's algorithm.