Gå till innehåll

Vem kan slå Filip och Fredrik: Först till 40


Recommended Posts

  • Svars 52
  • Created
  • Senaste svar

Top Posters In This Topic

Jag får det till att den enda informationen som borde vara relevant för en gto-strategi är fryst poäng, nuvarande poäng och motståndarens poäng (alltid fryst). Vilket för en spelare ger 40*(40 + 39 + 38 + ... + 1) = 32800 möjliga tillstånd att ta hänsyn till.

 

Nuvarande poäng kan inte vara högre än 40 - fryst poäng.

Länk till kommentar
Dela på andra webbplatser

hur definierar du en strategi?
En lista med ett beslut om att frysa eller slå en tärning för varje möjligt speltillstånd. I mitt exempel skulle det alltså i princip vara en lång radda ettor och nollar samt någon metod att koppla varje speltillstånd till rätt del av raddan.

 

Sen är det ju förstås möjligt att en strategi går att beskriva mycket kortare än så på något annat sätt. Men en sån specifikation borde göra det möjligt att antingen bruteforcea en exakt lösning eller åtminstone approximera utan att det krävs särskilt mycket mänsklig ansträngning.

 

Nuvarande poäng kan inte vara högre än 40 - fryst poäng.
Jag kollade inte så noga, men är rätt säker på att jag fick med det, den bifogade uträkningen var bara slutklämmen. Fick du något radikalt annorlunda resultat?

 

Det borde väl vara i rätt härad iaf iom att 40*40*40 = 64000.

 

Sen blir det ju en del extra iom att regeln tydligen inte var först till fyrtio, utan den som har högst den runda som någon fryser på 40+.

Länk till kommentar
Dela på andra webbplatser

Jag håller med hjort bortsett från det faktum då att man enligt videon inte måste stanna på 40 vilket gör tillstånden oändligt många i teorin. De tillstånd där man fortsätter att slå trots att man har över 40 blir dock mindre sannolika.

 

hur definierar du en strategi?

 

En strategi borde ju kunna definieras som att slå eller banka givet tillståndet, förutsatt omixade strategier.

 

Nuvarande poäng kan inte vara högre än 40 - fryst poäng.

 

I videon har Herngren 40 och får välja att fortsätta slå vilket borde falsifiera ovanstående.

 

Återkommer med förslag på lösning =)

 

Edit: Hjort var snabbare

Länk till kommentar
Dela på andra webbplatser

En lista med ett beslut om att frysa eller slå en tärning för varje möjligt speltillstånd. I mitt exempel skulle det alltså i princip vara en lång radda ettor och nollar samt någon metod att koppla varje speltillstånd till rätt del av raddan. Sen är det ju förstås möjligt att en strategi går att beskriva mycket kortare än så på något annat sätt.

 

en strategi definieras alltså som en mängd ettor och nollor, en för varje tillstånd = 2^32800 möjliga strategier, eller missar jag något nu?

Länk till kommentar
Dela på andra webbplatser

hur bruteforcear vi ens lösningen om vi kör till ett?

 

eller, ev:et i noden där båda har låst in 39.

 

blir ju någon skum serie typ, vi vinner 5/6 + 1/6^2*5/6 + 1/6^4*5/6 ... osv. (detta var dock innan chofritz påpekande om att fi får köra vidare även om vi går i mål).

 

man får nog selfplaya en massa så det konvergerar lite hyfsat.

Länk till kommentar
Dela på andra webbplatser

Nä själva tärningsrullandet får man väl ta analytiskt om man vill ha det exakt exakt, men det är väl ingen större poäng?

 

Iaf, om vi nu har fått det till att antalet strategier är en bit över 2^32800 så vore det ju lite kul att tänka över vad för sorts approach man kan använda för att få en bra lösning. Jag tänker mig att slumpa fram ett gäng, utvärdera dem mot varandra och korsa vinnarna i varje generation, vilket ju min föreslagna representation borde passa bra för. Men det är ju mest för att det är den enda heuristiska metoden jag kommer ihåg.

 

Sen skulle man ju kunna vara smart också och se hur mycket strategier man kan förkasta rakt av. Till exempel är det ju ingen större poäng att alls testa strategier som väljer att frysa utan att ha förbättrat sin poäng alls.

Länk till kommentar
Dela på andra webbplatser

Ett givet tillstånd kan bara tidspropageras till ett mycket begränsat (typ 5 + kommutatorn av motståndarens egentillstånd) antal tillstånd. Dessutom kan man applicera symmetri för alla transformationskommutatorer (Abelian, den oändliga varianten). Går i princip att lösa med topologisk grafteori och är absolut inga problem att bruteforca.

Länk till kommentar
Dela på andra webbplatser

Nu är det inte riktigt klart med reglerna men jag har för mig att han sa uttryckligen i videon att det var för att Herngren började som utmanaren skulle få chansen att kasta igen om Herngren var den som var först till 40. Dvs hade utmanaren varit först så hade han vunnit direkt. Spelet blir då inte riktigt symmetriskt, vilket eventuellt påverkar slutlösningen.

 

Om man beskriver ett tillstånd som T=[f, b, p] där f är fi:s poäng, b är bankade poäng och p är slagna poäng, så borde tillståndets EV kunna skrivas som:

 

EV([f, b, p]) = max (-EV([b+p, f, 0], 1/6*(EV([f, b, p+1])+EV([f, b, p+2])+...+([f, b, p+5])-EV([b, f, 0]))

 

Mycket tydligt och bra förstås ;)

 

Vi kan också ganska lätt räkna ut EV:t när den spelare som börjat har bankat ett tal över 40, då motståndaren kommer fortsätta slå tills han har högre eller slår en 6a.

 

Man borde nu kunna räkna rekursivt för att få fram lösningen, men måste ordna lite med mat här hemma så får ta mig an det senare.

 

Edit: insåg just att man måste skilja spelare 1 och spelare 2s tillstånd åt om reglerna är som jag beskrev i början av posten

Länk till kommentar
Dela på andra webbplatser

^kruxet är ju att det blir en självrefererande algoritm.

 

hjorts metod känns inte bra heller. att slumpa en strategi som en helhet borde inte vara nödvändigt. de senare noderna är inte beroende av vad vi hade för strategi i de tidigare noderna. de tidigare noderna är däremot beroende på vad vi har för strategi i de kommande noderna. således borde vi lösa GTO i de senare noderna först osv.

 

alternativt vänta på slaktis magiska lösning.

Länk till kommentar
Dela på andra webbplatser

Lite introduktion till algoritmer med populär vetenskaplig touch och science fiction. Dock ganska intressant. http://www.ur.se/Produkter/169988-UR-Samtiden-Lundaforskare-forelaser-Utopier-i-science-fiction-och-datavetenskap Pusslet som nämns är alltså följande, bestående av 256 bitar som är "omöjligt" att lösa. http://en.wikipedia.org/wiki/Eternity_II_puzzle

Länk till kommentar
Dela på andra webbplatser

En enkel metod som man som människa kan använda och som trots detta ligger väldigt nära GTO är att växa maximalt tills man närmar sig randen (dvs 40-sqrt(2)*6.028) och där använda riskreducering/ökning om möjlighet ges.

 

Riskreducering i ett tidigare skede kommer inte fungera eftersom väntevärdesskadan inte går att reparera, vilket enkelt kan förstås enligt följande

 

Vi spelar endast 1 rond. Den som har högst poäng efter ronden vinner.

 

Spelare1 spelar maximal tillväxt enligt n=5.4848+_n40, spelare2 riskrecuderar maximalt. Spelare2 vinner >70% (dvs, spelare2 slår tärningen endast för att nå spelare1s resultat+1, om spelare1 får 0p nöjer sig spelare2 med att slå endast en gång osv).

 

Vi spelar 2 ronder. Den som har högst sammanlagd poäng efter två ronder vinner. Spelare2 kan fortfarande vinna, men hans reducerade väntevärde börjar ligga honom i fatet och statistiken börjar svänga över till Spelare1s fördel. Efter ytterligare någon rond finns det faktiskt ingen riskreducerande strategi Spelare2 kan välja som uppväger väntevärdesförlusten.

 

Utan att gå in på avancerad matematik bör det av ovanstående kännas logiskt att det är i slutet och inte i början spelare2 (eller i vissa tillstånd spelare1) ska hävda sin eventuella positionsfördel medelst riskmanipulation (och alltså frångå principen om maximal tillväxt.)

 

Edit: Eftersom målet är större än eller lika med 40 måste n korrigeras från 5.4848 (maximal tillväxt mot oändligheten) då vi kan "sprinta i mål" på bekostnad av väntevärdet.

Länk till kommentar
Dela på andra webbplatser

Är maximerad tillväxt samma sak som att slå till man får 0EV i tillfällig poäng? Alltså i det här fallet till ens tillfälliga poäng är 18 eller större.

 

Varför är randen just sqrt(2)*6.028? 6.028 ser rätt likt väntvärdet för strategin ovan, men jag förstår inte varifrån roten ur två kommer.

 

"n=5.4848+_n40" här förstår jag inte notationen alls. Wikilänk eller nåt?

Länk till kommentar
Dela på andra webbplatser

Är maximerad tillväxt samma sak som att slå till man får 0EV i tillfällig poäng? Alltså i det här fallet till ens tillfälliga poäng är 18 eller större.

 

"n=5.4848+_n40" här förstår jag inte notationen alls. Wikilänk eller nåt?

 

Först och främst bör brytvärdet vara 15 inte 18.

 

För det andra är 20 ett bättre fast brytvärde för först till 40 av den enkla anledningen att vi inte ska växa maximalt på lång sikt utan komma först i mål (40) på kort sikt. Redan vid först till 200 kommer brytvärde 15 slå brytvärde 16.

 

Vill man vara riktigt avancerad kan man ändra detta brytvärde för varje runda beroende på tillståndet.

 

Om n är antalet tärningskast (och f(n) alltså väntevärdet av n kast) gäller:

 

evn.gif

 

evprim.gif

 

ntheoretical.gif

 

Övningsuppgift, visa hur detta värde f(n_max) korrelerar med väntevärdet av strategin "slå om vi har 15 poäng eller mindre".

Länk till kommentar
Dela på andra webbplatser

^men var är bruteforcelösningen med topologisk grafteori?!

 

om vi istället definierar en strategi som 39*39 brytpunkter så kan man ju faktiskt bruteforcea det hela genom att först beräkna brytpunkten i tillståndet där hero och fi har [39, 39] låsta, sen brytpunkten i [39,38] osv.

 

vet dock inte om man kan utesluta att GTO ibland vill frysa på x men inte på x+1 i något läge.

Länk till kommentar
Dela på andra webbplatser

vet dock inte om man kan utesluta att GTO ibland vill frysa på x men inte på x+1 i något läge.

 

Tja, vid ställningen 5-15 ska spelare1 fortsätta med att slå max 20 (och försöka nå målet i två ronder), medan spelare2 helt plötsligt ska öka till max 25 (och försöka nå målet i 1 rond))

 

