Tabele bitova

Tabela bitova (Bitboard) je struktura podataka koja se koristi u teoriji igara.

Tabela bitova, koja se često koristi za implementaciju igara kao što su šah, Dama i igre rečima, je specijalna vrsta bitskog niza, u kojoj svaki bit čuva poziciju ili neko stanje igre. Dizajnirana je da optimizuje brzinu i umanji korišćenje prostora glavne memorije, kao i da smanji korišćenje diska pri velikim računanjima. Bitovu u istoj tabeli bitova su povezani pravilima igre i obično predstavljaju neko stanje igre kad se posmatraju zajedno. Druge tabele bitova se često koriste kao maske da transformišu pozicije ili da odgovaraju na upite o pozicijama.

Kratak opis

Tabele bitova se koriste u mnogim vodećim svetskim programima za šah, kao što su Houdini, Stockfish, i Critter. One pomažu programima da analiziraju pozicije šahovskih figura sa malim brojem procesorskih instrukcija i da efikasno čuvaju ogroman broj stanja u memoriji.

Tabele bitova omogućavaju kompjuteru da odgovori na neka pitanja o stanju igre sa jednom logičkom operacijom. Na primer, ako program za šah želi da zna da li ima belih pijuna na centru table, sve što treba da se uradi, jeste da poredi tabelu bitova koja označava pozicije belih pijuna sa tabelom bitova koja predstavlja četiri polja sredine table i da izvriši jednu „I“ operaciju.

Rezultati upita se takođe mogu predstaviti korišćenjem tabela bitova. Na primer, odgovor na upit: „Koja polja se nalaze između X i Y?“ se može predstaviti kao tabela bitova. Rezultati ovakvih upita su obićno unapred izračunati, tako da je programu za upit potrebno samo jedo čitanje iz memorije.

Međutim, kao posledica ogromne kompresije i enkodiranja, programi koji koriste tabele bitova nisu laki za pisanje i održavanje.

Istorija

Tabele bitova se prvi put pojavljuju sredinom 50-ih u programu za dame, koji je napravio Artur Samjuel. Metod je objavljen 1959. u IBM-ovom žurnalu istraživanja i razvoja (IBM Journal of Research and Development).

Tim Kaissa iz Sovjetskog saveza je taj metod nezavisno ponovo otkrila kasnih 60-ih u mnogo komplikovanijem programu za šah, ali nije javno dokumentovano.

Opis za sve igre ili aplikacije

Tabela bitova ili bit polje je format koji stavlja grupu povezanih logičkih promenljivih u istu mašinsku reč, obično predstavlja pozicije ili stanja igre. Svaki bit je jedna pozicija i ako je taj bit pozitivan, onda je vrednost te pozicije tačna. Na primer, jedna tabelu bitova predstavlja pozicije crnih konja na šahovskoj tabli, ta tabela bitova bi se sastojala od 64 bita, gde bi svaki bit predstavljao jedno polje šahovske table. Druga tabela bitova je konstanta i predstavlja četiri centralna polja šahovske table. Poređenjem te dve tabele bitova, logičkom operacijom „I“ dobićemo treću tabelu bitova koja predstavlja crne konje na sredini šahovske table. Ovaj format je generalno bolji za procesor i memoriju.

Prednosti i mane

Procesor

Prednosti

Prednost korišćenja tabele bitova je sto se iskorištavaju bitovske operacije koje su implementirane na skoro svakom procesoru i koje se izvršavaju u jednom ciklusu. Skoro svi procesori imaju ugrađene logičke operacije „I“, „ILI“, „NILI“ i ekskluzivnu disjunkciju, a mnogi imaju i instrukcije za dodatne bitovske operacije, kao što je nalaženje prvog bita, koje čine tabele bitova još efikasnije. Ako nemaju te dodatne instrukcije postoje mnogi algoritmi preko kojih se to može implementirati brzo.

Dalje, moderni procesori imaju protočnu obradu, koja stavlja instrukcije u red da čekaju na izvršavanje. Procesor sa više jedinica za izvršavanje može da obavlja više od jedne instrukcije po ciklusu ako više instrukcija čeka na izvršavanje. Grananje (korišćenje uslovnih naredba kao sto je „if“ naredba) otežava procesoru da koristi protočnu obradu, jer procesor nije siguran šta će mu trebati u budućnosti. Tabele bitova zahtevaju manje uslovnih naredba i tako efikasnije iskorištavaju procesor.

Mane

Za neke upite će biti potrebno više vremena nego da su se koristili nizovi, pa se tabele bitova obično koriste uz nizove.

Korišćenje memorije

Prednosti

Tabele bitova su veoma kompaktne. Potrebno je veoma malo prostora u memoriji da bi se predstavila pozicija ili maska, pa onda mnogo pozicija može završiti u registrima i kešu. Ovo će doprineti boljim performansama jer će vreme učitavanja biti drastično manje.

Mane

Za neke igre implementacija sa tabelama bitova će biti poprilično duža od klasične. Za neke ograničenije uređaje (kao što su mobilni telefoni) koji imaju ograničeniji broj registra ili manje procesorske keš memorije, ovo može prouyrokovati probleme. Na slabijim desktop računarima, ovo može pruzrokovati više promašaja između L1 i L2 keša. Ovo nije velika mana jer će većina mašina imati dovoljno keša, pa ovo neće biti problem.

Standardne

Algebarska notacija

Prvi bit obično predstavlja polje a1 (donji levi ugao), a 64. bit predstavlja polje h8 (gornji desni ugao).

Postoji dvanaest vrsta figura i svaka ima svoju tabelu bitova. Zajedno tih dvanaest tabela bitova predstavlja poyicije figura jednog igrača. Neki trivijalni podaci takođe trebaju da se čuvaju. Na primer, koji igrač je na potezu, da li je igrač matiran itd.

Obično su implementirane konstante, na primer: WHITE_SQUARES (bela polja), BLACK_SQUARES (crna polja), FILE_A (kolona a), RANK_4 (četvrti red) itd.

Rotirane

„Rotirane“ tabele bitova se obično koriste u svim programima koji koriste tabele bitova. One čine određene operacije efikasnijim. Ovakvi endžini se nazivaju „endžini rotiranih tabela bitova“, ali to nije baš dobar naziv jer oni pored rotiranih, sadrže i obične tabele bitova.

Ovakve tabele bitova rotiraju pozicije za 90, 45 ili 315 stepeni. Tipična tabela bitova ima jedan bajt po vrsti šahovske table. Sa ovakvom tabelom lako je odrediti kako top napada po vrsti, koresteći tabelu indeksiranu po zauzetom polju i zauzetim pozicijama u vrsti (pošto se napad topa zaustavlja na prvom zauzetom polju). Rotirajući tabelu za 90 stepeni, možemo na isti način i odrediti kako napada i po kolonama. Kad dodamo tabele rotirane za 45 i 315 stepeni, dobijamo tabele u kojima lako možemo posmatrati dijagonale. Kako kraljica napada možemo lako videti spajanjem tabela bitova za top i lovca.