[ dontoo @ 17.03.2010. 18:14 ] @
Dali je tko čitao kakvu knjigu gdje se objašnjava board game AI ( šah, go, itd.. )? Zanimaju me različiti search tree algoritmi za takve igre. Ili ako tko zna sajt koji dobro objašnjava ova područja, može i to.
[ vlaiv @ 18.03.2010. 08:29 ] @
Za pocetak preporucujem da se upoznas sa min max algoritmom, to ti je osnova po kojoj se prave algoritmi
za igre sa naizmenicnim potezima

http://www.lmgtfy.com/?q=min%20max%20algorithm

Nakon toga preporucujem da pogledas na netu (ili sam da smisljas ako si sklon tome, posto je i zabavno
i korisno) heuristiku situacije na tabli.

U gore pomenutom algoritmu kljuc je heuristicka (ili pak deterministicka u zavisnosti od igre, za jednostavnije
igre se tacno zna kakva je situacija) funkcija koja odredjuje nivo (interval recimo 0-1) koji oznacava kvalitet
pozicije gde je 0 igrac izgubio i 1 igrac pobedio sa svim vrednostima u intervalu koji predstavljaju "koliko dobro
stoji igrac"

Za min max algoritam je dobro razviti i funkciju koja ce takodje u nekom intervalu (opet 0-1) da proceni
korisnost poteza ali nije od toliko velike vaznosti posto samo sluzi da bi se ubrzalo trazenje.
Svojstvo min max algoritma (varijanta sa alpha i beta odsecanjem - pruning) jeste da je izuzetno brz
ukoliko se prvo ispituju potezi koji doprinose da se situacija pomeri u korist igraca (recimo za shah:
materijalna ili poziciona prednost). Ova funkcija sluzi za sortiranje mogucih poteza prilikom pretrage.
(pre ce doci na ispitivanje potez kojim se pesakom nosi top nego skakac menja poziciju na nekom delu table
koji nije od velike pozicione vaznosti)

Napomena: (a to ces videti kada se upoznash sa min-max algoritmom) igrac u gore navedenom kontekstu
je i program i covek, u zavisnosti ciji se potez gleda. Kompjuter tezi da maksimizira efektivnost svog poteza
i ujedno minimizira efektovnost covekovih mogucih poteza (to ces videti iz algoritma)

Sam min-max algoritam se moze dodatno ubrzati nekim keshiranjima rezultata i slicno, ali je sam po sebi
doboljno brz ako se pravilno implementira. Kljuc lezi u kvalitetnoj funkciji za procenu situacije na tabli.

U zavisnosti od algoritma ove funkcije mogu se razviti razliciti tipovi igraca. Npr igrac koji favorizuje igru
pesacima ili pak igrac koji juri materijalnu prednost.

Eto, preporuka je da pocnes odatle pa ces vec pohvatati gde sta na netu treba dalje da procitas.
[ Nedeljko @ 20.10.2010. 02:53 ] @
Programiranje igara u kojima učestvuje više od dva igrača je bitno različito od programiranja igara za dva igrača.