![]() ![]() |
ARCHIV |
||||||||||||||||
![]() ![]() ![]() ![]() ![]() ![]() |
|
XOR | ||
x | 0 | 1 |
0 | 0 | 1 |
1 | 1 | 0 |
Pokud prázdné pole a černé i bílé kameny reprezentujeme hodnotami 0 až 12, zkažené rošády jedním číslem s nastavenými spodními 4 bity (malá bílá, velká bílá, malá černá a velká černá rošáda, proto 4) a právo braní mimochodem číslem od 0 do 8 podle sloupce, kde lze brát, a 0 znamená, že brát nelze, může být výpočet takto jednoduchý:
u32 nahodaSachovnice[64][13];/* náhodná čísla pro kameny na šachovnici */ u32 nahodaZkazeneRosady[16]; /* celkem 2^(počet rošád) = 2^4 = 16 možností */ u32 nahodaMimochodem[9]; /* 8 sloupců + 1 (nelze brát) = 9 možností braní mimochodem */ u32 nahodaBily; /* kdo je na tahu */ u32 F(const u8 *sachovnice, int rosady, int mimochodem, int bily) { u32 vysledek = 0; int i; for (i = 0; i < 64; i++) { vysledek ^= nahodaSachovnice[i][sachovnice[i]]; } vysledek ^= nahodaZkazeneRosady[rosady]; vysledek ^= nahodaMimochodem[mimochodem]; if (bily) vysledek ^= nahodaBily; return vysledek; }
Díky funkci XOR výsledek závisí na všech polích šachovnice, drobná změna na jediném poli nebo v jiné vlastnosti pozice (braní mimochodem a podobně) způsobí, že výsledek bude vyxorován s jedním úplně jiným číslem a tedy úplně jiný. Díky tomu bude funkce F rozhazovat hodnoty pozic rovnoměrně do celé haš tabulky a kontrolní funkce G používající jinou sadu náhodných čísel bude mít úplně jiné kolize. Myslím, že idea hašování objektu pomocí náhodných čísel a funkce XOR je zajímavá a mohla by se v nějaké zcela odlišné úloze hodit i programátorům, kteří se nikdy šachům věnovat nebudou.
Funkce F a G už jsou definovány správně, ale máme ještě jeden problém a tím je efektivita výpočtu. Funkci budeme volat v každém navštíveném uzlu stromu propočtu včetně listů. Musíme ušetřit každou instrukci. Bohužel ve výpočtu je cyklus přes celou šachovnici a to si nemůžeme dovolit. Naštěstí máme funkce definované pomocí XOR a to je asociativní tj. (A XOR B) XOR C = A XOR (B XOR C), komutativní tj. A XOR B = B XOR A a navíc platí A XOR B XOR B = A. Díky tomu může funkci počítat i inkrementálně. To v podstatě znamená, že podle výše uvedeného kusu kódu spočítáme F a G jen jednou a to na začátku propočtu. Dejme tomu, že program má vymyslet první tah bílého ze základního postavení. Spočítá si tedy F a G pro základní postavení a dejme tomu, že v propočtu zkoumá variantu 1. Jf3 tedy tah jezdcem z g1 na f3. Udělá to následovně:
vysledek = hodnota_F_pro_zakladni_postaveni; vysledek ^= nahodaSachovnice[G1][PRAZDNE_POLE]; vysledek ^= nahodaSachovnice[G1][BILY_JEZDEC]; vysledek ^= nahodaSachovnice[F3][PRAZDNE_POLE]; vysledek ^= nahodaSachovnice[F3][BILY_JEZDEC]; vysledek ^= nahodaBily;
Tedy zaxorují se jenom odlišnosti. Díky tomu, že XOR je samo vůči sobě inverzní operací, nemusíme ani myslet na to, která vlastnost tahem Jf3 nastává a která se ruší. Kdybychom funkce F a G místo na XOR vystavěli například na + (+ tak jak se běžně počítá na procesoru tj. modulová aritmetika se zahazováním bitů které se nevejdou do typu výsledku), museli bychom rušené jevy (zde Jg1 a nic na f3) místo sčítání odečítat a nastávající (zde nic na g1 a Jf3) přičítat. Zároveň je vidět, že bychom mohli náš výpočet s XORem trochu urychlit, pokud bychom pro prázdná políčka místo náhodných čísel použili natvrdo nuly. V příkladu s tahem Jf3 bychom místo s 5 XORy vystačili se třemi.
Příští díl bude o něco techničtější. Řekneme si něco o tom, jak reprezentovat pozici, jak generovat a ukládat tahy a podobně. To všechno jsou věci, které by každý zkušený programátor jistě nějak zvládl, ale existuje celá řada technik a drobných fíglů, které nejsou zcela bezprostřední a mohou ušetřit hodně času jak programátorovi, tak i jeho šachovému programu.
Nejsou žádné diskuzní příspěvky u dané položky. Příspívat do diskuze mohou pouze registrovaní uživatelé. |
28.11.2018 23:56 /František Kučera
Prosincový sraz spolku OpenAlt se koná ve středu 5.12.2018 od 16:00 na adrese Zikova 1903/4, Praha 6. Tentokrát navštívíme organizaci CESNET. Na programu jsou dvě přednášky: Distribuované úložiště Ceph (Michal Strnad) a Plně šifrovaný disk na moderním systému (Ondřej Caletka). Následně se přesuneme do některé z nedalekých restaurací, kde budeme pokračovat v diskusi.
Komentářů: 1
12.11.2018 21:28 /Redakce Linuxsoft.cz
22. listopadu 2018 se koná v Praze na Karlově náměstí již pátý ročník konference s tématem Datová centra pro business, která nabídne odpovědi na aktuální a často řešené otázky: Jaké jsou aktuální trendy v oblasti datových center a jak je optimálně využít pro vlastní prospěch? Jak si zajistit odpovídající služby datových center? Podle jakých kritérií vybírat dodavatele služeb? Jak volit vhodné součásti infrastruktury při budování či rozšiřování vlastního datového centra? Jak efektivně datové centrum spravovat? Jak co nejlépe eliminovat možná rizika? apod. Příznivci LinuxSoftu mohou při registraci uplatnit kód LIN350, který jim přinese zvýhodněné vstupné s 50% slevou.
Přidat komentář
6.11.2018 2:04 /František Kučera
Říjnový pražský sraz spolku OpenAlt se koná v listopadu – již tento čtvrtek – 8. 11. 2018 od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5). Tentokrát bez oficiální přednášky, ale zato s dobrým jídlem a pivem – volná diskuse na téma umění a technologie, IoT, CNC, svobodný software, hardware a další hračky.
Přidat komentář
4.10.2018 21:30 /Ondřej Čečák
LinuxDays 2018 již tento víkend, registrace je otevřená.
Přidat komentář
18.9.2018 23:30 /František Kučera
Zářijový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 20. 9. 2018 od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5). Tentokrát bez oficiální přednášky, ale zato s dobrým jídlem a pivem – volná diskuse na téma IoT, CNC, svobodný software, hardware a další hračky.
Přidat komentář
9.9.2018 14:15 /Redakce Linuxsoft.cz
20.9.2018 proběhne v pražském Kongresovém centru Vavruška konference Mobilní řešení pro business.
Návštěvníci si vyslechnou mimo jiné přednášky na témata: Nejdůležitější aktuální trendy v oblasti mobilních technologií, správa a zabezpečení mobilních zařízení ve firmách, jak mobilně přistupovat k informačnímu systému firmy, kdy se vyplatí používat odolná mobilní zařízení nebo jak zabezpečit mobilní komunikaci.
Přidat komentář
12.8.2018 16:58 /František Kučera
Srpnový pražský sraz spolku OpenAlt se koná ve čtvrtek – 16. 8. 2018 od 19:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tentokrát jsou tématem srazu databáze prezentaci svého projektu si pro nás připravil Standa Dzik. Dále bude prostor, abychom probrali nápady na využití IoT a sítě The Things Network, případně další témata.
Přidat komentář
16.7.2018 1:05 /František Kučera
Červencový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 19. 7. 2018 od 18:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tentokrát bude přednáška na téma: automatizační nástroj Ansible, kterou si připravil Martin Vicián.
Přidat komentář
31.7.2023 14:13 /
Linda Graham
iPhone Services
30.11.2022 9:32 /
Kyle McDermott
Hosting download unavailable
13.12.2018 10:57 /
Jan Mareš
Re: zavináč
2.12.2018 23:56 /
František Kučera
Sraz
5.10.2018 17:12 /
Jakub Kuljovsky
Re: Jaký kurz a software by jste doporučili pro začínajcího kodéra?