Iti0120lab6lisa - Redigeerimiste ajalugu

PriitJ – 8. oktoober 2018, kell 06:41

2018-10-08T06:41:17Z

@@ 1. rida: / 1. rida: @@
 Karujahi hästi mängimine eeldab, et saadakse jagu järgmisest probleemist - võiduseisud on otsingupuus sügaval ning vahepeal midagi eriti ei juhtu, näiteks ei ole "löömist". Peenemalt öeldes on igasugused seisueelised ''dünaamilised'' ning võivad nii tekkida kui kaduda.
 === Korduvate seisude elimineerimine ===
@@ 45. rida: / 49. rida: @@
 Sellisel viisil otsides eelistab programm käiku, mis saavutab sama tulemuse varem: kui käik A ja B viivad mõlemad karu nurka surumiseni, aga A teeb seda 3 käigu ja B 20 käiguga, siis järjestades A ettepoole, jääb ta meie valitud käiguks, isegi kui maksimumsügavusel B sama väärtuse saavutab.
-=== Teoreetiline keerukus ===
+== Teoreetiline keerukus ==
 Arvuta välja, kui palju on meie ülesandes toodud mängulaual erinevaid võimalikke seise. Kas on mõeldav, et teha tabel, kus iga seisu jaoks on kirjas, mis käik kõige soodsam on?
 Kuna harjutuse eesmärk on alpha-beta otsinguga tutvumine, siis selliste tabelite genereerimise tehnikaid juhendis pole kirjeldatud :-)

PriitJ: /* Teoreetiline keerukus */

2018-10-07T17:59:17Z

Teoreetiline keerukus

←Vanem redaktsioon		Redaktsioon: 7. oktoober 2018, kell 19:59
47. rida:		47. rida:
	=== Teoreetiline keerukus ===		=== Teoreetiline keerukus ===

	Arvuta välja, kui palju on meie ülesandes toodud ~~mänguväljal~~ erinevaid võimalikke seise. Kas on mõeldav, et teha tabel, kus iga seisu jaoks on kirjas, mis käik kõige soodsam on?		Arvuta välja, kui palju on meie ülesandes toodud mängulaual erinevaid võimalikke seise. Kas on mõeldav, et teha tabel, kus iga seisu jaoks on kirjas, mis käik kõige soodsam on?

	Kuna harjutuse eesmärk on alpha-beta otsinguga tutvumine, siis selliste tabelite genereerimise tehnikaid juhendis pole kirjeldatud :-)		Kuna harjutuse eesmärk on alpha-beta otsinguga tutvumine, siis selliste tabelite genereerimise tehnikaid juhendis pole kirjeldatud :-)

PriitJ: /* Peavariant ja iteratiivne sügavnemine */

2018-10-07T17:45:15Z

Peavariant ja iteratiivne sügavnemine

←Vanem redaktsioon		Redaktsioon: 7. oktoober 2018, kell 19:45
37. rida:		37. rida:
	Iteratiivset sügavnemist (''iterative deepening'') kasutatakse mängudes paljudeks eesmärkideks, nagu aja haldamine, transpositsioonitabelite efektiivne kasutus jne. Meie puhul on temast aga kasu peavariandi (''principal variation'', PV) arvestamisel.		Iteratiivset sügavnemist (''iterative deepening'') kasutatakse mängudes paljudeks eesmärkideks, nagu aja haldamine, transpositsioonitabelite efektiivne kasutus jne. Meie puhul on temast aga kasu peavariandi (''principal variation'', PV) arvestamisel.

	Nimelt on tavaline fikseeritud (näiteks 20 käiguni) sügavusega otsing strateegiliselt väga rumal. Kui sama eesmärgi võib saavutada kolme või 20 käiguga, et tee ta neil vahet ning võib juhuslikult eelistada pikemat varianti - kõik sõltub sellest, mis käik otsingus ettepoole satub. Selline "edasi lükkamine" võib ebasoodsal ~~juhusel~~ kesta lõpmatuseni. Sama efektiga tegelesime juba võiduseisu väärtuse arvutamise juures.		Nimelt on tavaline fikseeritud (näiteks 20 käiguni) sügavusega otsing strateegiliselt väga rumal. Kui sama eesmärgi võib saavutada kolme või 20 käiguga, et tee ta neil vahet ning võib juhuslikult eelistada pikemat varianti - kõik sõltub sellest, mis käik otsingus ettepoole satub. Selline "edasi lükkamine" võib ebasoodsal juhul kesta lõpmatuseni. Sama efektiga tegelesime juba võiduseisu väärtuse arvutamise juures.

	* alustame otsingut sügavusega 1		* alustame otsingut sügavusega 1

PriitJ: Uus lehekülg: 'Karujahi hästi mängimine eeldab, et saadakse jagu järgmisest probleemist - võiduseisud on otsingupuus sügaval ning vahepeal midagi eriti ei juhtu, näiteks ei ole "löömist...'

2018-10-07T14:18:50Z

Uus lehekülg: 'Karujahi hästi mängimine eeldab, et saadakse jagu järgmisest probleemist - võiduseisud on otsingupuus sügaval ning vahepeal midagi eriti ei juhtu, näiteks ei ole "löömist...'

Uus lehekülg

Karujahi hästi mängimine eeldab, et saadakse jagu järgmisest probleemist - võiduseisud on otsingupuus sügaval ning vahepeal midagi eriti ei juhtu, näiteks ei ole "löömist". Peenemalt öeldes on igasugused seisueelised ''dünaamilised'' ning võivad nii tekkida kui kaduda.

=== Korduvate seisude elimineerimine ===

Alpha-beta on sügavutiotsing ning tsüklid mängupuus genereerivad sinna lõputus koguses tippe. Karujahi puhul teame ka, et ükskõik milline kordus on alati karu jaoks kasulik. Seda võib ''minimax'' hinnangut arvutades isegi karu võiduks lugeda, kuna see on parim võimalik tulemus karu jaoks - kahe korduva seisu vahel pole jahimehed mitte midagi saavutanud.

* jäta meelde kõik mängus reaalselt esinenud seisud ja seisude jada otsingupuu juurest käesoleva tipuni (s.t. kuidas otsing hetkel arvab, et mäng edasi läheks)
* katkesta otsing (s.t. tagasta seisu väärtus, mis on karu jaoks positiivne ja jahimeeste jaoks negatiivne), kohe, kui otsingu käigus esinev seis kordab mingit eelnevat seisu
* pane tähele, et sama nuppude konfiguratsioon on sama seis ainult siis, kui käigul on ka sama pool

=== Käikude järjestamine ===

Alpha-beta algoritm eeldab, et paremad käigud tehakse enne, kui halvemad. Üks lihtsamaid viise seda teha oleks otsida enne käike, mis viivad mänguvälja keskele. Karu eelistaks jääda keskele ning jahimehed peavad ka sinna liikuma, et karu äärele tõrjuda. Seega võime väga umbkaudu hinnata, et käigud keskmistele väljadele on paremad.

=== Transpositsioonitabel ===

Eelnevad muudatused teevad meie otsingu teoreetilisest seisukohast väga palju efektiivsemaks. Praktikas peab ta aga ikkagi palju tühja tööd tegema, kuna meie karujahi mängus, nagu ka paljudes teistes mängudes, viivad sageli erinevad käikude järjestused samade seisudeni, seda nii samal kui ka teistel otsingusügavustel.

Väga lihtsustatult on transpositsioonitabel (TT) koht, kus on kirjas, mis mingi seisu otsinguga leitud väärtus on. Selle seisu uuesti kohtamisel pole enam vaja otsingut korrata, väärtus võetakse tabelist.

Praktikas on asi natuke keerulisem. Alpha-beta efektiivsus põhineb sellel, et paljude seisude jaoks ei arvutata selle täpset väärtust vaid see, palju ta maksimaalselt või minimaalselt väärt on. Neid ei saa omavahel segamini ajada ega ka käsitleda täpse ''minimax'' väärtusena.

Vaata [http://people.csail.mit.edu/plaat/mtdf.html#abmem siit] ühte viisi, kuidas TT väärtuseid käsitleda. Näiteks ''beta''-lõike puhul otsing katkestatakse ning teada on vaid, et väärtus on ''vähemalt'' see mis leiti. Nii pannaksegi see alampiirina kirja ja seda tohib ka järgmisel korral samas seisus ''beta''-lõike tekitamiseks kasutada.

Sageli kontrollitakse ka, kui sügava otsinguga TT väärtus on leitud ning kasutatakse ainult neid, mille sügavus on sama suur või suurem, kui praeguse otsingu sügavus oleks ilma TT-ta.

Koos eelnevate muudatustega peaks saavutatav otsingusügavus radikaalselt suurenema ning ulatuma vähemalt 20-40 käiguni.

=== Hinnangufunktsioon ===

Nüüd on otsing efektiivne, aga suudab eristada ainult võiduseise ja kordusi. See tähendab, et vahepealsed seisud tunduvad kõik ühesugustena, mida nad kindlasti tegelikult ei ole. Täpsem hinnangufunktsioon (''utility'', ''eval'') aitab mängu juhtida soodsas suunas.

Strateegiamängudes on tihti oluline tsentraalsus ja mobiilsus. See kehtib ka siin, vähemalt karu kohta. Lihtsa, aga suhteliselt hea hinnangufunktsiooni saame, kui anname jahimeestele plusspunkte, kui karu asub serval. Lisaks anname jahimeestele punkte, kui mõni jahimees paikneb karu kõrval - see piirab karu mobiilsust. Karu poolt mängides annavad samad asjad miinuspunkte.

=== Peavariant ja iteratiivne sügavnemine ===

Iteratiivset sügavnemist (''iterative deepening'') kasutatakse mängudes paljudeks eesmärkideks, nagu aja haldamine, transpositsioonitabelite efektiivne kasutus jne. Meie puhul on temast aga kasu peavariandi (''principal variation'', PV) arvestamisel.

Nimelt on tavaline fikseeritud (näiteks 20 käiguni) sügavusega otsing strateegiliselt väga rumal. Kui sama eesmärgi võib saavutada kolme või 20 käiguga, et tee ta neil vahet ning võib juhuslikult eelistada pikemat varianti - kõik sõltub sellest, mis käik otsingus ettepoole satub. Selline "edasi lükkamine" võib ebasoodsal juhusel kesta lõpmatuseni. Sama efektiga tegelesime juba võiduseisu väärtuse arvutamise juures.

* alustame otsingut sügavusega 1
* jätame meelde, mis käik leiti ning liidame sügavusele 1
* järgmisel sügavusel paigutame leitud käigu otsingujärjekorras esimeseks

Sellisel viisil otsides eelistab programm käiku, mis saavutab sama tulemuse varem: kui käik A ja B viivad mõlemad karu nurka surumiseni, aga A teeb seda 3 käigu ja B 20 käiguga, siis järjestades A ettepoole, jääb ta meie valitud käiguks, isegi kui maksimumsügavusel B sama väärtuse saavutab.

=== Teoreetiline keerukus ===

Arvuta välja, kui palju on meie ülesandes toodud mänguväljal erinevaid võimalikke seise. Kas on mõeldav, et teha tabel, kus iga seisu jaoks on kirjas, mis käik kõige soodsam on?

Kuna harjutuse eesmärk on alpha-beta otsinguga tutvumine, siis selliste tabelite genereerimise tehnikaid juhendis pole kirjeldatud :-)