Om du ska beräkna en 40x40 matris för poäng 0-39 per spelare kan det vara värt att notera att symmetrin i problemet. Varje element kommer ta dig ett par min att beräkna med någorlunda noggrannhet på en normal bordsdator. Om du inte utnyttjar symmetri blir det 48h beräkningar osv :)

 

Du kan också notera att man väldigt snabbt ska börja försöka nå målet i en runda istället för de urpsrungliga 2 (20+20) varför du kan "fuska" och lägga in matriselementen direkt.

Länk till kommentar
Dela på andra webbplatser

Tja, vid ställningen 5-15 ska spelare1 fortsätta med att slå max 20 (och försöka nå målet i två ronder), medan spelare2 helt plötsligt ska öka till max 25 (och försöka nå målet i 1 rond))

 

så, hur kom du fram till detta? om jag tolkar "slå max 20" så är det ett brytvärde vid 16? (jag vet inte om du ville visa ett exempel på när ett brytvärde inte är tillräckligt).

 

 

Om du ska beräkna en 40x40 matris för poäng 0-39 per spelare kan det vara värt att notera att symmetrin i problemet. Varje element kommer ta dig ett par min att beräkna med någorlunda noggrannhet på en normal bordsdator. Om du inte utnyttjar symmetri blir det 48h beräkningar osv :)

 

Du kan också notera att man väldigt snabbt ska börja försöka nå målet i en runda istället för de urpsrungliga 2 (20+20) varför du kan "fuska" och lägga in matriselementen direkt.

 

nu var väl inte spelet helt symmetriskt eftersom spelare 2 får spela vidare efter spelare 1 har >= 40. då går det väl inte heller att fuska på det sättet då vi måste veta vilket brytvärde >= 40 vi vill ha, mer exakt.

Länk till kommentar
Dela på andra webbplatser

wiie.png

 

Här är en bild på min lösning av det symmetriska problemet (dvs först till 40 vinner oavsett vem som börjar). Hittade verkligen inget bättre sätt att åskådliggöra lösningen än detta matlabhack. Earthnut håller på att kontrollera i skrivande stund, men det verkar som att vi har fått liknande lösningar med olika metoder.

 

Återstår bara att utvidga till det fullständiga problemet då =)

 

Edit: Jag har eventuellt löst även det fullständiga problemet också nu, men måste kontrollera lösningen lite mer vilket jag är på tok för trött för att göra nu.

Länk till kommentar
Dela på andra webbplatser

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Gäst
Svara i detta ämne...

×   Du har klistrat in innehåll med formatering.   Ta bort formatering

  Endast 75 max uttryckssymboler är tillåtna.

×   Din länk har automatiskt bäddats in.   Visa som länk istället

×   Ditt tidigare innehåll har återställts.   Rensa redigerare

×   You cannot paste images directly. Upload or insert images from URL.


×
×
  • Skapa nytt...