Al Zimmermann: Reversing Nearness

[Herbert Kociemba]

Yes you are right. I now implemented your idea(thanks again for sharing it)and it runs correctly. The update of the precomputed sums is indeed $O(N)$ but the advantage of the algorithm is not as large in the range N<=30 as I expected. For N = 30 it is currently only about twice as fast as my old method. Maybe there are some ways for optimizations...

[dimkadimon]

12d3, большое спасибо за ваш метод. Он очень хороший. Я думаю с таким методом можно победить :)

[Herbert Kociemba]

jcmeyrignac в сообщении #1408933 писал(а):

Is it possible to find two different grids that have the same score ?

For almost all grids there is a different grid with the same score.
Take for example this normalized 6x6 grid with a raw score of 10016.
(AA, AB, BC, AD, DE, AF),
(BF, EE, AE, FC, EA, DC),
(BA, FB, DB, EC, BB, BE),
(EF, EB, AC, CA, FF, CD),
(DA, FE, DD, CC, CB, FA),
(FD, CE, CF, BD, ED, DF)

If (grid[i,j].x ,grid[i,j].y) describes the entry at position (i,j) the inverse grid is defined by
invgrid[grid[i, j].x, grid[i, j].y].x := i
invgrid[grid[i, j].x, grid[i, j].y].y := j
The inverse grid always has the same score as the original grid.

After normalization the inverse grid for the example is
(AA, AB, DC, AD, BC, AF),
(CA, CE, AC, FD, CF, BA),
(DD, EE, ED, DF, FB, FC),
(EA, CC, BF, EC, AE, FF),
(BE, DB, CD, FE, BB, DA),
(EF, CB, BD, FA, EB, DE)

Al could include the inversion process into the normalization procedure to get a case reduction by a factor of 2.

Why did I write "For almost all grids..."? A grid may be selfinverse (inverse grid = grid) or may have some antisymmetry (the inverse grid is a rotation/reflection/translation of the grid) in which case we get no new grid.

[Herbert Kociemba]

Herbert Kociemba в сообщении #1409931 писал(а):

After normalization the inverse grid for the example is
(AA, AB, DC, AD, BC, AF),
(CA, CE, AC, FD, CF, BA),
(DD, EE, ED, DF, FB, FC),
(EA, CC, BF, EC, AE, FF),
(BE, DB, CD, FE, BB, DA),
(EF, CB, BD, FA, EB, DE)

Sorry for some confusion, but the correct inverse is

(AA, AC, DD, AE, EB, FE),
(BA, EC, EE, CC, BD, BC),
(CD, CA, DE, FB, DC, DB),
(DA, DF, FD, CE, EF, AF),
(CB, FC, BF, EA, BB, BE),
(FA, AB, CF, FF, AD, ED)

The grid I posted erroneously is generated by

newgrid[grid[i, j].y, grid[i, j].x].x := j;
newgrid[grid[i, j].y, grid[i, j].x].y := i;

But his transformation also leaves the rawscore invariant.


You can combine the two operations (they commute) to get another variant which in its normalized form is

(AA, BA, CB, DA, ED, FA),
(DF, EC, FC, DB, DE, FD),
(AD, EF, DD, CC, BC, AF),
(FE, BE, CA, AC, FF, DC),
(AB, BF, BD, CE, BB, EB),
(FB, EE, EA, CF, AE, CD)


So there usually are at least 4 normalized boards, which have the same score.

[Herbert Kociemba]

Al's equivalence classes contain 8 N^2 grids based on rotation, reflection and shift of the grid. There are other nongeometrical transformation except inversion which preserve the raw score. You can do for example
newgrid[i, j].x := (grid[i, j].x + c1) mod N
newgrid[i, j].y := (grid[i, j].y + c2) mod N

for any 0<=c1,c2< N

if you think the coordinates not as letters but as numbers from 0.. N-1. This alone usually gives N^2 "new" normalized boards. Or in other words, if you include this operation an equivalence class woud have 8 N^4 grids.

[whitefox]

Herbert Kociemba в сообщении #1409970 писал(а):

Sorry for some confusion, but the correct inverse is

Имхо, вы исправили правильное значение на ошибочное. Из вашего определения:

Herbert Kociemba в сообщении #1409931 писал(а):

If (grid[i,j].x ,grid[i,j].y) describes the entry at position (i,j) the inverse grid is defined by
invgrid[grid[i, j].x, grid[i, j].y].x := i
invgrid[grid[i, j].x, grid[i, j].y].y := j
The inverse grid always has the same score as the original grid.

следует, что

grid[1, 2].x = 1
grid[1, 2].y = 2
invgrid[1, 2].x = 1
invgrid[1, 2].y = 2

поэтому invgrid[1, 2] = AB, а не AC.

[Herbert Kociemba]

whitefox в сообщении #1410144 писал(а):

Имхо, вы исправили правильное значение на ошибочное.

Sorry, but I disagree. The confusion results because Al defines the grid differently as usually. On his page you can see that the default grid is

AA BA CA......
AB BB CB......
AC BC CC.....

and not - as me and you are used to -

AA AB AC......
BA BB BC......
CA CB CC.....

I made the same mistake on my first try.

[whitefox]

Herbert Kociemba в сообщении #1410207 писал(а):

Sorry, but I disagree. The confusion results because Al defines the grid differently as usually. On his page you can see that the default grid is

Понятно. Довольно необычное решение, но я исходил из вашего определения.

-- 14 авг 2019, 12:50 --

Herbert Kociemba в сообщении #1410051 писал(а):

Al's equivalence classes contain 8 N^2 grids based on rotation, reflection and shift of the grid. There are other nongeometrical transformation except inversion which preserve the raw score. You can do for example
newgrid[i, j].x := (grid[i, j].x + c1) mod N
newgrid[i, j].y := (grid[i, j].y + c2) mod N

