[shkola] Malko teoriq na igrite (long) (Was: Re: Edna zadacha za wsichki)

Ta taka. Za da ne wi ostawqm w newedenie i da wi se izqsni na wsichki 
zashto dawam tazi zadacha, shte wi razkazha malko ot teoriqta na 
igrite, taka kakto ni q razkazaha na nas(nacionalite).

> Vsyshtnost sega mi hrumna oshte edna ideq. Ako se vzemat klechki ot
> kraq na edna redica to se promenq nejnata dylzhina. A ako se vzemat
> klechki ot sredata na redicata tova de fakto premahva starata i
> porazhda 2 novi. Mislq che tova mozhe da se izpolzva da se napishe
> edno blyskane po broj redici i dylzhina na vsqka edna ot tqh. Trqbva
> da sedna i da go doiszmislq, no maj shte trqbvat oshte optimizacii da
> se dovede do rabotesht variant.
Tochno za towa ti goworq. W daden moment imash n redici. I celta e da 
namerish podhodqshto kodirane. Towa e ideqta na zadachata - kak da 
se kodira dadena situaciq. 

Ottam natatxk e standartna ideqta: Namirash krajnata(ite) situacii 
obqwqwash gi za gubeshti slagash gi w opashka i weche pochwash da 
obrabotwash opashkata. 
        - Wsqka obrabotena situaciq ot opashkata ti e napxlno razgledana i 
wsichkata informaciq ot neq - izwlechena. 
        - Za wsqka situaciq w opashkata, no ne oshte obrabotena ti znaesh dali 
e pecheliwsha ili gubeshta, no oshte ni si izwlqkal napxlno 
informaciqta ot neq. Tq ne swxrshwa samo s towa.
        - Za wsichki neobraboteni situacii, koito irc.naturella.comne sa i w 
opashkata ne znaesh nishto.
        Ta koga edna situaciq e pecheliwsha - kogato sxshtestwuwa hod, kojto te 
wkarwa w gubeshta situaciq(zashtoto ti predlagash tazi situaciq na 
drugiq i tq e gubeshta). 
        Analogichno situaciqta e gubeshta, kogato wsichki hodowe wodqt do 
pecheliwshi situacii.
        Dotuk pod pecheliwsha i gubeshta situaciq razbiram situaciq, pri koqto 
ti si na hod i priemash che dwamata igrachi igraqt optimalno. Predi da 
prodxlzhim natatxk mnogo dobre si izqsnete gornite dwa momenta.

        I sega kak procedirame. Ami za igri bez cikli t.e. kakto i da igraqt 
igrachite ne mogat da powtorqt weche igrana situaciq(kakwato ochewidno 
e i nashata igra - txj kato broqt na klechkite namalqwa) mozhem da 
polzwame sledniqt algoritxm(ne kazwam che e samo toj, dazhe toj se 
izpolzwa predimno za igrite s cikli).
        1. Namirame nqkakwo kodirane na situaciite. t.e. wsqka igrowa situaciq 
trqbwa da mozhe da se indeksira unikalno s nqkakwo chislo.
        2. Namirame wsichki terminalni situacii. T.e. takiwa za koito e kazano 
w uslowieto che igrata swxrshwa s pobeda za nqkogo. W sluchaq za nas 
towa e 0 reda s 0 klechki obshto. Zashtoto spored uslowieto gubi tozi 
igrach, kojto ne mozhe da naprawi hod. Dobawqme tezi situacii w 
opashka.
        3. Za wsqka situaciq w opashkata namirame wsichki predshestwashti q. I 
...
        3.1.  ako situaciqta e gubeshta, to predshestwashtite q sa pecheliwshi 
i tqh wkarwame w opashkata. 
        3.2. ako situaciqta e pecheliwsha, i za predshestwenika weche sme 
prowerili che wsichki ostanali negowi naslednici sa pecheliwshi, to 
tozi predshestwenik e gubesht i go wkarwame w opashkata(za da obqsnq 
po-dobre - za wsqka situaciq pazim kolko naslednika ima i wseki pxt 
kogato obrabotwame nqkoi ot tezi naslednici i toj e pecheliwsh namalqme 
tozi broqch s edno. ako broqcha stigne 0, to situaciqta e gubeshta, 
ponezhe wodi samo do pecheliwshi za protiwnika situacii)
        3.3. pazim masiw visited, za da ne wkarame dwa pxti situaciq w 
opashkata
        4. Kogato izcherpim opashkata weche sme opredleili wsichki wxrhowe 
dali sa pecheliwshi ili gubeshti. 

        Interesnoto e che tozi algoritxm raboti i za igri s cikli(kato trade 
naprimer) kato tam mozhe da sxshtestwuwat i rawni(neutralni) situacii 
t.e. ne wsichki naslednici sa pecheliwshi, no i nqma gubeshti t.e. ima 
pone edin neutralen naslednik i za nas naj-umno e da igraem imenno tozi 
hod. T.e. igrata e remi txj kato protiwnika sxshto bi igral takxw 
hod(toj igrae optimalno) i bi ni dowel ewentualno w cikxl.

        Inache za igrite bez cikli mozhe da se polzwa(i dazhe w nqkoi sluchaj 
taka e mnogo po-dobre) i DFS(ne backtrack, a DFS) kato towa e mnogo 
po-lesno za pisane i wxrshi sxshtata rabota samo che trxgwate ne ot 
krajnite situacii a ot nachalnata.
        Slozhnostta i na dwata algoritxma e linejna po broq na situaciite.

        Ta za nashata zadacha e wazhno da razberem kolko sa tezi situacii. Za 
nqkoi igri, wkljuchitelno i edna mnogo podobna na taz(lichno az na 
sxstezanie bih napisal tazi tochno taka)i, ima direktni formuli za 
prowerka dali dadena situaciq e pecheliwsha i ako sa ponosimi(t.e. 
wmestwat se w pametta) da si napishem gorniqt algoritxm ako toj se 
wmestwa wxw wremeto. I tuk se seshtam che ogranicheniqta ne sa 
korektni. Txj kato osnowno procesorno wreme se gubi w nachaloto predi 
pxrwiqt hod za analiz na igrata i situaciite a sled towa samo se 
otgowarq po preizchislenite w nachaloto tablchki. No ne e qsno dali 
wxobshte shte se nalozhi da polzwame gorniqt algoritxm, no wi go 
kazwam, zashtoto e dobre da go znaete wxpreki wsichko

Znam che ne sxm obqsnil kakto trqbwa, no ako imate nqkakwi - pitajte.

Pozdrawi,
        Ivo

-- 
Ivaylo Riskov <ivaylo_riskov@xxxxxxx>

Other related posts: