ConwayLife.com - A community for Conway's Game of Life and related cellular automata
Home  •  LifeWiki  •  Forums  •  Download Golly

apgsearch v4.0

For general discussion about Conway's Game of Life.

Re: apgsearch v4.0

Postby dvgrn » November 6th, 2018, 10:47 am

danny wrote:
calcyman wrote:Please immediately update to v4.62 -- it fixes a problem causing GoL objects to appear in other lifelike rules.

i left mine running at home...

Which version was the GoL-object-spewing bug introduced in? Is it something recent, since v4.52-ll1.62 let's say, or has it been around a while?
User avatar
dvgrn
Moderator
 
Posts: 4906
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: apgsearch v4.0

Postby calcyman » November 6th, 2018, 3:13 pm

dvgrn wrote:
danny wrote:
calcyman wrote:Please immediately update to v4.62 -- it fixes a problem causing GoL objects to appear in other lifelike rules.

i left mine running at home...

Which version was the GoL-object-spewing bug introduced in? Is it something recent, since v4.52-ll1.62 let's say, or has it been around a while?


Very recent: the bug was introduced in v4.58-ll2.0.15 and repaired in v4.62-ll2.0.16.
What do you do with ill crystallographers? Take them to the mono-clinic!
User avatar
calcyman
 
Posts: 1733
Joined: June 1st, 2009, 4:32 pm

Re: apgsearch v4.0

Postby calcyman » November 6th, 2018, 11:59 pm

A while ago, I wrote:In terms of further rule families, the next one I intend to implement is outer-totalistic rules up to range 5.


Higher-range outer-totalistic (HROT) rules are implemented as of v4.63 (in apgsearch) and ll2.0.17 (in lifelib).

The syntax is rXbXXX...XsXXX...X[z]

where the range can be either 2, 3, 4, or 5, and the 'b' and 's' must each be followed by exactly r(r+1) hexadecimal characters. For instance, the LtL rule r2b4t4s10t19 has the outer-totalistic rulestring r2b000008s03ff00, where:

  • 000008 = 0000 0000 0000 0000 0000 1000 because we have birth only on 4 neighbours, and the 4th-from-last bit is 1 (the others are 0).
  • 03ff00 = 0000 0011 1111 1111 0000 0000 because we have survival from 9 to 18 neighbours, and those bits are 1.

