Computer-go/internet-go
1


Daniel Paraschiv (8 octombrie 2001, reactie la Sorin Gherman, a reactionat Sorin Gherman) :

Tweedie asta nu a fost in stare sa faca IGS-ul sa numere corect o partida terminata.
Partida atasata am jucato ieri pe IGS, eu alb si rezultatul dat de catre IGS a fost 90.5 pentru alb si 100 pentru negru. Cred ca nu a numarat grupul din dreapta sus asa ca victoria s-a pus pentru negru.
Daca un batran capcaun nu a putut face un program sa numere punctele la sfarsitul unei partide, atunci nu stiu cine ar putea sa faca un program sa joace de 1D*


Sorin Gherman (8 octombrie 2001, reactie la Daniel Paraschiv, ai reactionat Dan Micsa si Daniel Paraschiv) :

Nu m-am uitat pe partida, dar din ce zici tu deduc ca nu ai ridicat toate grupurile moarte la sfirsitul partidei (manual adica), nu?
Serverul IGS nu se prinde automat de ce grupuri sint moarte, presupune ca
toate grupurile traiesc cind incepe el numaratoarea.
E foarte greu de facut un numarator automat, stie cineva de asa ceva?


Dan Micsa (8 octombrie 2001, reactie la Sorin Gherman, a reactionat Sorin Gherman) :

Dupa cunostiintele mele cel mai bine numara HandTalk foarte rar se incurca.
Parese ca si Many face of Go in ultimele incarnari descopera corect grupurile vi si moarte.

Apropo are cineva un Many Face of Go V10 is tare curios de el da nu's curios sa ma usurez de vo 100 de dollari.

Respect,
Un cititor retras


Sorin Gherman (8 octombrie 2001, reactie la Dan Micsa, a reactionat Dan Micsa) :

(a reactionat Dan Micsa)

Bineinteles ca daca situatia e clara (fiecare grup are ochi vizibil, sau nu are ochi, tot vizibil) se poate incropi o numaratoare, dar daca situatia finala e mai complicata (semeaiuri) nici nu exista (cred) algoritm sa gaseasca grupurile vii si moarte corect.

(a reactionat Dan Micsa)

Eu unul nu mi-as lasa rezultatul partidei la mila unui numarator d-asta automat :)


Dan Micsa (8 octombrie 2001, reactie la Sorin Gherman, a reactionat Sorin Gherman) :

(reactie la Sorin Gherman)

Imi pare rau (sau chiar bine) sa te contrazic aici sunt algoritmi care sunt
capabili sa citeasca corect viatza si moartea grupurilor. Pentru asta
analizeaza un ptic capabilatatziile programelor de azi si studiaza Computer
Go o sa vezi ca se cam fac progrese in domeniul asta.

(reactie la Sorin Gherman)

Asta'i pararea ta de adzi mai vorbim in 5 ani despre asta ma tot gindesc cu
mila la bietul Kasparov cind scriu acum.


Sorin Gherman (8 octombrie 2001, reactie la Dan Micsa, a reactionat Dan Micsa) :

Si mie mi-ar pare tare bine sa si vad un algoritm din asta, care anume dindu-se o pozitie pe care 2 jucatori o considera incheiata, sa numere punctele.

Problema e, cum am zis, sa decida ce grupuri traiesc si ce grupuri nu. Pentru asta, la modul foarte general, nu cred ca exista un algorithm care sa merga in timp rezonabil (anume fara sa faca backtracking, analizind muncitoreste toate posibilitatile de joc).
Programele existente sint sigur ca merg pentru pozitii "normale", adica cele ce apar in mod curent.

Apropo de asta, Marcel chiar a demonstrat ca dindu-se o scara, rezolvarea problemei "cine cistiga scara" nu este rezolvabila cu algoritmi eficienti.

Mi-ar parea tare bine sa ma insel, si sa ma contrazici cu un exemplu mai concret :)


Dan Micsa (8 octombrie 2001, reactie la Sorin Gherman, a reactionat Sorin Gherman) :

(a reactionat Sorin Gherman)

  • Problema rezolvari scari poate fi rezolvat (dupa umila mea parere) in timp linear(!) proportional cu lungimea scari punind o singura, simpla conditzie de prunare - minimazarea numarului de libertatzi in fiecare pas.
    Dupa cite bine imi amintesc cind am scris asta in pascal acu vreo 10 ani pe un 286 treaba asta nu tinea mai mult de 1 secunda pentru scari destul de intoarse si complicate. Asa copacul variatilor ii in realitate un falnic si simplu "plop" in cazul asta.

Acum rezolvarea problemei cu grupuri vi si moarte ii asa cum ai remarcat un pic ii mai "pom fructifer" din punct de vedere al variatilor si bineinteles nu'i asa de trivial de implementat. Fi sigur ca ii un algoritm de gen min-max care necesita backtracking sau backtracking-simulat nu se prea poate sa-l rezolvi printro simpla scanare bidemensionala a tablei. Problemele complexe de seki sau semeaiuri complexe nu pot fi citite dintr'una fara a recurge si analiza toate combinatziile RELEVANTE.

(a reactionat Sorin Gherman)

Cred ca am citit despre genelul asta de algoritmi pe'undeva da nu ma intreba pe unde ca nu mai stiu.

respect
Billator out


Sorin Gherman (8 octombrie 2001, reactie la Dan Micsa, a reactionat Dan Micsa)) :

(reactie la Dan Micsa)

  •    Ah, unde umbla Marcelica ala, e iar dupa japonezoaice, de nu zice nimic?
       Marcel a pus mai demult pe lista o problema de genul asta, adica

    (a reactionat Dan Micsa)
    • "nerezolvabila cu calculatoru'". (Daca nu stii care, probabil ca umblai dupa englezoaice in timpul ala :)) ).
   Marceeeeeeel??

(reactie la Dan Micsa, a reactionat Dan Micsa)

   Ba uite ca-s nesimtit si te intreb! :))


Dan Micsa (8 octombrie 2001, reactie la Sorin Gherman, a reactionat Robert Mateescu) :

(reactie la Sorin Gherman)

Cind eram mai tinar ma purtam mai ca omu.

Acu intradevar am cam imbatrinit si ma intereseaza mai mult problemele existetiale ca Goul spre exemplu.

(reactie la Sorin Gherman)

  • bine intreaba ma
    :)

salut

P.S. Poate ma uit dupa ceva documentatzie da nu promit.

(a reactionat Robert Mateescu)

P.S.2 Ma intereseaza problema aia de scara


Robert Mateescu (8 octombrie 2001, reactie la Dan Micsa, a reactionat Dan Micsa, II) :

(reactie la Dan Micsa)

draga billator,

un exemplu de problema de'a lui marcel gasesti in mesajul 3360, de unde poti destul de usor sa vezi ca e greu sa rezolvi scara aia liniar.


Dan Micsa (8 octombrie 2001, reactie la Robert Mateescu) :

multzam mestere,

dau cu ochiu ASAP

billator out


Dan Micsa (8/9 octombrie 2001, reactie la Robert Mateescu, a reactionat Robert Mateescu) :

Deci io zic ca scara in go se poate rezolva cu un algoritm recursiv cu comportare liniara (asta nu inseamna ca nu exista sau nu pot exista citeodata alte ramuri!) insemna ca comportamentul lui e preponderent este liniar.
Si ca in general pentru ai calcula timpul de rulare il calculezi cu o relatie liniara. Mai mult de atit este liniar cu lungimea tablei (sau a scarii) si nu cu numarul de punte de pe tabla si asta'i destul de important pentru ca nu are comportament exponential nici(si)cum! Acum potzi sa'i dai dimensiuni (aproape) fractale si sa tot cirmesti scara ca o suprafata mai mare te lasa sa cirmesti mai mult dar orisicum o sa vezi ca in general comportamentul linear primeaza.