for any 0<=c1,c2< N

if you think the coordinates not as letters but as numbers from 0.. N-1. This alone usually gives N^2 "new" normalized boards. Or in other words, if you include this operation an equivalence class woud have 8 N^4 grids.

И, вообще, можно поступить следующим образом:

• каноническую форму исходной решётки включим в поколение 0;
• чтобы построить поколение $p+1$ для каждой решётки поколения $p$ найдем $8n^2$ эквивалентных решёток и инвертируем их, канонические формы этих решёток включаем в поколение $p+1$.

Для примера Herbert Kociemba, в поколение 0 входит 1 решётка, в поколение 1 — 288, и т.д.

[Herbert Kociemba]

whitefox в сообщении #1410297 писал(а):

Для примера Herbert Kociemba, в поколение 0 входит 1 решётка, в поколение 1 — 288, и т.д.

I do not believe that generation 1 contains 288 elements, I think it is only 72. From the original grid, the inverse of the original grid and the 36 coordinate shifts (0<=c1,c2<6) you get 72 grids which all are in different equivalence classes. I think thats all you can get. So I am quite sure that from your 288 grids always 4 grids fall into the same equivalence class. And generation 2 will not give any new grids at all.

[whitefox]

Herbert Kociemba в сообщении #1410331 писал(а):

I do not believe that generation 1 contains 288 elements, I think it is only 72.

Проверено, 288.

Собственно говоря, не важно какое определение инверсии использовать — первое или второе. В обоих случаях в первом поколении содержится до $8n^2$ канонических решёток. Во втором поколении тоже — до $8n^2$ канонических решёток. Объединением этих двух поколений всё и заканчивается. Всего таким способом можно получить до $128n^4$ решёток с одинаковой оценкой, из них до $16n^2$ канонических.

Для вашего примера получаем 576 канонических решёток. Список приведу попозже.

[Herbert Kociemba]

whitefox в сообщении #1410512 писал(а):

Herbert Kociemba в сообщении #1410331

wrote:
I do not believe that generation 1 contains 288 elements, I think it is only 72.
Проверено, 288.

Отлично. It's already the second time in this thread that I am too fast in not believing something. Thank you for the verification!

[whitefox]

Выкладываю обещанный список 576 существенно различных решёток. В архиве:

1. список 576 решёток;
2. отдельный список 288 решёток поколения 1;
3. счётная программа;
4. исходный код.

[Herbert Kociemba]

Thanks. I think I have now complete understood what happens. In the summary below all computations are mod N. Also to avoid confusion again we assume the default grid uses numbers from 0 ... N-1 and uses the order

00 10 20 ....
01 11 21 ....
02 12 22 ...

In 02, we call 0 the x-coordinate und 2 the y-coordinate,

We have three basic geometric grid transformations which do not change the raw score

1. shiftgrid (shift grid by vector (dx,xy)):
newgrid[i, j].x := grid[i + dx, j + dy].x 0 <= dx, dy <N
newgrid[i, j].y := grid[i + dx, j + dy].y

2. rotgrid (90° rotation about 00):
newgrid[i, j].x := grid[j, -i].x;
newgrid[i, j].y := grid[j, -i].y

3. flipgrid (reflection along diagonal)
newgrid[j, i].x := grid[i, j].x
newgrid[j, i].y := grid[i, j].y

From a given grid these three transformations generate 8*N^2 equivalent grids. This is the equivalence class AZ currently uses for canonicalization.

There is one basic nongeometric transformation which does not change the rawscore:

4. invgrid (inversion of the grid permutation):
newgrid[grid[i, j].x, grid[i, j].y].x := i
newgrid[grid[i, j].x, grid[i, j].y].y := j

Each of the 3 geometric transformations have duals, which do not shift, rotate or flip the grid but "shift", "rotate" or "flip" the coordinates. This also does not change the rawscore. We can generate them by conjugation with the inversion:

5.
shiftcoord = invgrid*shiftgrid*invgrid
newgrid[i, j].x := grid[i, j].x - dx 0 <= dx, dy <N
newgrid[i, j].y := grid[i, j].y - dy

6.
rotcoord = invgrid*rotgrid*invgrid
newgrid[i, j].x := -grid[i, j].y
newgrid[i, j].y := grid[i, j].x

7.
flipcoord = invgrid*flipgrid*invgrid
newgrid[i, j].x := grid[i, j].y
newgrid[i, j].y := grid[i, j].x

Now for a given grid, we can apply 8*N^2 geometric transformations to get 8*N^2 grids. Inverting these grids gives 16*N^2 grids in total. Applying the 8*N^2 coordinate transformations to each of the 16*N^2 grids gives the 128 N^4 grids.

[whitefox]

12d3 в сообщении #1409284 писал(а):

Итого, для подсчета оценки после обмена двух фишек нам потребуется $O(N)$ времени.

Ну хорошо, поменяем местами фишки в позициях $(i_0,j_0)$ и $(i_1,j_1)$, за время $O(N)$ вычислим новые оценки фишек в этих позициях $F'(i_0,j_0)$ и $F'(i_1,j_1)$. А что с остальными фишками? Ведь их оценки тоже изменятся, и если даже сложность вычисления такого изменения для одной фишки $O(1)$, самих фишек $O(N^2)$.

UPD: Вопрос снимается. Используя вашу технику действительно можно вычислять изменение оценки решётки за время $O(N)$.

[Herbert Kociemba]

whitefox в сообщении #1410713 писал(а):

А что с остальными фишками? Ведь их оценки тоже изменятся

The values of the other chips change but this does not matter until you remove one of these chips. And then you can recompute the value of the chip in $O(N)$.