Табеле битова

Табела битова (Битбоард) је структура података која се користи у теорији игара.

Табела битова, која се често користи за имплементацију игара као што су шах, Дама и игре речима, је специјална врста битског низа, у којој сваки бит чува позицију или неко стање игре. Дизајнирана је да оптимизује брзину и умањи коришћење простора главне меморије, као и да смањи коришћење диска при великим рачунањима. Битову у истој табели битова су повезани правилима игре и обично представљају неко стање игре кад се посматрају заједно. Друге табеле битова се често користе као маске да трансформишу позиције или да одговарају на упите о позицијама.

Кратак опис

Табеле битова се користе у многим водећим светским програмима за шах, као што су Хоудини, Стоцкфисх, и Цриттер. Оне помажу програмима да анализирају позиције шаховских фигура са малим бројем процесорских инструкција и да ефикасно чувају огроман број стања у меморији.

Табеле битова омогућавају компјутеру да одговори на нека питања о стању игре са једном логичком операцијом. На пример, ако програм за шах жели да зна да ли има белих пијуна на центру табле, све што треба да се уради, јесте да пореди табелу битова која означава позиције белих пијуна са табелом битова која представља четири поља средине табле и да извриши једну „И“ операцију.

Резултати упита се такође могу представити коришћењем табела битова. На пример, одговор на упит: „Која поља се налазе између X и Y?“ се може представити као табела битова. Резултати оваквих упита су обићно унапред израчунати, тако да је програму за упит потребно само једо читање из меморије.

Међутим, као последица огромне компресије и енкодирања, програми који користе табеле битова нису лаки за писање и одржавање.

Историја

Табеле битова се први пут појављују средином 50-их у програму за даме, који је направио Артур Самјуел. Метод је објављен 1959. у ИБМ-овом журналу истраживања и развоја (ИБМ Јоурнал оф Ресеарцх анд Девелопмент).

Тим Каисса из Совјетског савеза је тај метод независно поново открила касних 60-их у много компликованијем програму за шах, али није јавно документовано.

Опис за све игре или апликације

Табела битова или бит поље је формат који ставља групу повезаних логичких променљивих у исту машинску реч, обично представља позиције или стања игре. Сваки бит је једна позиција и ако је тај бит позитиван, онда је вредност те позиције тачна. На пример, једна табелу битова представља позиције црних коња на шаховској табли, та табела битова би се састојала од 64 бита, где би сваки бит представљао једно поље шаховске табле. Друга табела битова је константа и представља четири централна поља шаховске табле. Поређењем те две табеле битова, логичком операцијом „И“ добићемо трећу табелу битова која представља црне коње на средини шаховске табле. Овај формат је генерално бољи за процесор и меморију.

Предности и мане

Процесор

Предности

Предност коришћења табеле битова је сто се искориштавају битовске операције које су имплементиране на скоро сваком процесору и које се извршавају у једном циклусу. Скоро сви процесори имају уграђене логичке операције „I“, „ИЛИ“, „НИЛИ“ и ексклузивну дисјункцију, а многи имају и инструкције за додатне битовске операције, као што је налажење првог бита, које чине табеле битова још ефикасније. Ако немају те додатне инструкције постоје многи алгоритми преко којих се то може имплементирати брзо.

Даље, модерни процесори имају проточну обраду, која ставља инструкције у ред да чекају на извршавање. Процесор са више јединица за извршавање може да обавља више од једне инструкције по циклусу ако више инструкција чека на извршавање. Гранање (коришћење условних наредба као сто је „иф“ наредба) отежава процесору да користи проточну обраду, јер процесор није сигуран шта ће му требати у будућности. Табеле битова захтевају мање условних наредба и тако ефикасније искориштавају процесор.

Мане

За неке упите ће бити потребно више времена него да су се користили низови, па се табеле битова обично користе уз низове.

Коришћење меморије

Предности

Табеле битова су веома компактне. Потребно је веома мало простора у меморији да би се представила позиција или маска, па онда много позиција може завршити у регистрима и кешу. Ово ће допринети бољим перформансама јер ће време учитавања бити драстично мање.

Мане

За неке игре имплементација са табелама битова ће бити поприлично дужа од класичне. За неке ограниченије уређаје (као што су мобилни телефони) који имају ограниченији број регистра или мање процесорске кеш меморије, ово може проуyроковати проблеме. На слабијим десктоп рачунарима, ово може прузроковати више промашаја између Л1 и Л2 кеша. Ово није велика мана јер ће већина машина имати довољно кеша, па ово неће бити проблем.

Стандардне

Алгебарска нотација

Први бит обично представља поље а1 (доњи леви угао), а 64. бит представља поље х8 (горњи десни угао).

Постоји дванаест врста фигура и свака има своју табелу битова. Заједно тих дванаест табела битова представља поyиције фигура једног играча. Неки тривијални подаци такође требају да се чувају. На пример, који играч је на потезу, да ли је играч матиран итд.

Обично су имплементиране константе, на пример: WХИТЕ_СQУАРЕС (бела поља), БЛАЦК_СQУАРЕС (црна поља), ФИЛЕ_А (колона а), РАНК_4 (четврти ред) итд.

Ротиране

„Ротиране“ табеле битова се обично користе у свим програмима који користе табеле битова. Оне чине одређене операције ефикаснијим. Овакви енџини се називају „енџини ротираних табела битова“, али то није баш добар назив јер они поред ротираних, садрже и обичне табеле битова.

Овакве табеле битова ротирају позиције за 90, 45 или 315 степени. Типична табела битова има један бајт по врсти шаховске табле. Са оваквом табелом лако је одредити како топ напада по врсти, корестећи табелу индексирану по заузетом пољу и заузетим позицијама у врсти (пошто се напад топа зауставља на првом заузетом пољу). Ротирајући табелу за 90 степени, можемо на исти начин и одредити како напада и по колонама. Кад додамо табеле ротиране за 45 и 315 степени, добијамо табеле у којима лако можемо посматрати дијагонале. Како краљица напада можемо лако видети спајањем табела битова за топ и ловца.