Wyciąganie bitów z pojedynczym mnożeniem

Bardzo interesujące pytanie. Jestem gonging z moich dwóch centów, czyli to, że, jeśli uda Ci się przedstawić problemy jak ten w kategoriach logiki pierwszego rzędu nad teorią bitvector, następnie theorem provers są twoim przyjacielem, i potencjalnie może dostarczyć bardzo szybkie odpowiedzi na pytania. Powtórzmy zadany problem jako twierdzenie:

"istnieje kilka 64-bitowych stałych 'mask' i 'multiplicand' takich, że dla wszystkich 64-bitowych bitwektorów x, w wyrażeniu y = (x & Maska) * multiplicand, mamy, że y.63 == x.63, y.62 == x.55, y. 61 = = x. 47, itd."

Jeśli to zdanie jest w rzeczywistości twierdzeniem, to prawdą jest, że niektóre wartości stałych "mask" i "multiplicand" spełniają tę własność. Tak więc ujmijmy to w kategoriach czegoś, co może zrozumieć twierdzenie prover, a mianowicie wejście SMT-LIB 2:

(set-logic BV)

(declare-const mask         (_ BitVec 64))
(declare-const multiplicand (_ BitVec 64))

(assert
  (forall ((x (_ BitVec 64)))
    (let ((y (bvmul (bvand mask x) multiplicand)))
      (and
        (= ((_ extract 63 63) x) ((_ extract 63 63) y))
        (= ((_ extract 55 55) x) ((_ extract 62 62) y))
        (= ((_ extract 47 47) x) ((_ extract 61 61) y))
        (= ((_ extract 39 39) x) ((_ extract 60 60) y))
        (= ((_ extract 31 31) x) ((_ extract 59 59) y))
        (= ((_ extract 23 23) x) ((_ extract 58 58) y))
        (= ((_ extract 15 15) x) ((_ extract 57 57) y))
        (= ((_ extract  7  7) x) ((_ extract 56 56) y))
      )
    )
  )
)

(check-sat)
(get-model)

A teraz zapytajmy twierdzenie prover Z3, czy jest to twierdzenie:

z3.exe /m /smt2 ExtractBitsThroughAndWithMultiplication.smt2

Wynik jest następujący:

sat
(model
  (define-fun mask () (_ BitVec 64)
    #x8080808080808080)
  (define-fun multiplicand () (_ BitVec 64)
    #x0002040810204081)
)

Patrząc na to z bardziej ogólnej perspektywy, możemy postrzegać to jako przykład problemu syntezy programu pierwszego rzędu, który jest rodzącym się obszarem badań, na temat którego opublikowano kilka artykułów. Wyszukiwanie {[3] } powinno zacząć.

Każdy 1-bit w mnożniku jest używany do skopiowania jednego z bitów do jego poprawnej pozycji:

• 1 jest już w prawidłowej pozycji, więc pomnóż przez 0x0000000000000001.
• 2 musi być przesunięte o 7 bitów w lewo, więc mnożymy przez 0x0000000000000080 (bit 7 jest ustawiony).
• 3 musi być przesunięte o 14 bitów w lewo, więc mnożymy przez 0x0000000000000400 (Bit 14 jest ustawiony).
• i tak dalej do
• 8 muszą być przesunięte o 49 bitów w lewo, więc mnożymy by 0x0002000000000000 (bit 49 jest ustawiony).

Mnożnik jest sumą mnożników dla poszczególnych bitów.

Działa to tylko dlatego, że bity do zebrania nie są zbyt blisko siebie, więc mnożenie bitów, które nie należą do siebie w naszym schemacie, albo wychodzi poza 64 bit lub w dolnej części don't care.

Zauważ, że pozostałe bity w numerze oryginalnym muszą być 0. Można to osiągnąć poprzez maskowanie ich za pomocą operacji AND.

(nigdy wcześniej tego nie widziałem. Ta sztuczka jest świetna!)

Rozwiń trochę twierdzenie Florisa, że podczas ekstrakcji n bitów potrzebujesz n-1 przestrzeni między dowolnymi nie kolejnymi bitami:

Moja początkowa myśl (zobaczymy za chwilę, Jak to nie do końca działa) była taka, że możesz zrobić lepiej: jeśli chcesz wyodrębnić n bity, będziesz miał kolizję podczas wyodrębniania / przesuwania bitu i Jeśli masz kogoś (nie-kolejne z bitem i) w i-1 bitach poprzedzających lub n-i bitów kolejnych.

Podam kilka przykładów do zilustrowania:

...a..b...c... Działa (nikt w 2 bitach po a, bit przed i bit po b, i nikt nie jest w 2 bitach przed c):

  a00b000c
+ 0b000c00
+ 00c00000
= abc.....

...a.b....c... zawiedzie, Ponieważ {[15] } jest w 2 bitach po a (i zostaje wciągnięty w czyjeś miejsce, gdy przesuniemy a):

  a0b0000c
+ 0b0000c0
+ 00c00000
= abX.....

...a...b.c... nie powiedzie się, ponieważ b jest w 2 bitach poprzedzających c (i zostaje zepchnięty w czyjeś miejsce, gdy we shift c):

  a000b0c0
+ 0b0c0000
+ b0c00000
= Xbc.....

...a...bc...d... działa, ponieważ kolejne bity przesuwają się razem:

  a000bc000d
+ 0bc000d000
+ 000d000000
= abcd000000

Ale mamy problem. jeśli użyjemy n-i zamiast n-1, możemy mieć następujący scenariusz: co jeśli mamy kolizję poza częścią, na której nam zależy, coś, co zamaskujemy na końcu, ale czyje bity nośne kończą się ingerencją w ważny, niezamaskowany zakres? (i uwaga: wymóg n-1 upewnia się, że tak się nie stanie, upewniając się, że i-1 bity po naszym Nie maskowanym zakresie są jasne, gdy przesuniemy i th bit)

...a...b..c...d... potencjalna awaria na nośnikach, c jest w n-1 po b, ale spełnia n-i kryteria:

  a000b00c000d
+ 0b00c000d000
+ 00c000d00000
+ 000d00000000
= abcdX.......

Więc może wrócimy do tego wymogu "n-1 bitów przestrzeni"? ponieważ możemy zrobić lepiej :

...a....b..c...d.. nie powiodło się test "n-1 bitów przestrzeni", ale Działa dla naszej sztuczki wydobywania bitów:

+ a0000b00c000d00
+ 0b00c000d000000
+ 00c000d00000000
+ 000d00000000000
= abcd...0X......

Nie mogę wymyślić dobrego sposobu na scharakteryzuj te pola, które nie mają n-1 przestrzeni między ważnymi bitami, ale nadal będą działać dla naszej operacji. Jednak, ponieważ wiemy z wyprzedzeniem które bity nas interesują, możemy sprawdzić nasz filtr, aby upewnić się, że nie doświadczamy kolizji carry-bitowych: {]} W przeciwieństwie do innych systemów, nie można ich używać w systemach Windows, Mac OS X, Mac OS X, Mac OS X, Mac OS X, Mac OS X, Mac OS X, Mac OS X, Mac OS X, Mac OS X, Mac OS X, Mac OS X, Mac OS X, Mac OS X, Mac OS X, Mac OS X, Mac OS X, Mac OS X]}

