zanimljiva matematika

[kurdi]

Pazi, sve potezne igre koje se zasnivaju na determinističkim pravilima, a ne na sreći, moraju biti determinističke po svojoj prirodi. To uključuje čak i šah! U prevodu, u šahu sigurno postoji pravilo da beli ili crni pobeđuje ako igra savršeno, samo što je broj kombinacija tako enorman, da čovečanstvo jednostavno nije još došlo do tog odgovora.

cuj, "moraju".svi mi prisutni se oko toga slazemo intuitivno, al ne bi se dokazivalo da je to sto to tako garant mora biti dokaz samo po sebi :)mislim dokaz za ovo tvoj tvrdju bih bio jako iznendajen da postoji.a i generalno ne znam skoro nista o oblasti, pa ne znam recimo da li mozda postoji opsti dokaz da mora tako biti (sumnjam) ali se opet dokazuje konstruktivno i za svaku igru ponaosob.("konstruktivno" ovde koristim slobodno, ne mislim da se dokazuje nuzno tako sto se nalazi pobednicka strategija, ali da se dokazuje u kontekstu konkretnih pravila igre)

Elem, imam ideju kako da ovo dokažem... samo treba malo da ga uobličim.

ajde...mada nisam ja neki ekspert za obaranje tih dokaza... mene mozda i prevaris a da se posle ispostavi da dokaza nema.

[kurdi]

probah ovo da procitam al ne ide...ali jedna zbunjujuca recenica:The classic game Go was influential on the early combinatorial game theory, and Berlekamp and Wolfe subsequently developed an endgame and temperature theory for it (see references). Armed with this they were able to construct plausible Go endgame positions from which they could give expert Go players a choice of sides and then defeat them either wayznaci, ako sam razumeo, mozemo konkretnu poziciju u go-u + standardna go pravila nazvati igrom (svaka pozicija je druga igra). i sad ovi tvrde da su mogli da ponude nekome da bira da li hoce da bude prvi ili drugi i svejedno da ga pobede ma sta da odigra? :zbunj: nravno taj ekspert nije savrsen igrac, ali svejedno... nekao zvuci kao da su ovi bili sigurni u svoju pobedu???

[Al-Khwarizmi]

Ajde da probamo ovako - ako napraviš stablo pretraživanja (prvi nivo tog stabla su svi mogući potezi prvog, drugi nivo svi mogući potezi drugog itd...) listovi tog stabla su ishodi. Pošto mora postojati konačan broj ishoda, to i broj listova mora biti konačan. Grane tog stabla su odluke, to jest potezi. Mesta gde se grane račvaju su čvorovi (listovi su u stvari čvorovi bez grana). Čvor predstavlja stanje na tabli u tom trenutku. Sve grane na jednom nivou stabla pripadaju istom igraču, odnosno od svakog čvora se zna koji igrač nastavlja igru, te možemo označiti čvorove tipa I1 (ako odatle igra prvi igrač) ili tipa I2 (ako igra drugi igrač). E, sad, izaberimo jedan list i krenimo unazad od njega. Neka taj čvor koji smo izabrali znači npr. da je prvi pobednik. To ćemo označiti kao tip P1 (u suprotnom bi bilo P2). Ako grana koja vodi do tog lista pripada prvom igraču, onda je ona ta koju bi prvi igrač izabrao ako mu se ukaže prilika. Ako pak pripada drugom igraču, on će pokušati da je izbegne ako ikako može. U svakom slučaju, povratkom unazad tom granom do prethodnog čvora, njemu označavamo dotičnu granu kao pobedničku za prvog igrača (P1).E. sad ide bitan deo - to uradimo za sve grane koje vode unazad do tog čvora, i za svaku granu označimo da li je P1 ili P2 (ako postoji više nivoa, videćemo kasnije kako se rekurzivno stiže do tog čvora). Ako je čvor tipa I1, a sve grane tipa P2, to znači da mu nema spasa - drugi igrač sigurno pobeđuje, te smo primorani da taj I1 čvor označimo kao P2. U svakom drugom slučaju (ako postoji bar jedna P1 grana) označavamo čvor kao P1. Potpuno je simetrično za I2 čvorove - postaju P2 ako postoji bar jedna P2 grana koja vodi od njega, inače je P1. I najbitniji korak - nastavljamo tako rekurzivno unazad! Ova rekurzija je ujedno i odgovor na pitanje - kako saznati da li je čvor P1 ili P2 ako od tog čvora na neku stranu vodi grana koja ima svoje podgrane.Kada tako unazad stignemo do korena, pošto imamo pokrivene sve moguće slučajeve, koren mora biti ili P1 ili P2. Ako je P1, prvi igrač će jednostavno izabrati jednu od P1 grana i to će mu biti uputstvo kako da stigne do pobede. Ako je pak koren P2, može da odigra bilo šta, jer mu ionako nema spasa. U tom slučaju će igrač 2 pratiti isti algoritam, samo što će krenuti od drugog nivoa, i umesto P1 grana, pratiće P2 grane do pobede.Mislim da je ovaj algoritam ujedno i dokaz, jer zbog konačnog broja listova (i čvorova) za svaki čvor deterministički određuje tip - P1 ili P2.

