GetReachableNodes

[Dr-Steve]

If I have something like this:

BX _X _XX __X WXX XX

and I do a getReachableIndices on the white queen, it returns [40, 30, 20, 31](as it should). Now if I shoot space 30 and make the same query, I get [40]. It seems that the diagonal gets eaten. I believe that the checker that breaks the board into two partitions doesn't check diagonals, so it shows the partition the white queen is in as only having one space(40), thus it considers 31 as BLOCKED.

[searing]

You are correct. I will work on a fix now.

[searing]

I believe I fixed it.

I'm sorry for all the bugs. I will do more work on the test suite later this afternoon/evening when I have time. Hopefully there will not be so many bugs in the future.

[Dr-Steve]

No worries, Some of these bugs would have taken a hell of a test suite to find. Its probably just as efficient with me coming across them as I test my stuff.

[Dr-Steve]

Hmm getting a negative on this fix. I'll test it a bit more to see if its on my end, but are you sure this works?

[searing]

I've written a test for it now and I can confirm that it doesn't work. I'm still trying to fix it.

[searing]

The issue seems to be that it doesn't properly check the northeast corner. I will attempt to fix this.

[searing]

I've pushed changes that work with my (primitive) tests. Basically, if you write diagonally across the entire board, it does not split anymore.

[Dr-Steve]

Did you change something in the last hour? This worked when I left for class but now I got back, pulled, and it no longer works again

[Dr-Steve]

Still doesn't work. Here is a fun little board set up you can use to verify the bug:

//create a partition
NodeSet _refSet = new NodeSet();
Partition _p = _refSet.getRootPartition();

List<Partition> _lp1 = _p.forkNode(1, NodeState.BLOCKED);
Partition _p1 = _lp1.get(0);
List<Partition> _lp2 = _p1.forkNode(2, NodeState.BLOCKED);
Partition _p2 = _lp2.get(0);
List<Partition> _lp3 = _p2.forkNode(24, NodeState.BLOCKED);
Partition _p3 = _lp3.get(0);
List<Partition> _lp4 = _p3.forkMove(new ClientMove(3,0,2,1,1,1),true);
Partition _p4 = _lp4.get(0);
//List<Partition> _lp5 = _p4.forkMove(new ClientMove(6,0,4,0,4,1),false);
//Partition _p5 = _lp5.get(0);
List<Partition> _lp5 = _p4.forkNode(20, NodeState.BLOCKED);
Partition _p5 = _lp5.get(0);
List<Partition> _lp6 = _p5.forkNode(30, NodeState.BLOCKED);
Partition _p6 = _lp6.get(0);
List<Partition> _lp7 = _p6.forkNode(31, NodeState.BLOCKED);
Partition _p7 = _lp7.get(0);
List<Partition> _lp8 = _p7.forkNode(22, NodeState.BLOCKED);
Partition _p8 = _lp8.get(0);
List<Partition> _lp9 = _p8.forkNode(32, NodeState.BLOCKED);
Partition _p9 = _lp9.get(0);
List<Partition> _lp10 = _p9.forkNode(3, NodeState.BLOCKED);
Partition _p10 = _lp10.get(0);
List<Partition> _lp11 = _p10.forkNode(13, NodeState.BLOCKED);
Partition _p11 = _lp11.get(0);
List<Partition> _lp12 = _p11.forkNode(23, NodeState.BLOCKED);
Partition _p12 = _lp12.get(0);

If you ask for black's moves, it seems to return that it can only move to 1,0. Then if you take that move and shoot 0,0 then it says that the black queen has no moves.

[Dr-Steve]

Here is a printout for the board so you can see it a little better. Does Git handle unicode?

   0 1 2 3 4 5 6 7 8 9
  ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
 0│ │X│X│X│ │ │B│ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
 1│ │X│ │X│ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
 2│X│B│X│X│X│ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
 3│X│X│X│ │ │ │ │ │ │B│
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
 4│ │ │ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
 5│ │ │ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
 6│W│ │ │ │ │ │ │ │ │W│
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
 7│ │ │ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
 8│ │ │ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
 9│ │ │ │W│ │ │W│ │ │ │

[searing]

Sorry about the delay on this - I was really into the search code (which is probably about half done, give or take). I'll look at this now.

[searing]

I'm still working on this issue, but I've noticed that it lets you fork nodes that don't belong to the partition you're forking from! This was clearly an oversight on my part ("why would anyone do that?), but I will add a check in anyways. After we get it to work, before we go live, I can remove it for performance.

Note: This check may break some code. Be comforted that the code in question never should have worked anyways.

I'll give more details and make an "issue" about it when I make the change.

[searing]

I've isolated the bug, but I don't have a fix yet. I'll keep working on it.

[searing]

The issue is in the detection of split partitions. If a sub-partition is adjacent to two other sub-partitions, a split occurs when no split should occur.

I will have to rework the algorithm to detect split partitions.

Edit: To clarify, this is an issue with the algorithm itself. It was never working "properly". I never considered this edge case.

[searing]

I fixed it. The new algorithm is not at all optimal (worst case is O(n^2), but I added another optimization that causes it to only check for split partitions if there are enough neighboring blocked nodes to cause a split. As a result, the runtime is down by about 20%.

[Dr-Steve]

Woooooo!!!!!!

[Dr-Steve]

Guess which bug is back from the dead? It seems we have a zombie bug. Try not to get bit, less the zombie virus mutates to affect humans.

I just pushed a new round of my alpha-beta search. Run it and you will see the problem. The black queen moves, then the white queen moves, then the rogue zombie bug prevents the black queen from seeing any moves, despite the obvious open square sitting to his right. Well, I suppose her right, as queens are generally female. But anyways if you check line 29 of said class, you can see that the black queen clearly thinks it is stuck, then observe in the printed board (through the spam of the null pointer errors) that it should be able to move.

[searing]

Oh my. I'd like to finish the search implementation tonight though (I'm about 70% done).

[searing]

Is this resolved?

[Dr-Steve]

I'm going to go with yes. The endpartition dfs is complete for partitions in which there is one queen. I believe that this wouldn't work if this bug was still around. I will now begin abstracting this to the case of multiple queens of the same color(shouldn't be too hard). Should I worry about black/white or should I always assume that we are white?

[searing]

Hmm, are you talking about filling? If so, then yes, we need to handle multiple queens, but you may always assume they are white.