Nekromanti Jag tycker mig ana en ny trend...

[Troberg]

Re: GO [ot]

Jag tänkte bygga ett sådant träd för spelet Tic Tac Toe på papper, men märkte rätt snart att det blev för jobbigt.

Det föll dig inte in att slå 1*2*3*4*5*6*7*8*9 på en miniräknare först och se att det fanns 362 880 möjliga partier (jag vet, många slutar innan brädet är fullt, men det är en bra fingervisning om att du behöver ett stort papper).

Ganska lätt att lösa på en dator, men inte manuellt.

Om man jämför det med go och 10^700 partier så är det något helt annat. Det är så otroligt mycket att jag inte tror att någon kan komma på någon fysisk företeelse som kan räknas i så stora antal, åtminstone inte i vårt närområde. Då inkluderar jag även sådant som antal molekyler i jorden...

Underskatta inte hur mycket kombinatorik kan ställa till det. Jag har gjort ett program som ska lista ut vilken väg bilar tar genom en korsning. Till min hjälp har jag mätdata från ett antal mätstationer, en i varje ingående och utgående trafikflöde. Från dessa får jag exakt passagetid, riktning, alla axelavstånd, hastighet och typ av fordon. Jag vet hur korsningen ser ut, var mätstationerna är och var köer/väntetider kan inträffa. Trots att jag vet allt detta så tar det ungefär 30-60 minuter att analysera data för ett dygn, och jag lyckas bara koppla ihop 95-97% av de ingående fordonen med ett utgående fordon. Detta trots att det är ett mycket enkelt fall och jag har massor av data om situationen...

 

[Troberg]

Re: GO [ot]

Det enda sätt vi känner till att dela upp talet N i dess primtalsfaktorer är att harva igenom alla kända udda tal n < N/2 och testa om man får en rest i divisionen N/n.

Så kan man ju göra, men det är inte så smart. Smartare är att harva genom alla kända primtal < roten ur N.