Edited November 18, 2007 by Al-Khwarizmi

[Al-Khwarizmi]

probah ovo da procitam al ne ide...ali jedna zbunjujuca recenica:The classic game Go was influential on the early combinatorial game theory, and Berlekamp and Wolfe subsequently developed an endgame and temperature theory for it (see references). Armed with this they were able to construct plausible Go endgame positions from which they could give expert Go players a choice of sides and then defeat them either wayznaci, ako sam razumeo, mozemo konkretnu poziciju u go-u + standardna go pravila nazvati igrom (svaka pozicija je druga igra). i sad ovi tvrde da su mogli da ponude nekome da bira da li hoce da bude prvi ili drugi i svejedno da ga pobede ma sta da odigra? :zbunj: nravno taj ekspert nije savrsen igrac, ali svejedno... nekao zvuci kao da su ovi bili sigurni u svoju pobedu???

Da, o tome se i radi. Igrač od krvi i mesa nije mašina, i nema teorije da ne pogreši. Čak i ako igrač izabere pobedničku boju, mašina samo treba da gura algoritam niz stablo po najpovoljnijoj putanji, do prve greške igrača. Jasno ti je da je ova izjava da UVEK može da pobedi igrača teoretski nonsens - šta ako joj suprotstavimo drugu identičnu mašinu?E sad, ponavljam da je i u gou i u šahu broj mogućnosti enorman. Čak ni današnje mašine nisu u stanju da naprave potpuno stablo, te umesto toga koriste razne heuristike. Međutim, ako su heuristike dovoljno dobre, čovek i dalje nema šanse. Edited November 18, 2007 by Al-Khwarizmi

[Al-Khwarizmi]

Kada tako unazad stignemo do korena, pošto imamo pokrivene sve moguće slučajeve, koren mora biti ili P1 ili P2. Ako je P1, prvi igrač će jednostavno izabrati jednu od P1 grana i to će mu biti uputstvo kako da stigne do pobede. Ako je pak koren P2, može da odigra bilo šta, jer mu ionako nema spasa. U tom slučaju će igrač 2 pratiti isti algoritam, samo što će krenuti od drugog nivoa, i umesto P1 grana, pratiće P2 grane do pobede.

Jbg, došao sam dotle da sam sebi repliciram... ;) Ono što sam zaboravio da navedem u algoritmu - ako od nekog čvora I1 postoje i P1 i P2 grane, sve P2 treba precrtati, jer ih igrač 1 sigurno neće izabrati. Za I2 isto važi, samo što se precrtavaju P1 grane. Međutim, ako čvor I1 nema P1 grana, već samo P2, ne možemo ih precrtati, jer nemamo drugih opcija na raspolaganju. Opet, za I2 važi simetrično.Ovo nije bitno za dokaz, ali kad sam već dao algoritam, ajd da ga bar isteram do kraja ;) Edited November 18, 2007 by Al-Khwarizmi

[kurdi]

znam jebiga, to bih i ja ponudio kao dokaz i ja ne vidim rupu, ali prosto ne znam da li stvrano jeste dokaz ili se negde (a ne znam gde) krije nesto sto je zapravo samo nase filozofsko uverenje u determinizam.mislim moze to i krace recima...ako je G(ubitnik) stavio u (1,1) znaci da je morao.znaci da ga je P(obednik) na to primorao.znaci da je pre toga G P-u ostavio mogucnost da ga na to primora, a ne bi to uradio da nije morao.znaci da je pre toga P odigrao nesto sto je G-a primoralo da P-u ostavi mogucnost da ga ovaj primora da...i tako unazad to mora znaciti da je igra detreministicka.jel ti vidis da tvoja verzija sadrzi nesto formalnije od toga?ja u principu ni u ovom kracem ne vidim rupu, isto zvuci uverljivo, samo prosto ne znam da li je dokaz ili nesto propustamo.niti znam sta bi definitivno bio dokaz osim naravno konstruktivnog.niti mi pada na pamet sta bi bio dokaz da neka igra nije deterministicka, ali odsustvo tog dokaza tek nista ne znaci.

[kurdi]

Da, o tome se i radi. Igrač od krvi i mesa nije mašina, i nema teorije da ne pogreši. Čak i ako igrač izabere pobedničku boju, mašina samo treba da gura algoritam niz stablo po najpovoljnijoj putanji, do prve greške igrača. Jasno ti je da je ova izjava da UVEK može da pobedi igrača teoretski nonsens - šta ako joj suprotstavimo drugu identičnu mašinu?E sad, ponavljam da je i u gou i u šahu broj mogućnosti enorman. Čak ni današnje mašine nisu u stanju da naprave potpuno stablo, te umesto toga koriste razne heuristike. Međutim, ako su heuristike dovoljno dobre, čovek i dalje nema šanse.

sve se slazemo (a posebno da je ta recenica nonsens), na nivou uverenja.edit:pardon, ta recenica je nonsens u svakom slucaju, nije stvar uverenja, posto implicira dupli/kontradiktorni determinizam. Edited November 18, 2007 by kurdi

[kurdi]

kako god, da prihvatimo to, jer ja ne vidim kako cemo protiv uverenja oko kojih se slazemo...recimo da postoji deterministicka strategija za opste M x N.jel mozemo da je nadjemo?

[Al-Khwarizmi]

jel mozemo da je nadjemo?

Heh... lakše bi mi bilo napraviti algoritam, nego naći strategiju ručno. :) Verovatno može, ali koliko je lako ili teško - pojma nemam. Probaću.

[Al-Khwarizmi]

Kad sam već potrošio toliko vremena da ispišem algoritam, evo i da ga ilustrujem na primeru 2x2. Kompletno stablo bi na početku izgledalo ovako:A posle primene algoritma ovako:

[Anton]

...

Edited November 18, 2007 by Anton

[Al-Khwarizmi]

U prevodu, u šahu sigurno postoji pravilo da beli ili crni pobeđuje ako igra savršeno

Sad čak sam sebe i demantujem. Nije tačno ovo što sam napisao. Zaboravio sam jednu važnu osobinu šaha, a to je da je jedan od mogućih ishoda pat pozicija. Da nema te treće mogućnosti, citirano bi bilo tačno.

[CPP]

Sad čak sam sebe i demantujem. Nije tačno ovo što sam napisao. Zaboravio sam jednu važnu osobinu šaha, a to je da je jedan od mogućih ishoda pat pozicija. Da nema te treće mogućnosti, citirano bi bilo tačno.

:nitpick: Ne mora da bude pat, moze da bude i remi usled a) nedostatka materijala B ) ponavljanja pozicije 3x Edited November 18, 2007 by CPP

[Al-Khwarizmi]

:nitpick: Ne mora da bude pat, moze da bude i remi usled a) nedostatka materijala B ) ponavljanja pozicije 3x

Tačno, pogrešno sam se izrazio. Mislio sam na bilo koji nerešen rezultat.

[paculla]

al-khwarizmi je u pravu sto se tice search stabla u sahu. mislim da dokaz nema rupu i da se slicna metodologija koristi u formalnim dokazima. probacu da nadjem negde radove na tu temu koje sam davno imala.kad vec spominjete go i sah, ove godine je zavrseno pravljenje search stabla za mice (checkers). ako bismo dosli do punog stabla za sah, sto je vrlo malo verovatno da cemo mi doziveti, da li mozemo nekako pretpostaviti ko pobedjuje u idealnoj igri? mogli bismo reci da logika kaze da bi mogao biti beli, posto ima potez vise (u momentu kad beli matira protivnika, odigrao je jedan potez vise). zamislimo sad obrnuti slucaj. igramo idealnu partiju saha, ali je cilj oba protivnika da izgube (nesto kao samomat u savremenim sahovskim problemima). da li ce tu u prednosti da bude ista strana kao u slucaju igranja na pobedu?[na ovu temu mozemo samo da nagadjamo, da ne kazem - palamudimo]