Avatar uživatele
Kelt

Existuje šachový počítač, který by měl v paměti všechny kombinace?

Šachy mají svá pravidla, na začátku je pouze 20 možností pro úvodní tah, pak dalším tahem roste počet možných tahů. Tento počet tahů ale není nekonečný. Na každý tah by měl kromě těch všech teoretických možností existovat účinný protitah. Tedy teoreticky může, nebo existuje počítač, který by všechny tyto možnosti měl a byl by neporazitelný. Jak by musela být velká jeho kapacita? A je to vůbec možné? Tedy zápas, kdy na jedné straně hraje počítač a na druhé vynikající šachista. Může se radit, není omezena délka tahu ani zápasu. Může nastat situace, že je takový takový šachista proti takovému počítači absolutně bez šance?

Zajímavá 0 před 3430 dny Sledovat Nahlásit



Odpovědi
Avatar uživatele
Dochy

Není počítač, který by měl všechny kombinace. S délkou hry počet kombinací roste exponenciálně (zhruba). Pokud budeme brát trochu zjednodušeně jen počet možných tahů a pro zjednodušení řeknu jen 10 možností. Pak po prvním tahu bíléhoje je 10 možností. S tahem protihráče už je to 100 kombinací, atd… druhý tah obou hráčů už dává 10 000 kombinací, třetí 1 milion, … šestý miliardu. I kdyby bylo možné uložit jeden možný stav hry na jeden byte, pak 3 tahy potřebují cca 1MB paměti, 6 tahů 1000GB = 1TB a to už je kapacita běžného harddisku. Pro dalších 6 tahů, tedy celkem 12 už potřebujete miliardu harddisků.

Data by se dala komprimovat, ale zas je třeba s nimi průběžně pracovat, což použití komprimace zas omezuje… Algoritmus pro počítačového protihráče je poměrně zajímavou školní úlohou. Základní technikou je „brute force“ – počítač si zkusí pomyslně přehrát partii na pár tahů dopředu s tím, že zkouší všechny přípustné tahy v dané situaci a vybere pro něj nejpříznivější tah)
Je to výpočetně a paměťově náročné, počítač stíhá jen pár tahů dopředu. A záleží i na ohodnocovací funkci jak zjistit, který tah je pro něj příznivý, protože až ke konečnému jednoznačnému matu se po většinu hry nedopočítá…

0 Nominace Nahlásit


Avatar uživatele
gecco

Pokud vím, pak nejdokonalejší šachový počítač je DeepBlue ( http://cs.wiki­pedia.org/wiki/De­ep_Blue ) – ale netuším, nakolik má možné kombinace uloženy a nakolik je program ´schopen´ dedukce, osobně se přikláním ke druhé možnosti…
😉

0 Nominace Nahlásit


Diskuze k otázce
Avatar uživatele
bulík

Člověk má výhodu, neřeší slepé uličky. Též je schopen obětovat figury k posílení pozice.

před 3429 dny Odpovědět Nahlásit
Avatar uživatele
Dochy

To dokáže i ten počítač, pokud si to dokáže „promyslet“ dost dopředu aby to posílení pozice poznal, nebo pokud má opravdu dobře nasatvenu tu hodnotící funkci. Jenže člověk to někdy dá „intuitivně“ na základě předchozích zkušeností, bez toho aby si ty tahy opravdu promýšlel… V tomhle má zkrátka člověk nad počítačem výhodu… učí se a uchovává si i ty zkušenosti, které nejsme schopni exaktně popsat… Do počítače můžeme naprogramovat jen to chování, které popsat můžem – a to ještě s omezeními.

před 3426 dny Odpovědět Nahlásit
Nový příspěvek