Man har väl räknat stora primtal förr (eftersom man inte har någon slumpfunktion i SQL (jag ville sortera efter bland annat slump) så får man fejka det genom att tex dividera ett mycket stort primtal med postens ID och sedan ta ut decimaldelen. Inte riktigt äkta slump, men om man har en packe bra primtal så blir det nära nog, speciellt som slumpfaktorn vara var tredje fältet (om jag minns rätt) som sorterades på. Ibland bara hatar man SQL...

 

[Troberg]

Re: minst 10 drag i förväg [OT/ANT]

"Och med 3^(19x19) möjliga states per drag så blir det helt enkelt för mycket för en dator att syssla med det."

Inte nog med det. Dom flesta prospelarna läser minst tio drag in i spelet, inte bara tre

Trean är inte för antalet drag i förväg. Formeln ger antalet möjliga uppställningar på brädet, det vill säga ögonblicksbilder. Tre är antalet möjliga tillstånd per kryss (vit, svart, tom).

Detta för att visa för Rising att det är en övermäktig uppgift att lösa även om man bara försöker bygga upp en lista med bräden och nästa drag.

Naug, som spelar Go varje måndag på Uppsala Go-klubb

Själv föredrar jag Go-cart.

 

[anth]

Re: GO [ot]

Jag tror du överdriver lite. Dels tror jag att datorerna kommer att slå människan i go, dessutom inom ett decennium eller två, dels tror jag att du överdriver hur datorerna behöver se ut.

Jag har för mig att det är Moores lag som säger att datorkapaciteten dubblas på 18 månader.
För att en dator ska kunna räkna med ytteligare ett drag längre fram i Go krävs det c:a 10 års datorutveckling.

När det gäller teknologier så skulle jag säga att neurala nät låter som en trevlig kandidat. De har en viss mönsterigenkänningsförmåga som liknar vår och kan lära sig på egen hand genom att spela mot bra spelare. På grund av djupet som man måste undersöka för varje drag så är annars trevliga metoder som genetiska algoritmer inte möjliga (men de funkar rätt bra i schack, där man oftast ser om ett drag är värt att prova efter 3-5 drag).

Låter som en bra kandidat - säg mig, när kommer de i serieproduktion?
(jag tvivlar på att de kommer inom de närmaste 20 åren)

 

[Troberg]

Re: GO [ot]

Jag har för mig att det är Moores lag som säger att datorkapaciteten dubblas på 18 månader.

Nja, egentligen är det antalet trissor per kvadratmillimeter, men i praktiken är det detsamma.

Den håller dessutom rätt bra för hårddiskar (1 TB-diskar inom 3 år! Yay!) och minnen.

För att en dator ska kunna räkna med ytteligare ett drag längre fram i Go krävs det c:a 10 års datorutveckling.

Detta under förutsättning att Moores lag håller, vilket jag inte tror att den kommer att göra så länge till. Kanske tio år, möjligen tjugo, men sedan så börjar fysikaliska begränsningar som är ganska definitiva att bli ett problem (molekylstorlek, ljushastighet osv).

Låter som en bra kandidat - säg mig, när kommer de i serieproduktion?

Neurala nät finns redan idag och används och fungerar i många olika sammanhang (teckenigenkänning, väderprognoser, taligenkänning med mera), sök på Artificial neural networks. Vet inte om de tillämpats på go. Nackdelen med dem är att "tanken" i dem är dold och det finns ingen garanti för en bästa lösning.

Genetiska algoritmer finns också och används i många sammanhang. Det typiska exemplet är att finna en optimal resväg. Man slumpar då ett antal olika resvägar (tex 1000), väljer ut de bästa (tex 100). På var och en av dessa hundra slumpar man några mindre variationer (så att man får tusen nya varianter). Av dessa väljer man de bästa och slumpar fram nya med ännu mindre variationer från dem. Osv.

De är enkla att göra, kommer otäckt fort fram till en bra lösning, men garanterar inte att bästa lösningen hittas.

Båda dessa metoder innebär dock att man måste ha ett sätt att mäta vad som är "bra", vilket är långt ifrån uppenbart i go, eftersom "bra" inträffar långt senare, påverkat av en massa andra drag.

 

[Rising]

Re: GO [ot]

"Det föll dig inte in att slå 1*2*3*4*5*6*7*8*9 på en miniräknare först och se att det fanns 362 880 möjliga partier "

Jag tänkte mer än så. Jag tänkte att det bara fanns tre sätt att börja på (mittruta, sidoruta, hörnruta) vilka därefer förgrenade sig i 12 (5 för sidoruta och hörnruta, men bara 2 om man börjat i mitten) möjligheter i andradraget, och därefter kan man ju ganska snabbt konstatera saker som att nästan varje följande drag tvingar motståndaren att sätta någonstans för att blocka, vilket ju drar ner antalet möjliga partier mellan två spelare som inte tillåts göra några misstag till ett väldigt litet antal. Jag har exempelvis kunnat konstatera att om jag börjar på en hörnruta och du därefter sätter en ring i någon annan ruta än i mittenrutan, då har jag redan vunnit (om jag vet vad jag håller på med, alltså. Det räcker med två till drag för mig, och sedan har jag dig i matt).

Så, så länge man tvingar spelarna att lägga där de oundvikligt -måste- lägga något för att inte förlora, och om man struntar i att bena ut alla olika möjligheter av remi från det att man sett att partiet omöjligtvis kan vinnas av endera parter, då tänkte jag faktiskt att det i allra högsta grad skulle gå att genomföra.

Det vara bara liiite för jobbigt för mig, men jag kommer göra det en vacker dag.

"Om man jämför det med go och 10^700 partier så är det något helt annat."

Vilket alltså är helt fel utgångspunkt i mina ögon. Jag tror att man ska börja med att knäcka Go på ett litet 5 x 5 bräde, typ. Sedan gå vidare med att knäcka det för 6 x 6 rutor. Vad ser man för skillnader? Sedan, när man ska knäcka det för 7 x 7 rutor, då kan man säkert redan i ens algoritm strunta i stora delar av trädet som man på förhand vet är dömda att missslyckas, efter att ha analyserat tidigare lösningar. Man kan säkert också döma ut partier direkt efter att någon har lidit stora förluster på brädet; det är ju inte som schack där man kan ligga under hur mycket som helst för att ändå slutligen vinna med ens sista bonde. I Go minskar ens chanser dramatiskt efter varje litet nederlag. När man sedan fortsätter med att knäcka det för 8 x 8 rutor så tror jag att man kommer märka att den snabbaste lösningen mot en motståndare som försöker förlora så lite som möjligt kommer att följa en sorts symmetriskt mönster som fokuserar på maktkampen kring hörnen och sidorna, när man analyserar dessa matematiskt kommer man sedan att greja det, och kunna framställa en lösning som funkar på alla sorters bräden, oavsett hur stora de är.

Återigen, bara min gissning, men jag tycker det verkar enklare att fokusera på spelet Go's svagaste och mest lättanalyserade sidor, än att drunkna i antalet möjliga sorters partier. Det gäller ju att hitta möjligheter att skära bort delar av trädet, inte att stå och titta över dess friljoners olika grenar och säga "omöjligt!"

Frågan är bara hur man kan skära bort "dåliga" grenar och strunta i att analysera dem så tidigt som möjligt i trädet.

/Rising

 

[Troberg]

Re: GO [ot]

Jag tänkte mer än så. (snip)

OK, låter vettig, om än fortfarande ogörligt om man ska göra det manuellt.

Jag tror att man ska börja med att knäcka Go på ett litet 5 x 5 bräde, typ. (snip)

Jag har också funderat i de banorna, men konstaterade ganska snart att man måste beakta hela brädet i varje given situation. Genast är man tillbaka i början igen. Jag funderade också på delvis överlappande grids av mindre bitar, där varje grid kan klassas som olika säker, men även det verkar inte hålla, åtminstone inte om man ska spela bra.

Det som gör go svårt är i första hand den långa tiden mellan ett drag och möjligheten att bedöma dess effekt.

 

[Dimfrost]

Re: GO [ot]

Om man jämför det med go och 10^700 partier så är det något helt annat. Det är så otroligt mycket att jag inte tror att någon kan komma på någon fysisk företeelse som kan räknas i så stora antal, åtminstone inte i vårt närområde. Då inkluderar jag även sådant som antal molekyler i jorden...

Det finns ungefär 10^80 elementarpartiklar inom Hubbleradien för ett universum (alltså en sfär med 15 miljarder ljusårs radie, ungefär: allt man kan betrakta). Så 10^700 är ganska mycket, helt enkelt.


/Dimfrost

 

[Troberg]

Re: GO [ot]

Det finns ungefär 10^80 elementarpartiklar inom Hubbleradien för ett universum (alltså en sfär med 15 miljarder ljusårs radie, ungefär: allt man kan betrakta). Så 10^700 är ganska mycket, helt enkelt.

Jag skulle dessutom sträcka mig till att ta till kraftuttryck och säga attans mycket!

Tänk dessutom på att varje extra tre nollor ökar radien med tio gånger (det stämmer väl? Volymen ökar med med kubikroten av radiens ökning?).

Vilken stackare är det som har suttit med pincett och räknat elementarpartiklarna? Var det han som blandade ihop fot och meter och dumpade marssonden som fått det som straffarbete?

 

[Black Dwarf]

Var du verkligen den enda som kunde genomskåda mig och förstå att jag med rollspel egentligen menar sexlekar..? Jag som trodde att det fanns nån intelligent människa här, eller årminstone några galna människor som försöker tolka/misstolka allt och gärna hitta konspiration hela tiden(om dom sen finns är en annan fråga...)

Hoppas att du inte tog illa vid dej. Jag försökte placera in en -smiley där för att det skulle se ut som det skämt som det var menat som. Om du tog det som något annat ber jag ödmjukast om ursäkt.

/BD, lite konfunderad.

 

[Troberg]

Hoppas att du inte tog illa vid dej. Jag försökte placera in en -smiley där för att det skulle se ut som det skämt som det var menat som. Om du tog det som något annat ber jag ödmjukast om ursäkt.

Jag tolkade som att du försökte göra en sexuell invit mot honom.

Kul att du är tillbaka förresten!

 

[King Kromm]

Nej nej nej...

Inte ens nära något sådant, kunde bara inte låta bli att ge ett halvflummigt svar, hoppas inte att det lät illa? Var iaf inte tänkt så... Och jag hoppas nästan att Troberg iaf hade fel...?

Om inte annat så för att jag har massa på g. och inte riktigt tid med sånt just nu!

 

[hraufnir]

Re: GO [ot]

Detta kanske har skrivit nedan, eftersom jag inte idas läsa neråt innan jag svarar...
men jag anser att det i spel som Go, Shack, Backgammon handlar om att lära sig bemästra motståndaren och inte spelet i sig. Man bemästrar spelet shack när man vet hur pjäserna går, man bemästrar motståndaren när man vet hur man skall flytta pjäserna. Det är iaf min åsikt

 

[Rising]

Re: GO [ot]

"jag anser att det i spel som Go, Shack, Backgammon handlar om att lära sig bemästra motståndaren och inte spelet i sig. Man bemästrar spelet shack när man vet hur pjäserna går, man bemästrar motståndaren när man vet hur man skall flytta pjäserna. Det är iaf min åsikt."

Anledningen att man kan tycka det, är för att vi ännu är så långt ifrån att bemästra spelet. Spelen I SIG har ju inga som helst psykologiska egenskaper (vilket däremot poker har (ett psykologiskt spel måste handla om att motståndaren kan göra dolda drag som man får gissa sig till)), så den psykologiska biten funkar bara när båda spelare spelar "dåligt", alltså om de ännu inte lärt sig att bemästra spelet.

När väl det har gjorts, så finns det varken någon psykologi eller spelskicklighet kvar att tala om: Det kommer att bli som Nim eller Tic Tac Toe; spel som slutar att vara spel. (Ingen vinner någonsin i Tic Tac Toe, så länge som båda har bemästrat spelet)

/Rising

 

[Krille]

Re: GO [ot]

"När väl det har gjorts, så finns det varken någon psykologi eller spelskicklighet kvar att tala om: Det kommer att bli som Nim eller Tic Tac Toe; spel som slutar att vara spel. (Ingen vinner någonsin i Tic Tac Toe, så länge som båda har bemästrat spelet)"

...och hur var det med rollspel som man inte vinner i nu igen?

Men okej, jag köper väl idén att go slutar att vara intressant när det är bemästrat. Kruxet är att det inte är bemästrat, och inte kommer att vara det på rätt lång tid framöver och defintivt inte av människor, så jag ser inte problemet annat än en obstinat fixering vid idén att något som kan bli bemästrat någon gång i framtiden är tråkigt.

 

[Rising]

Re: GO [ot]

"jag ser inte problemet annat än en obstinat fixering vid idén att något som kan bli bemästrat någon gång i framtiden är tråkigt."

Jag har ju bara skrivit det någon enstaka gång att spelet skulle bli tråkigt när det väl bemästrades, det är inte min poäng. Poängen är att det kan bemästras, och att det är betydligt enklare än vad det ser ut när man räknar ut hur många möjliga olika partier det finns. Jag är nästan klar med min fullständiga genomgång av Tic Tac Toe på papper, och då har jag ändå använt en extremt olämplig metod för arbetet (jag fortsätter att bena ut delar av trädet som jag redan konstaterat att de kommer klippas bort så fort jag börjar ansa trädet med min matematiska modell). Jag har ju redan bemästrat spelet för länge sedan, när jag var liten, och vet att ett parti aldrig kan sluta på annat sätt än oavgjort om båda spelar så bra det går. Om man skulle jobba effektivt och ha en dator till hjälp så skulle man alltså kunna skära bort flera miljontals olika möjliga partier på ett hyffsat avancerat spel på nolltid.

Jag tycker snarast att det finns en obstinat fixering vid att mystifiera den mänskliga förmågan att spela spel: Alla pratar om att man måste bygga helt nya sorters datorer för att ens ha en chans att mäta sig med den mänskliga hjärnans förmåga att tolka ett spelbräde, och man försöker verkligen klamra sig fast vid föreställningen om att vi människor fortfarande har en förmåga som inte kommer kunna ersättas av datorer inom en överskådlig framtid, tills att vi fått kvantdatorer och alla möjliga sorters knasiga tokigheter, att man måste analysera motståndaren psykologiskt osv. Jag är mer krass och konstaterar demystifierat att det är tur att programmerare är så lökiga, eftersom vi annars hade varit omkullsprugna på detta område också.

Jag tycker förresten personligen att det är mycket intressantare att se hur man bäst lär en dator att spela poker. Eller rollspel. Hur lär man en dator samberätta en historia? DET är en uppgift som det kommer att krävas tokigt avancerade datorer för att klara. Go är som en smygande myggfjärt i sammanhanget.

/Rising

 

[Troberg]

Re: GO [ot]

Jag är nästan klar med min fullständiga genomgång av Tic Tac Toe på papper, (snip) Om man skulle jobba effektivt och ha en dator till hjälp så skulle man alltså kunna skära bort flera miljontals olika möjliga partier på ett hyffsat avancerat spel på nolltid.

Nej, en dator skulle inte kunna kapa bort miljontals partier, det finns mindre än 362 880 möjliga partier (många av dem slutar innan brädet är fullt, så det blir inte så många).

Jag tycker snarast att det finns en obstinat fixering vid att mystifiera den mänskliga förmågan att spela spel: Alla pratar om att man måste bygga helt nya sorters datorer för att ens ha en chans att mäta sig med den mänskliga hjärnans förmåga att tolka ett spelbräde, och man försöker verkligen klamra sig fast vid föreställningen om att vi människor fortfarande har en förmåga som inte kommer kunna ersättas av datorer inom en överskådlig framtid, tills att vi fått kvantdatorer och alla möjliga sorters knasiga tokigheter, att man måste analysera motståndaren psykologiskt osv. Jag är mer krass och konstaterar demystifierat att det är tur att programmerare är så lökiga, eftersom vi annars hade varit omkullsprugna på detta område också.

Dagens datorer kan slå människan i de flesta spel eller är nära att göra det. Det var egentligen inte det som var frågan, frågan var om de kan bli oslagbara, dvs automatiskt vinna alla partier.

Jag tycker förresten personligen att det är mycket intressantare att se hur man bäst lär en dator att spela poker.

OK, där har vi ett spel som datorer är riktigt usla på, och antagligen kommer att fortsätta vara ett tag.

 

[Rising]

Re: GO [ot]

"Nej, en dator skulle inte kunna kapa bort miljontals partier"

...app app! Jag skrev att en dator skulle "kunna skära bort flera miljontals olika möjliga partier på ett hyffsat avancerat spel på nolltid". Inte Tic Tac Toe, utan ett hyffsat avancerat spel som är är för svårt att knäcka för någon människa.

...men nu är vi alldeles för mycket OT, och inget vettigt har sagts i Go-frågan på de senaste inläggen. Jag sammanfattade ju egentligen allt som överhuvudtaget var värt att säga om saken redan med mina första, i vanlig ordning, genialiska och uttömmande inlägg.

Sedan kan vi bara gissa om vad som händer. Är Go ett spel som Tic Tac Toe; som ingen kan vinna om båda spelar så bra som möjligt, eller är det så att vit/svart är predestinerad att vinna varenda match om båda vet vad de håller på med? Vem är det i så fall som vinner, vit eller svart?

/Rising

 

[kefka]

Re: GO [ot]

Ok, kanske ska lägga mig i diskussionen lite eftersom jag spelar både schack och GO, schack har jag tränat och tävlat i snart 10 år.

är Go ett spel som Tic Tac Toe; som ingen kan vinna om båda spelar så bra som möjligt, eller är det så att vit/svart är predestinerad att vinna varenda match om båda vet vad de håller på med ?

Nej, Go kan aldrig bli oavgjort, den finns en regel, komi, som gör att vit får 5,5 extra poäng, efter som det är en nackdel att lägga tvåa. Både i schack och Go har den som börjat en stor fördel, desto högre nivå man spelar på desto större betydelse. Men schack blir givtivs oavgjort om bägge spelar helt korretkt.

Go dator är mycket sämre än schack datorer därför att det på ett 19x19 bräde finns betydligt fler möjliga drag än på ett ett 8x8. Fast problemet som alla datorer har är att fast de är väldigt bra på att räkna varianter så har de problem med positions och spelkänslan, de måste helt enkelt räkna fram vilken ruta en pjäs står starkast på.

 

[kefka]

Re: GO [ot]

jag tror att man ska börja med att knäcka Go på ett litet 5 x 5 bräde, typ. (snip)



Jag har också funderat i de banorna, men konstaterade ganska snart att man måste beakta hela brädet i varje given situation. Genast är man tillbaka i början igen. Jag funderade också på delvis överlappande grids av mindre bitar, där varje grid kan klassas som olika säker, men även det verkar inte hålla, åtminstone inte om man ska spela bra.

Det som gör go svårt är i första hand den långa tiden mellan ett drag och möjligheten att bedöma dess effekt.

Tja ett 5x5 bräde borde ha ett ganska så forcerat resultat. Sen är det ju ganska interesassant med att "dela" upp brädet i mindre delar, men då måste man ändå få med stegar osv. Sen hur ska man få datorn att han förstå att han faktiskt förlorar på att kriga på och vinna territorium i en del av brädetm jämfört med vad han skulle tjänat på att vinna inflytande i ett annan del?