Acum io nu zic ca nu se pot imagina probleme de go care sa fie complicate da nu vad cum influenteaza problemele astea algortimu' ast' mic si umil al scarii in sine care este influentzat doar de numarul de libertatzi ale lantzurilor care ating scara si de lantzu care fuge.

Io dzic ca noi ne "certam" acilea pe doua probleme diferite io incerc sa rezolv scara care ca rezultat poate avea ca raspuns un da sau ba (+ eventual o lista de lantzuri active + numarul lor de libertatzi pentru cache probabil) iar tu vorbesti despre scari care ating acelasi lantz si'i descresc numarul de libertatzi deci normal.

Respect


Andrei Cseh (8/9 octombrie 2001) :

Daaaaaaa,
Probleme complicate astea cu calculatoru'.
Da' chestia aia existentiala mi-a placut.
Mai vreo cateva si poate punem de o culegere folclorica.
Folclor autohton de Go, bineinteles, poate si ceva manele.
Sau manivele.

Scuzati-ma, sunt obosit,

In consecinta, draga billator, daca cinstesti tu, cinstesc si eu.
De nu ma mai intelegeti, dati un semn si ma duc la culcare.


Daniel Paraschiv (9 octombrie 2001, reactie la Sorin Gherman) :

Eu folosesc pe IGS "The Go Assistant Version 2.0" si nu stiu daca are numaratoare manuala, nu am vazut la el asa ceva. Am folosit comanda score piesele de la el din teritoriu au fost marcate apoi si cele de la mine din teritoriu cu exceptia piesei 1 din teritoriu din dreapta sus, am mai stat putin apoi am dat comanda done si m-am trezit ca afiseaza cu 23 de puncte mai putin. Am incercat sa vorbesc pe tell cu respectivul dar nu mai era logon. Probabil daca dai repede score apoi done si iesi din retea nu se numara bine pentru adversar. De exemplu cu client-ul meu daca dau sign off in timpul jocului, atunci partida nu se pune pentru nimeni, se amana automat fara acordul adversarului (Am descoperit asta cand jucam cu cineva aveam in fata si de odata ma trezesc ca adversarul doreste sa amanam partida eu nu am vrut, a dat de cateva ori comanda adjourn eu ii raspundeam No, dar cand a iesit din IGS mi-a aparut un mesaj ca partida a fost adjourned) Am dat de cateva ori "sign off" la inceput pe un alt cont cand vedeam ca nu pot sa castig (caci si altii imi facusera mie lafel :) ), dar dupa aceea mi-am spus ca nu am nimic de pierdut daca pierd o partida, este meritul adversarului, asa ca nu am mai dat sign off deloc. Cand m-am confirmat 5k*,de la 4k, tot asa un 6k* m-a batut pe nedrept ne fiind o numaratoare corecta. Cand eram in jur de 7k* era moda sa se intrerupa partida si sa nu se puna pentru nimeni, acum vad ca se poate castiga pe nedrept.
Pe Baduk(go) server - www.dashn.com clientul ridica toate grupurile moarte la sfirsitul partidei prima data automat si apoi pot sa le dau manual daca vad ca nu s-au ridicat toate grupurile, pe IGS nu am vazut un client care sa ridice grupuri si manual.


Robert Mateescu (9 octombrie 2001, reactie la Dan MIcsa, au reactionat Dan Micsa, ) :

Cred ca exemplul la care te-am trimis nu e cel mai nimerit. Unul mai bun gasesti la

http://www.cwi.nl/~tromp/img/ladders.gif

O sa constati (surprins), ca algoritmul mic nu merge liniar in dimensiunea tablei. Mai exact, o sa vezi ca si albul, cel care e luat in scara, are optiuni, nu numai negrul ...
Il astept pe Marcel sa te lamureasca mai bine, ca el s-a tot ocupat de
asta.