Magiczne przesunięcie / mnożenie, aby wyodrębnić nasze bity, działa wtedy i tylko wtedy, gdy oba są równe.

Oprócz doskonałych odpowiedzi na to bardzo interesujące pytanie, warto wiedzieć, że ta sztuczka z mnożeniem bitowym jest znana w społeczności szachów komputerowych od 2007 roku, gdzie występuje pod nazwą Magic BitBoards.

Wiele komputerowych silników szachowych używa kilku 64-bitowych liczb całkowitych (zwanych bitboardami) do reprezentowania różnych zestawów elementów (1 bit na zajmowany kwadrat). Załóżmy, że element ślizgowy (Wieża, biskup, królowa) na pewnym kwadrat początkowy może przesuwać się do co najwyżej K kwadratów, jeśli nie ma elementów blokujących. Użycie bitowego-i tych rozproszonych K bitów z płytą bitową zajętych kwadratów daje określone K-bitowe słowo osadzone w 64-bitowej liczbie całkowitej.

Magiczne mnożenie może być użyte do odwzorowania tych rozproszonych K bitów na dolne K bity 64-bitowej liczby całkowitej. Te dolne bity K mogą być następnie używane do indeksowania tabeli wstępnie obliczonych płyt bitowych, które reprezentują dozwolone kwadraty, które kawałek na jego początkowy kwadrat może rzeczywiście przenieść się do (dbanie o bloki itp.)

Typowy silnik szachowy wykorzystujący to podejście ma 2 tabele (jedna dla wieżowców, jedna dla biskupów, królowych wykorzystujących kombinację obu) z 64 wpisami (po jednym na kwadrat początkowy), które zawierają takie wstępnie obliczone wyniki. Zarówno Najwyżej oceniane zamknięte źródło (Houdini) i open source chess engine (Stockfish) obecnie stosuje się to podejście do jego bardzo wysokiej wydajność.

Znalezienie tych magicznych mnożników odbywa się albo za pomocą wyczerpujące wyszukiwanie (zoptymalizowane z wczesnymi odcinkami) lub z trial i eror (np. próba wielu losowych 64-bitowych liczb całkowitych). Nie było wzorców bitowych używanych podczas generowania ruchu, dla których nie można było znaleźć stałej magicznej. Jednak bitowe efekty przenoszenia są zwykle konieczne, gdy bity, które mają być odwzorowane, mają (prawie) sąsiadujące indeksy.

AFAIK, bardzo ogólny SAT-solver approachy by @ Syzygy nie był używany w szachach komputerowych, nie ma też żadnej formalnej teorii dotyczącej istnienia i wyjątkowości takich stałych magicznych.