Po 18 rokoch počítania dokonalá neporaziteľná stratégia pre PC v dáme

Ďalšou tradičnou doskovou hrou, ktorá neodolala výraznému nárastu výkonu PC, a ktorá je dokonale vyriešená počítačmi sa stala americká verzia hry dáma. Po 18 rokoch počítania bol preskúmaný kompletný strom možných vývojov hry, ktoré môžu vzniknúť pri ideálnom hraní. Zo stromu vyplynulo, že pri optimálnej stratégii oboch hráčov sa hra skončí remízou, ani pre jedného z hráčov tak definitívne neexistuje výherná stratégia.

DSL.sk, 20.7.2007

Ďalšou doskovou hrou, ktorá neodolala mohutnému nárastu výpočtového výkonu počítačov, sa stala americká verzia hry dáma.

Americká dáma sa hrá podobne ako zvyčajne na Slovensku hrávaná verzia na hracom poli s 8 x 8 poľami. Každý hráč má ale dvanásť kameňov, začína hráč s čiernymi kameňmi.

Po presunutí sa na základnú líniu protihráča sa stáva z kameňa tzv. dáma respektíve v USA kráľ, ktorý sa môže pohybovať a skákať aj dozadu. V americkej verzii je to ale iba o jedno pole podobne ako u základných kameňov.

Hoci je dáma výrazne jednoduchšia ako šach, doteraz nebola optimálne vyriešená počítačmi a dlhodobo sa v nej organizujú aj majstrovstvá sveta.

Tím Jonathana Schaeffera z University of Alberta v kanadskom Edmontone včera oficiálne oznámil ukončenie počítačového dokazovania, ktoré preukázalo, že pri optimálnej hre neexistuje ani pre začínajúceho ani pre druhého hráča víťazná stratégia a hra skončí remízou.

Tím má zároveň k dispozícii strom optimálnych ťahov, ktorý umožňuje počítaču hrať dokonale a nikdy neprehrať, podľa ťahov protivníka remizovať alebo zvíťaziť.

Tento strom nie je k dispozícii pre každú možnú pozíciu v hre vzniknutú pri neoptimálnom začiatku, ale iba pre pozície potrebné pri dokazovaní optimálnej stratégie zo štartovnej pozície. Zároveň ale obsahuje optimálne riešenia aj pre veľmi veľa pozícii, ktoré neležia na trasách optimálnych hier oboch hráčov.

Rovnako o šachu sa predpokladá, že ani pre začínajúceho alebo pre druhého hráča víťazná stratégia neexistuje a pri optimálnej hre oboch hráčov sa tak hra skončí remízou. Vzhľadom na rádovo oveľa väčší počet možných pozícií je ale dôkaz tejto teórie zatiaľ v nedohľadne.

Dáma má celkovo 5 x 10 ^ 20 možných pozícií, práca na jej úplnom vyriešení odštartovala v roku 2001. Použité ale boli aj výsledky vypočítané postupne od roku 1989 pre program Chinook, ktorý sa stal majstrom sveta medzi ľudmi v roku 1994.

Chinook mal vybudovanú kompletnú databázu optimálnych riešení pre situácie s ľubovoľnými najviac desiatimi kameňmi rozličného typu na hracom poli. Táto databáza obsahuje 3.4 x 10 ^ 13 pozícii, vďaka špecializovanému komprimačnému algoritmu zohľadňujúcemu prechody medzi pozíciami zaberá len 237 gigabajtov miesta, teda v jednom bajte sú uložené informácie o priemerne 154 pozíciách.

Výpočet prehľadávajúci strom optimálnych riešení využívajúci heuristiku programu Chinook začal až v roku 2001 so štvoročnou prestávkou po predchádzajúcich výpočtoch, keďže algoritmus vyžadoval dostupný 64-bitový operačný systém. Použitý OS a konfiguráciu počítačov Schaeffer nespresnil.

Výpočet bežal na priemerne 50 počítačoch súčasne, v niektorých obdobiach na viac ako 200 počítačoch. Výpočet bol dokončený 29. apríla tohto roka, 19. júla boli výsledky prvýkrát verejne publikované v magazíne Science.

Strom optimálnych riešení a možného výsledku pri uskutočnení daného ťahu si je možné pozrieť interaktívnym spôsobom tu, hry ale nie je možné dohrať úplne do konca, ukážka sa zastaví pri odkaze na strom predpočítaných koncoviek.