Dan Micsa (9/10 octombrie 2001, reactie la Robert Mateescu, au reactionat Daniel Maniov si Marcel Crasmaru) :

Acuma tu vrei sa'mi dai dreptate cu tot dinadinsu' nu? :)

De mai citesti odata raspunsul o sa vezi ca tzam raspuns exact la scari de genul asta. Am si reamintit ca poate avea o variatzie un ptic mai fractala adica nu'i chiar liniar ci poate ajunge de complexitate lungimea ^ (1.1 - 1.3) din cauza ca potzi sa o cirmesti de mai multe ori daca tabla e mai mare dar in general comportamentul asteptat al algoritmului (io zic) ca poate fi considerat linear. Si mai mult de atit in cazuri reale cind 99% din scari is mai ortodoxe devine liniar de tot poate fara nici o ramificatie semnificativa.

Reamintesc ca virgula cam totzi algoritmi din computing go sunt recursivi nu prea am multe contra exemple probabil unul ar fi cel de numarare al libertatzilor care se face prin baleire si marcare intr'un container asociativ ce poate fi dens (recomandabil) matrice bidimensional cu booleani sau sparse hash table altul bazat pe baleiere ii creerea containarului cu lantzuri inconjuratoare.

Acum s'ar putea citeva josekiuri sau getauri sa fie cacheate si comparate direct cu paternuri predefinite pentru a pruna recursivitatea dar astea sunt doar tehnici de prunare si nu schimb problematica computer goului in general.

(au reactionat Marcel Crasmaru si Constantin Ghioc)

  • Io dzic sa ne concentram mai bine in algoritmi de prunare a problemelor de tsume go caci acolo comportamentu' polinomial ii bezerk rau si orice contributie in domeniu poate fi semnificativa.

Ce spunetzi ii un subiect interesant?

Respect


Daniel Maniov (9/10 octombrie 2001, reactie la Dan Micsa, au reactionat Dan Micsa si Marcel Crasmaru) :

Da, e un subiect interesant... pentru programatori :)
Pentru noi "astialalti" e insa un subiect cam || ...


Dan Micsa (9/10 octombrie 2001) :

Ai scuzele mete.


Marcel Crasmaru (11 octombrie 2001, reactie la Daniel Maniov si Dan Micsa, a reactionat Calin Morariu) :

Imi cer scuze ca raspund tarziu la interpelare, dar a trebuit sa ma reabonez la rgo mai intai :)

Subiectul nu e interesant cred numai pentru programatori. Jucatorii de Go au auzit sigur de proverbul ca: "Daca nu poti calcula o scara, lasa-te de go", sau asa ceva. In timp ce proverbul e adevarat pe o tabla normala (19x19), pe table mari NU e la fel. In nici un caz timpul de calcul al unei scari nu e LINIAR in dimensiunea tablei, ci cel mai probabil EXPONENTIAL. Mai precis, exista
pozitii in care sa decizi daca o scara merge sau nu, necesita analizarea unui numar exponential de pozitii.

Pentru toti cei interesati de ce e asa, la sfarsitul paginii de web

http://www.cwi.nl/~tromp/go.html

se poate down-load-a in format postscript articolul "Ladders are PSPACE complete", pe care l-am scris impreuna cu John Tromp.

(a reactionat Calin Morariu)

Daca ins cineva vrea explicatii mai detailate, scrieti-mi pe adresa

crasmarum@yahoo.com,

sa nu aglomeram lista rgo cu subiecte paralele cu Go-ul, totusi:)

Toate cele bune,


Calin Morariu (11 octombrie 2001, reactie la Marcel Crasmaru, a reactionat Marcel Crasmaru) :

(reactie la Marcel Crasmaru)

Cum lista e destul de libera in zilele astea si o buna parte din utilizatori sunt si programatori, eu zic ca nu strica ca subiectul sa continue pe lista


Vezi parte 2


Top
Modificari
Index de partide, teorii si probleme de go