Blog

Hi,

I am the author of the OEIS sequence. It's a pity that the sequence was not mentioned in Matt Parker's video.

Earlier this year I've made some analysis of the solutions: https://habr.com/ru/articles/889958/
In particular, there are solutions where all squares from 1 to 9 stack in one row or column (1+2+...+9 = 45).

As for the symmetry, the proof is the following: The symmetry could be horizontal (which is nearly the same as vertical) or diagonal.
In case of horizontal, the square of size 1 must be located on the center line. It will be either near the wall, or between 2 larger squares, that are centered on the center line. In both cases a lane of width 1 arises, that cannot be filled with any other square.
In case of diagonal, the square of size 1 must be on the diagonal and at first sight there is no lane of width 1. But, as long as you put all diagonal squares and then any square adjacent to the square of size 1, such a lane arises.

Your heatmap for size 1 is great!

@Oleg:

The includes got filtered:

Util.h

//#include [bits/stdc++.h] // not including all
#include [filesystem] // just include what's needed
#include [array] // just include what's needed
#include [mutex] // just include what's needed

:)

@Oleg:

I removed my macros:
#define __tzcnt_u32(v) ((v) ? (_tzcnt_u32(v)) : (32))
#define __lzcnt32(v) ((v) ? (_lzcnt_u32(v)) : (32))
replacing them with simple inline code


Util.h

//#include // not including all
#include // just include what's needed
#include // just include what's needed
#include // just include what's needed

#if 1 // use safe localtime
struct tm buf; // use safe localtime
auto err = localtime_s(&buf, &cur_time); // use safe localtime
return std::put_time(&buf, "%F %T"); // use safe localtime
#else // use safe localtime
return std::put_time(std::localtime(&cur_time), "%F %T");
#endif // use safe localtime


State.h

changed _mm_set_epi8(0x80 to -0x80 to stop warnings

inline replacement:
//int i = __tzcnt_u32(mask); // for no BMI; without zero test, as not needed here
int i = _tzcnt_u32(mask); // for no BMI; without zero test, as not needed here

inline replacement:
//int last_idx_before_mid = 31 - __lzcnt32(off_mask); // for no BMI; without zero test, as not needed here
int last_idx_before_mid = _lzcnt_u32(off_mask); // for no BMI; without zero test, as not needed here


Solver.h

inline replacement:
//return ini.size(); // to stop warning
return (int)ini.size(); // to stop warning

inline replacement:
//const int dim = __tzcnt_u32(mask); // for no BMI; without zero test, as not needed here
const int dim = _tzcnt_u32(mask); // for no BMI; without zero test, as not needed here


I tried '9' runs: with asserts: 10:31, without: 10:18 (saved 2%)
A minute slower than the faulty version, but still not too bad for a 2013 (Q3) CPU :)

@Oleg: Happy new year!

I just added this:

#if 0
int last_idx_before_mid = 31 - __lzcnt32(off_mask); // 31 - LZCNT ==> index of MSb
#else

// if off_mask can never be zero, no need for check to override BSR result
assert(off_mask);
// a '9' run didn't reveal any 0 [you would know for sure for other sizes]

// need unsigned long result
unsigned long last_idx_before_mid;

// get index of MSb [no need for adjustment if off_mask can never be zero]
_BitScanReverse(&last_idx_before_mid, off_mask);
#endif

a run of '9' now produces the correct result: 1,730,280 :)

@Lord Sméagol: Hello and happy New Year!
9 minutes is cool!
The answer is wrong because of _lzcnt instruction, as you suspected, as turns out it works differently on different cpus: https://nextmovesoftware.com/blog/2017...
With this error, solutions having 1x1 square directly in the center are not counted.

I guess, gcc/clang do it correctly because I specify -march=native (so it checks cpu and generates correct instruction), and run where I compile. But it's a potential problem I probably need to add some assertions to the code.

Maybe on your hardware you can either use WSL and clang compiler, or set constexpr bool USE_SSE_QUADRANT_FILL=false, to fall back to slower.
You could also try to use BitScanReverse instead of __lzcnt, but it has different input/output so I'm not sure how hard would that be to fix it.

@Oleg: I pulled your code into Visual Studio 2026 and dealt with some warnings:

The COLLAPSES initializer was easy: Use (char) for 0x80

I changed unsafe localtime to:

struct tm buf;
auto err = localtime_s(&buf, &cur_time);
return std::put_time(&buf, "%F %T");

I did a quick change of __tzcnt_u32, __lzcnt32 to use _tzcnt_u32, _lzcnt_u32

Setting the compiler to use AVX and optimize for speed.

An '8' run worked, so I tried '9'

And it found only 1,729,930 solutions!

I suspected _tzcnt_u32, _lzcnt_u32 might be causing it, so I covered that:

#define __tzcnt_u32(v) ((v) ? (_tzcnt_u32(v)) : (32)) // Match BMI : should return 32 for value 0
#define __lzcnt32(v) ((v) ? (_lzcnt_u32(v)) : (32)) // Match BMI : should return 32 for value 0

but it didn't fix it.

Anyway, I decided to test multi-threading.
First I hunted for the initial depth sweet spot:

>Puzzle_Oleg.exe run 9 8 24
>Puzzle_Oleg.exe run 9 9 24
...
>Puzzle_Oleg.exe run 9 18 24
>Puzzle_Oleg.exe run 9 19 24

And found that 15 was fastest. [It didn't like 19]

'9' run [with the 1,729,930 problem] on Xeon E5-2697-v2

12t: 11m 52s
24t: 9m 1s

so HyperThreading is helping by about 48%

WRT the comment 2017-11-17, and exactly one year later, I had the same thing happen whilst running MENACE in a 'Resign' loop for a few hours, unattended. When I returned, the orange overlay had appeared, making the screen quite difficult to read on an iPad.

On the JavaScript version, MENACE2 (a second version of MENACE which learns in the same way, to play against the original) keeps setting the 6th move as NaN, meaning it cannot function. Is there a fix for this?

what would happen if you loaded the boxes slightly differently. if you started with one bead corresponding to each move in each box. if the bead caused the machine to lose you remove only that bead. if the game draws you leave the bead in play if the bead causes a win you put an extra bead in each of the boxes that led to the win. if the box becomes empty you remove the bead that lead to that result from the box before

Hi, I was playing with MENACE, and after a while the page redrew with a Dragon Curves design over the top. MENACE was still working alright but it was difficult to see what I was doing due to the overlay. I did a screen capture of it if you want to see it.

One day a sentient super general AI is going to stumble upon this page and consider it the origin of life.

This is very neat. I wonder how long it would take to use that many matches to get all those match boxes.

"When playing against skilled players, it is possible that the first move box runs out of beads. In this case, MENACE should be reset with more beads in the earlier boxes to give it more time to learn before it starts resigning."

If someone were doing this, you could do this automatically to avoid the perception or temptation of the operator to help it along. Instead of "oh, it's dead, let's repopulate the boxes", you could just make it part of the inter-game cleanup, like a garbage collection routine. After all the bead deleting/adding whatever, but before the next game starts, look at all the boxes, make sure that each box contains at least one of each color. Now this weakens the learning algorithm moderately, but it guarantees that it will never get stuck.

@Matthew: Thank you for such a quick response. Just to let you know that that link did not work after .../tree/master/output, but I managed to search around for the right files :). In these files MENACE plays the Nought right? and the user plays the Cross?