IMPORTANT: the middle cell is included in LtL (for consistency with Kellie Evans' original notation), but excluded in HROT (for consistency with the usual outer-totalistic B/S notation).

If you want survival on zero neighbours, stick a 'z' on the end of the rule. For instance, if we were allowed r1 (which we're not, because that pointlessly duplicates the outer-totalistic rulespace), then B3/S02456 would have the rulestring r1b04s3az:

  • 04 = 0000 0100 because we have birth only on 3 neighbours, and the 3rd-from-last bit is 1 (the others are 0).
  • 3a = 0011 1010 because we have survival on 2, 4, 5 and 6 neighbours.
  • z because we have survival on zero neighbours.

A maximum range of 5 is supported (in which case each of the birth and survival conditions have exactly 30 hex chars), because due to extremely technical reasons* the HROT code can't support neighbourhoods of area greater than 127.

* The easiest way to explain it is that PSHUFB allows me to index into a lookup table of at most 16 bytes, and I can (with some effort) use that as a 128-bit lookup table. I have separate 'birth' and 'survival' lookup tables, PSHUFB each of them, and combine the results using the result of PCMPEQB-ing the centre cell with zero. This extracts the relevant byte; to extract the specific bit, I PSHUFB a 'powers of 2' lookup table and take the bitwise AND with the vector of bytes.

Also, I haven't combined this with Generations yet (it's 3:58 am here and I want to have food and sleep soon!), but the changes to do so would be utterly trivial.
What do you do with ill crystallographers? Take them to the mono-clinic!
User avatar
calcyman
 
Posts: 1733
Joined: June 1st, 2009, 4:32 pm

Re: apgsearch v4.0

Postby cordership3 » November 7th, 2018, 10:57 pm

calcyman wrote:Thanks for noticing this. I've enabled the 'incubator' method of object separation for all non-B0 lifelike rules, and replaced the 'apg::pattern' with (a pair of!) 'apg::upattern's in linearlyse(). In Golly language, this corresponds to using QuickLife instead of HashLife. Now we get huge speed improvements, especially for rules with common linear growths:

Thank you for changing that, here are some preliminary results with the same rules as before (and actual rule standardization):

B368/S245: ~115 soups/s to 2000 soups/s
B3678/S34678: 7700-7800 soups/s to 11000 soups/s
B36/S23: 3-6 soups/sec to ~3? soups/s

Although there is a significant increase from before, this still doesn't compare to the v3.x speeds I reported earlier in the thread. Not that this is very bad-- it just shows that v3.x is still in fact (for me at least) not quite deprecated yet.
All hail WADUFI our king.
User avatar
cordership3
 
Posts: 103
Joined: August 23rd, 2016, 8:53 am
Location: haha long boy

Re: apgsearch v4.0

Postby Apple Bottom » November 8th, 2018, 10:45 am

calcyman wrote:Higher-range outer-totalistic (HROT) rules are implemented as of v4.63 (in apgsearch) and ll2.0.17 (in lifelib).


Very cool!

I'm seeing segfaults for these rules on Cygwin, however:

$ ./apgluxe-r2b000008s03ff00-C1.exe -L 1 -v 0 -s AppleBottomTestHaul -n 1000000000

Greetings, this is apgluxe v4.63-ll2.0.17, configured for r2b000008s03ff00/C1.

Lifelib version: ll2.0.17
Compiler version: 7.3.0
Python version: '2.7.14 (default, Oct 31 2017, 21:12:13)  [GCC 6.4.0]'

Using seed AppleBottomTestHaul
Running 1000000000 soups per haul:
Instruction set AVX1 detected
Chaotic-growth pattern detected: zz_LINEAR
r2b000008s03ff00/C1: 4287 soups completed (185.689 soups/second current, 185.689 overall).
r2b000008s03ff00/C1: 9357 soups completed (282.845 soups/second current, 228.153 overall).
Chaotic-growth pattern detected: zz_LINEAR
Failed to detect periodic behaviour!
r2b000008s03ff00/C1: 23680 soups completed (958.445 soups/second current, 423.190 overall).
Failed to detect periodic behaviour!
r2b000008s03ff00/C1: 55617 soups completed (3193.700 soups/second current, 843.244 overall).
Failed to detect periodic behaviour!
r2b000008s03ff00/C1: 68695 soups completed (892.757 soups/second current, 852.242 overall).
Chaotic-growth pattern detected: zz_LINEAR
r2b000008s03ff00/C1: 73203 soups completed (401.926 soups/second current, 797.236 overall).
Chaotic-growth pattern detected: zz_LINEAR
r2b000008s03ff00/C1: 85513 soups completed (873.855 soups/second current, 807.427 overall).
r2b000008s03ff00/C1: 128138 soups completed (3012.580 soups/second current, 1067.310 overall).
Failed to detect periodic behaviour!
r2b000008s03ff00/C1: 139141 soups completed (1048.005 soups/second current, 1065.757 overall).
r2b000008s03ff00/C1: 193617 soups completed (5447.600 soups/second current, 1377.508 overall).
Failed to detect periodic behaviour!
Chaotic-growth pattern detected: zz_REPLICATOR
r2b000008s03ff00/C1: 211899 soups completed (1336.306 soups/second current, 1373.853 overall).
Failed to detect periodic behaviour!
r2b000008s03ff00/C1: 240600 soups completed (2870.100 soups/second current, 1464.956 overall).
Failed to detect periodic behaviour!
r2b000008s03ff00/C1: 245135 soups completed (449.321 soups/second current, 1406.155 overall).
Chaotic-growth pattern detected: zz_LINEAR
r2b000008s03ff00/C1: 249600 soups completed (405.393 soups/second current, 1346.685 overall).
Chaotic-growth pattern detected: zz_REPLICATOR
r2b000008s03ff00/C1: 263282 soups completed (1368.200 soups/second current, 1347.786 overall).
Failed to detect periodic behaviour!
Pathological object detected!!!
r2b000008s03ff00/C1: 264282 soups completed (17.227 soups/second current, 1042.977 overall).
r2b000008s03ff00/C1: 299845 soups completed (3540.016 soups/second current, 1138.200 overall).
r2b000008s03ff00/C1: 338396 soups completed (3849.326 soups/second current, 1237.492 overall).
Segmentation fault (core dumped)
$


There's no actual core dump (this is Cygwin after all), but the stackdump file reveals that this is actually a stack overflow:

Exception: STATUS_STACK_OVERFLOW at rip=00100431735
rax=000000060E184880 rbx=00000000FFE06410 rcx=000000060E184880
rdx=0000000000000002 rsi=00000000FFE06418 rdi=6AAAAAAAAAAAAAAC
r8 =00000000FFE06410 r9 =00000000FFE06418 r10=0000000000000000
r11=0000000100454C50 r12=00000000FFFFC4F0 r13=00000000FFE04101
r14=0000000000000000 r15=0000000000000002
rbp=00000000FFE04150 rsp=00000000FFE03F90
program=[...]\apgluxe-r2b000008s03ff00-C1.exe, pid 13440, thread
cs=0033 ds=002B es=002B fs=0053 gs=002B ss=002B
Stack trace:
Frame        Function    Args
000FFE04150  00100431735 (00000000000, 00000000000, 00000000000, 00000000001)
000FFE04270  0010043165F (00000000000, 00000000000, 00000000000, 00000000001)
000FFE04390  0010043165F (00000000000, 00000000000, 00000000000, 00000000001)
000FFE044B0  0010043165F (00000000000, 00000000000, 6FFFBAB0010, 00000000001)
000FFE045D0  0010043165F (00000000000, 00000007000, 00000000000, 00000000001)
000FFE046F0  0010043165F (00000000000, 00000000000, 00000000000, 00000000001)
000FFE04810  0010043165F (00000000000, 00000000000, 00000000000, 00000000001)
000FFE04930  0010043165F (00000000000, 00000000000, 00000000000, 00000000001)
000FFE04A50  0010043165F (00000000000, 000004EEBD8, 001004317B1, 00000000001)
000FFE04B70  0010043165F (00000000000, 00000126824, 001004316C5, 00000000001)
000FFE04C90  0010043165F (00000000000, 00000321C5C, 001004316C5, 00000000001)
000FFE04DB0  0010043165F (000FFE050B0, 0000000000F, 001800BEE5C, 00000000001)
000FFE04ED0  0010043165F (00000000001, 00000000002, 000FFFFC4F0, 00000000001)
000FFE04FF0  0010043165F (000FFE06B54, 0060E14AF50, 0010042FB87, 00000000001)
000FFE05110  0010043165F (00000000000, 00000752E00, 00000000000, 00000000001)
000FFE05230  0010043165F (000000451E6, FFFFFFFFFFFFFFFF, 0010042C310, 00000000001)
End of stack trace (more stack frames may be present)


Looks like this is due to deep recursion, perhaps.
If you speak, your speech must be better than your silence would have been. — Arabian proverb

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!
User avatar
Apple Bottom
 
Posts: 978
Joined: July 27th, 2015, 2:06 pm

Re: apgsearch v4.0

Postby calcyman » November 8th, 2018, 8:32 pm

Thanks! It looks like it was trapped in an infinite recursion in pbbosc, which I've now fixed. This wasn't related to the new rules (the same thing happened in the LtL equivalent rule):

https://catagolue.appspot.com/hashsoup/C1/AppleBottomTestHaul348534/r2b4t4s10t19

I've also added multistate HROT rules.
What do you do with ill crystallographers? Take them to the mono-clinic!
User avatar
calcyman
 
Posts: 1733
Joined: June 1st, 2009, 4:32 pm

Previous

Return to General Discussion

Who is online

Users browsing this forum: No registered users and 3 guests