Viac informácií je možné nájsť na stránke projektu tu.





Najnovšie články:



Diskusia:

Beli Od: Beli | Pridané: 20.7.2007 14:51 Mne by sa teda čakať 6 rokov nechcelo:) Odpovedať Hodnotiť:

Cerni Od: Cerni | Pridané: 20.7.2007 15:19 program Chinook, ktorý sa stal majstrom sveta medzi ľudmi Odpovedať Hodnotiť:

MortarMan Od: MortarMan | Pridané: 22.7.2007 20:54 To je VHuboSratie - ako sa može program porovnavať s človekom ? keby mal aspoň AI ale on je len nastaveny na 60000 tahov dopredu co ma robit Odpovedať Hodnotiť:

Deer Dance Od: Deer Dance | Pridané: 22.7.2007 22:36 sa nemoze, vstanem a hodim z okna... FLAWLESS VICTORY Odpovedať Hodnotiť:

šoked Od: šoked | Pridané: 20.7.2007 15:45 šokujuce zistenie!!! Odpovedať Hodnotiť:

wave Od: wave | Pridané: 20.7.2007 21:30 ze, to sa mi zda take ..logicke.. ze remiza Odpovedať Hodnotiť:

tom Od: tom | Pridané: 20.7.2007 22:05 logicke to je u kazdej hry, otazne prave je, ci je to tak naozaj Odpovedať Hodnotiť:

wave Od: wave | Pridané: 22.7.2007 15:07 njn Odpovedať Hodnotiť:

FfF Od: FfF | Pridané: 20.7.2007 15:57 haa rad by som videl vyraz v tvarach tych matikov ktori po 18 rokoch vysli z pivnice a uvideli denne svetlo :DD boha naco sa s tym vobec srali.. Odpovedať Hodnotiť:

Uhlik Od: Uhlik | Pridané: 20.7.2007 16:27 teraz by som im odporucal este zaliezt naspat a nech skusia zistit, ci sa da remiza dosiahnut vzdy aj v pripade, ze super urobi pocas hry jednu chybu ;) ... Odpovedať Hodnotiť:

FfF Od: FfF | Pridané: 20.7.2007 19:45 alebo este zakernejsie- zmenime im sachovnicu na modro zelenu .. ich porazi z toho :) Odpovedať Hodnotiť:

Ibi maiga Od: Ibi maiga | Pridané: 21.7.2007 14:21 Pote si zahrat. http://www.travian.cz/?uc=cz8_18113 Odpovedať Hodnotiť:

RemuS Od: RemuS | Pridané: 20.7.2007 16:48 Si predstavte co za kompy budu, ked si precitame takuto spravu o spominanom sachu! uf, ktovie ci sa toho dozijeme, ale nepochybujem o tom, ze aj to raz pride Odpovedať Hodnotiť:

thriler Od: thriler | Pridané: 20.7.2007 16:57 Lebo ten program spustali povodne na 286 a zakazdym, ked pisiel rychlejsi pc tak to pustali odznova preto tych 18 rokov. :D Odpovedať Hodnotiť:

Scorpio Od: Scorpio | Pridané: 20.7.2007 18:38 Zas sprosty amici musia mat inu damu nez zvysok sveta, by bolo moc na nix posunut o viac policok. :D Odpovedať Hodnotiť:

einstein Od: einstein | Pridané: 20.7.2007 20:51 dalo sa to vypocitat len pre americku damu,pre europsku verziu by to neslo.je tam radovo viac kombinacii.je to ako keby objavili tepnu v kuracom hovne,tieto hry boli vymyslene pre ludi a koho serie ci si s tym poradi stroj.je to sport a hra. Odpovedať Hodnotiť:

wave Od: wave | Pridané: 22.7.2007 15:14 uplne suhlasim to su fakt dementi... radsej si spravia vlastnu, horsiu verziu hry, ako hrat svetovu... a potom aby si to este selektoval na nete, ked si chces trochu zahrat Odpovedať Hodnotiť:

wave Od: wave | Pridané: 20.7.2007 21:29 lol vyhral som... Odpovedať Hodnotiť:

Hrusky Od: Hrusky | Pridané: 20.7.2007 22:14 v šachu je tolko moznych kombinacii ze nemaju sancu to vypocitat, aspon v najblizsich 5-10 rokov urcite... Odpovedať Hodnotiť:

AMIDEZ Od: AMIDEZ | Pridané: 20.7.2007 23:10 To mas pravdu v Sachu je pravdepodobne viac pozicii ako atomov v celom vesmire....ale americania maju urcite iny sach mozno kon sa moze pohybovat iba do lava a do prava.... Odpovedať Hodnotiť:

tomino Od: tomino | Pridané: 21.7.2007 0:14 nepodcenujme ludskeho ducha=) Odpovedať Hodnotiť:

thriler Od: thriler | Pridané: 21.7.2007 17:07 V sachu je nekonecne mnozstvo kombinacii. To bude tym, ze sa da pohybovat aj dopredu aj dozadu. Odpovedať Hodnotiť:

Uhlik Od: Uhlik | Pridané: 21.7.2007 22:04 kazde mnozstvo je konecne ;) ... Odpovedať Hodnotiť:

jas Od: jas | Pridané: 26.7.2007 12:23 Nie, nieje. Odpovedať Hodnotiť:

wave Od: wave | Pridané: 22.7.2007 15:11 jasne ze sach sa neda vypocitat... kedze mozes donekonecna tahat tam a spat... ale moze sa dat vypocitat, asi empiricky, tah, vlastne tahy, ktore ti zarucia istu vyhru pri "momentalnom" superovom rozpolozeni figuriek... BTW: aj vas pomylilo to slovicko "ked" ktore je pouzite v ankete? to si verite DSL.sk ked ste nepouzili AK :D Odpovedať Hodnotiť:

oOuser Od: oOuser | Pridané: 20.7.2007 23:41 ^ je xor? :-D Odpovedať Hodnotiť:

xxxx Od: xxxx | Pridané: 20.7.2007 23:41 KUknite www.zadarmoveci.szm.sk NEOLUTUJETE !! ZADARMO VECI A KTOMU ANI ZA POSTOVNE NEPLATITEE NAPRIKLAD PODLOZKA POD MYSS, VYSOKA KVALITA, FOTKY A INE VECI !! TAK NACO ESTE CAKATE ? SOSNITE !!!!! Odpovedať Hodnotiť:

kanpo Od: kanpo | Pridané: 20.7.2007 23:57 spammer posr... no ale ehm co som to cel... aha uz viem - mali zavolat mojho fotra, ten by im zarucene strategie napisal rucne za pol dna:) Odpovedať Hodnotiť:

Aero Od: Aero | Pridané: 21.7.2007 10:35 Neznasam hranie sachu alebo damy proti pocitacom .... podla mna sa tym hra kazi ... lebo ked hrajem proti niekomu tak mozem ratat s tym ze si niektore tahy nevsimne alebo zabudne ... pocitac takuto chybu nikdy neurobi a stale vidi celu plochu + chyby ktore som spravil a a nevsimol som si ich ... Odpovedať Hodnotiť:

Miso Od: Miso | Pridané: 21.7.2007 17:03 lenze su aj taki co chyby prakticky nerobia :) a tych to proti kamosom nebavi :D Odpovedať Hodnotiť:

thriler Od: thriler | Pridané: 21.7.2007 20:34 Suhlasim s tebou. V tom byva taktika. Odputania pozornosti jednym tahom, zatial co chystas nieco zlozitejsie. Odpovedať Hodnotiť:

Apelix Od: Apelix | Pridané: 21.7.2007 15:23 nato neni vzorec kolko ich tam je ?? kde tam je vela pozicii?? ved prsote nikdy nespravis ze odkrijes hend krala akoze nechaepom jak ze pozicie ??, niektore su nerealne lebo by si napr niekeoho vyhodil ?? jak pozicie ? nechapem tomu ze ked su v plnom pocte alebo co ?? kolko kombinacii hry je mozne ?? Odpovedať Hodnotiť:

Od: | Pridané: 21.7.2007 17:21 tak si tie pozície skús zakresliť (šach), začni prvým kolom, všetkými možnými kombináciami malo by ich byť 144, a každá z týchto kombinácií vytvára strom ďaľších... keď dokreslíš daj vedieť Odpovedať Hodnotiť:

Od: | Pridané: 21.7.2007 18:02 sorry, sekol som sa, malo by to byť 400 možností, miesto 144, dúfam že teraz je to dobre... Odpovedať Hodnotiť:

Uhlik Od: Uhlik | Pridané: 21.7.2007 22:16 tak tak ... a treba pripomenúť aj to, že v druhom kole ich už bude viac ako 400, keďže je možné ťahať podľa pozície figúrok aj vežami, strelcami, kráľom a dámou, takže v dvoch kolách už je možností podstatne viac ako 20 000 a toto číslo ďalej rastie geometrickým rádom ... ale snáď si s tým o 5 rokov nejaký cluster s 80 jadrovými procesormi hravo poradí ;) ... Odpovedať Hodnotiť:

Od: | Pridané: 21.7.2007 22:36 veru :D toto bude asi dosť mimo čo poviem, ale zdá sa mi, že po druhom kole je už možností cez 400 na druhú (160 000), keďže každá z tých 400 možností umožňuje, všetky zvyšné pohyby, okrem toho jedného, ktorý už bol vykonaný, a tiež umožňujú pohyb iných figúrok, ktoré sa nemusia hýbať len o 1 políčko.. ale apelixovi sa tozdá málo :D Odpovedať Hodnotiť:

Uhlik Od: Uhlik | Pridané: 22.7.2007 12:54 ano ... neviem preco som si myslel, ze 400x400 je 20000 :D ... internal error :o) ... Odpovedať Hodnotiť:

jas Od: jas | Pridané: 26.7.2007 12:27 A po 200 rokoch, keď počítač konečne dopočíta všetky možnosti, vedci zistia, že v algoritme nastala chyba :) . Odpovedať Hodnotiť:

Parada!!!!! Od: Parada!!!!! | Pridané: 22.7.2007 1:31 Fakt uzas, nieco neuveritelne co sa zas zistilo vo svete cele roky som na toto cakal! Oznamujem svetu ze v priebehu poslednych 18-tich sekund som zistil ze sa idem vysrat. Odpovedať Hodnotiť:

Uhlik Od: Uhlik | Pridané: 22.7.2007 12:56 To mi pripomina jeden vtip: - Keď si predstavím, že jedna operácia dnes trvá procesoru cca 0,000000001 sekundy, že počas mrknutia oka dokáže 80 000 000x presunúť čísla medzi registrami, spočítať a odčítať ich, počas toho súčasne 85x prekresliť všetkých 995 328 bodov na obrazovke a ešte si ich 130 000x overiť, či som medzitým náhodou nestlačil kláves alebo nepohol myšou, tak sa potom proste musím opýtať: Čo ten Excel už dve minúty, ku*va, robí...? Odpovedať Hodnotiť:

apelix Od: apelix | Pridané: 22.7.2007 12:48 kombinacie sa rataju len s jednymi farbami ?? ze kolko napr sa da urboti s ciernymi ?? alebo kolko kombinacie hier je moznych ?? Odpovedať Hodnotiť:

Od: | Pridané: 22.7.2007 14:41 počet možností? strašne veľa. Snáď sa neseknem pre zjednodušenie rátania, lebo zložitejšie sa mi nechce, alebo by som to nevedel? skôr to druhé... :(, nebudem brať do úvahy, že sa figúrky nebudú môcť vzájomne vyhadzovať, budú to takí dobrí kamaráti čo sa stretli na pive, a tiež že nehráme šach, len tie figúrky ukladáme na pozície, ktoré by v šachovej partii mohli okupovať. Tak teda: pešiakov máš 8 na každej strane, biely môžu mať 7 pozícií, kým čierny už len 6, pretože dáke tie políčka sú už obsadené, to je 7 na ôsmu * 6 na ôsmu, ostáva ešte 48 políčok a 16 figúriek, ďaľšie zjednodušenie, predpokladajme, i keď to nemusí byť pravda, že vždy je polovica z nich čierna. Teda strelcov na strane bielych môžeš uložiť 24*24 možnosťami, kým na strane čiernych 23*23 možnosťami, Odpovedať Hodnotiť:

Od: | Pridané: 22.7.2007 14:42 ostáva ešte 44 políčok a 12 figuriek, tieto môžeš obsadiť ľubovoľnými ostatnými tak teda 44*43*42*41*40*39*38*37*36*35*34*33*(tí strelci)24*24*23*23* (pešiaci)*7*7*7*7*7*7*7*7*6*6 *6*6*6*6*6*6=(zaokrúhlne) 3*10 na 37,k týmto možnostiam ešte musíš prirátať možnosti, keď bude chýbať 1 figúrka, treba prestriedať všetky, jedinečné- 2+2+2+2+4+16, ale toto sa nenásobí, to je len koľkými spôsobmi môže chýbať 1 figúrka, potom 2 etc, až zostane iba jeden kráľ... ale zaváňa mi to chybou :D skutoční matici prosím opravte :D ak sa Vám bude chcieť :) Odpovedať Hodnotiť:

