zfind discussion

[wildmyron]

For some reason ntzfind requires some extra padding when doing knight searches:

These comments from Sokwe when the horizontal offset feature was originally introduced are still relevant. https://conwaylife.com/forums/viewtopic ... 891#p35891

It's not possible to see the other phases of the partial but at least one of them would take up the full width of 5 in the second search.

[May13]

When I tried to find a c/3 diagonal spaceship in B3678/S34678 (Day and Night), ntzfind gives it:

Code: Select all

$  ./ntzfind B3678/S34678 p3 k1 x1 w8
ntzfind 3.0 by "zdr", Matthias Merzenich, Aidan Pierce, and Tomas Rokicki, 24 February 2018
- ./ntzfind B3678/S34678 p3 k1 x1 w8
Rule: B3678/S34678
Period: 3
Offset: 1
Width:  8
Symmetry: asymmetric
Horizontal offset: 1
Phase 0 has width 7
Depth limit: 2000
Stop search if a ship is found.
Starting search

..o.....
oooo....
.o.oo...
.o..oo..
..ooo...
....o...
Length: 16
Spaceship found. (1)

Current depth: 2001
Calculations: 32183
CPU time: 0.046000 seconds
Search terminated: spaceship found.

But ntzfind refuses to return a spaceship in B3ai/S2ae3aijr4aiw:

Code: Select all

$  ./ntzfind B3ai/S2ae3aijr4aiw p3 k1 x1 w10
ntzfind 3.0 by "zdr", Matthias Merzenich, Aidan Pierce, and Tomas Rokicki, 24 February 2018
- ./ntzfind B3ai/S2ae3aijr4aiw p3 k1 x1 w10
Rule: B3ai/S2ae3aijr4aiw
Period: 3
Offset: 1
Width:  10
Symmetry: asymmetric
Horizontal offset: 1
Phase 0 has width 9
Depth limit: 2000
Stop search if a ship is found.
Starting search
.o....o...
Length: 2
Search complete: 0 spaceships found.
Calculations: 10803
CPU time: 0.078000 seconds

Though I have this spaceship:

Code: Select all

x = 4, y = 4, rule = B3ai/S2ae3aijr4aiw
3o$o2bo$obo$bo!
[[ TRACK -1/3 -1/3 ]]

Bug or feature?
I'm using Cygwin.

[Sokwe]

ntzfind refuses to return a spaceship in B3ai/S2ae3aijr4aiw...

Though I have this spaceship:

Code: Select all

x = 4, y = 4, rule = B3ai/S2ae3aijr4aiw
3o$o2bo$obo$bo!
[[ TRACK -1/3 -1/3 ]]

Bug or feature?
I'm using Cygwin.

It appears to be a bug of some sort. I believe the problem is in lookAhead(), because if I modify lookAhead() to always return true, then it finds that ship as well as others such as the following:

Code: Select all

x = 5, y = 16, rule = B3ai/S2ae3aijr4aiw
o$2o$b2o3$b3o$o2bo$bobo2$b2o$b3o$b3o2$2bo$2b2o$3b2o!

It's been long enough that I don't really remember how I implemented the horizontal shift, and I was never a fan of the feature in zfind, so I'm not really inclined to hunt this bug down at the moment.

[ihatecorderships]

Is there a precompiled windows version of it?

[yujh]

ntzfind-win-precompiled.rar

Not compiled by me

(82.05 KiB) Downloaded 124 times

Is there a precompiled windows version of it?

[lemon41625]

If I'm not wrong, zfind is able to search for knightships. Does anyone know how the gfind search space is modified in order to allow for these searches?

I was working on implementing oblique / diagonal searches for cfind (unfortunately oblique searches don't work yet), so I'm curious to see how this is implemented in zfind.

[LaundryPizza03]

If I'm not wrong, zfind is able to search for knightships. Does anyone know how the gfind search space is modified in order to allow for these searches?

I was working on implementing oblique / diagonal searches for cfind (unfortunately oblique searches don't work yet), so I'm curious to see how this is implemented in zfind.

zfind searches along the orthogonal direction for knightships. You can find this beginning at line 579 of ntzfind.cpp ("#ifdef KNIGHT"). Paul Tooke's gfind mod includes an implementation of the same, which was used to find the p5 knightship in B3578/S235.

[Sokwe]

If I'm not wrong, zfind is able to search for knightships. Does anyone know how the gfind search space is modified in order to allow for these searches?

I was working on implementing oblique / diagonal searches for cfind (unfortunately oblique searches don't work yet), so I'm curious to see how this is implemented in zfind.

It wasn't particularly clever. When your partial result contains rows A, B, and X, and you're searching for row C such that

Code: Select all

AAAA   evolves into
BBBB ---------------> XXXX
CCCC

just shift row X horizontally by one cell before searching for row C.

As discussed above, I made some mistake in implementing LookAhead() with the horizontal shift. Ultimately, zfind's width limitations meant that this feature was mostly useless anyway, so I removed it. Other programs like ikpx2, LSSS, LLSSS, and even gfind are better. As LaundryPizza03 mentioned above, you're probably better off looking at Paul Tooke's modification of gfind, rather than whatever I wrote for zfind. I think it's the same basic idea.