It identifies separate "chambers" within our remaining space by looking at articulation points.
Let's take the following example:
############### # # # # # c # ###c########### # c # # # # # # a # b # ###a######b#### # a b # # # # # # # # 1# ###############
Slightly simplified, there are three articulation points: a,
b, and c.
Only two are directly reachable (without first passing through
another articulation point), a and b.
The maxsteps function tries all directly reachable articulation points, using the expand function to calculate how many steps can be made from the current position to each destination.
Then it calls itself recursively: when point a is reached, there is only a single articulation point left: c. Hence, we must walk from a to c (and can expand that path!).
Once we reach a chamber with no articulation points, we try to fill that room, again using expand. As destination, I try several options: all directly adjacent fields, and the field farthest aways from me.
The function returns the number of steps that can be taken, assuming the path that the function was called with is chosen. So, when the recursive calls for choices a and b return, we see that choice a allows for a longer path.
Unlike in this example, chambers can form loops. That's why the maxsteps function keeps track of which articulation points have already been visited along a call sequence.
An important aspect of both the maxsteps and expand function are
upper limits. Let's assume, in our above example, the opponent has
at most 70 fields left in his isolation (determined using flood-fill).
If maxsteps finds we can walk to a using (expanded) 64 steps,
and is currently expanding the shortest path from a to c,
we only need 7 more steps to beat the opponent.
Hence, expansion can abort after expanding the path only a few times,
and maxsteps doesn't even need to enter the chamber after reaching
c!