Od: | Pridané: 22.7.2007 14:45 ale až taký vysoký rád, pre všetky figúrky? sa mi fakt nezdá... musel som sa seknúť... Odpovedať Hodnotiť:

A.N. Od: A.N. | Pridané: 23.7.2007 9:29 hmm.. Autista? :) Odpovedať Hodnotiť:

pan dan Od: pan dan | Pridané: 23.7.2007 13:12 Vypocitat tie moznosti v sachu by sa este dalo, vobec ich nie je nekonecne vela, ved cykly "tahat tam a spat" su nepovolene. Dalej vela usporiadani sachovnice by sa opakovalo, vtedy by sa taketo vetvy stromu rieseni mohli spojit, tym sa usetri vela duplicit. Problemom by bolo ukladanie vysledkov a ako som uz spomenul, prehladavanie, ci uz taketo usporiadanie nevzniklo predtym. Odpovedať Hodnotiť:

muno Od: muno | Pridané: 23.7.2007 13:15 No tak takéto drísty ma naozaj bavia. Celú dámu si strčte do prdele, nemám záujem, nasrať ! Odpovedať Hodnotiť:

opec Od: opec | Pridané: 23.7.2007 13:38 wow, to ma zmysel hrat? hrame predsa pre pocit vytaztva Odpovedať Hodnotiť:

... Od: ... | Pridané: 24.7.2007 16:46 to potrebovali pocitat ?!?!?!? ked si vezmem velkost hracej plochy pocet kamenov, a 2 skuseniych hrac tak viem ze to moze skonct len remizou. V dame sa ma clovek mensiu pravdepodobnost urobit zly tah ako v savhu Odpovedať Hodnotiť:

666 Od: 666 | Pridané: 25.7.2007 11:31 http://bux.to/?r=Peptalkin zaregistrujte sa a klikanim zarabajte. Nie su to ziadne horibilne sumy, ale aspon je tato sluzba seriozna. Zaregistrujte sa prosim vyuzitim mojho referalu, nic tym nestracate. http://bux.to/?r=Peptalkin Odpovedať Hodnotiť:

Aero Od: Aero | Pridané: 28.7.2007 1:55 Jak vidim jak z celej sily pocitate kolko moznosti potiahnutia je v druhom kole tak to mozno za tych 18 rokov vypocitate aj sami z hlavy :D ale predpokladam ze za 18 rokov bude mašina ktora to vypočita sa par sekund :D ... samozrejme ak nenastane monopol Intelu alebo AMD :P Odpovedať Hodnotiť:

666 Od: 666 | Pridané: 2.8.2007 13:55 aj keby nastal monopol tak bude urcite nejaka firma ktora bude stale chcet byt lepsia lebo ju budu potrebovat nejake americke vladne organizacie aby boli vpredu pred konkurenciou Odpovedať Hodnotiť:

dejan Od: dejan | Pridané: 6.8.2007 20:30 Zarabajte na nete jednoduchym klikanim, Potrebujete len ucet na Paypal. :) http://tiny.sk/a52fv3k7 http://tiny.sk/9ig642fh http://tiny.sk/3nrcvus4 http://tiny.sk/zsbovzkr http://tiny.sk/trwtbxr5 http://tiny.sk/uo5qsatj http://tiny.sk/fe3ir7th http://tiny.sk/6wihxaju http://tiny.sk/idavbrhz http://tiny.sk/x44e5hmt http://tiny.sk/e99qya9u http://tiny.sk/k0v24mib http://tiny.sk/awiet2nn http://tiny.sk/z46hp4k5 Odpovedať Hodnotiť:

gddbdfh Od: erik44 | Pridané: 18.8.2010 11:10 Aby ste vedeli šach ma obmedzeny počet kombinacii! Ak sa 50 tahov nevihodi žiadna figurka, alebo sa nepohne pešiakom je remiza! Tieto dve pravidla obmedzuju počet kombinacii a nieje to nekonečno, len neuveritelne vela. Odpovedať Hodnotiť:

svsdbddgbd Od: jadhhs | Pridané: 18.8.2010 11:13 kombinaci je asi 100na 500 Odpovedať Hodnotiť:

Pridať komentár