Da var jeg tilbake fra en vikingfestival, hvor jeg møtte en slu danske. Vi spillte et artig spill, men problemet var at han vant hele tiden.
Reglene er som følger: 3 svarte, 4 orange og 5 blå stener legges ut på et bord. To spillere bytter på å trekke én eller flere stener av samme farge. (For eksempel kan du trekke 4 blå stener, men ikke 2 svarte og 2 orange i samme trekk.) Den som trekker den siste stenen taper.
Hva er den optimale vinnerstrategien?
Vikingspill
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
http://en.wikipedia.org/wiki/Nim
også kjent som "pearls before swine".
Her kan du spille det: http://www.transience.com.au/pearl.html
Kort forklaring: Spillet er "løst". Dvs. ut fra posisjonen kan man finne ut hvilken spiller som vinner, hvis begge spiller optimalt.
også kjent som "pearls before swine".
Her kan du spille det: http://www.transience.com.au/pearl.html
Kort forklaring: Spillet er "løst". Dvs. ut fra posisjonen kan man finne ut hvilken spiller som vinner, hvis begge spiller optimalt.
http://projecteuler.net/ | fysmat
Ah, interessant link. Takker!Gommle skrev:http://en.wikipedia.org/wiki/Nim
også kjent som "pearls before swine".
Her kan du spille det: http://www.transience.com.au/pearl.html
Kort forklaring: Spillet er "løst". Dvs. ut fra posisjonen kan man finne ut hvilken spiller som vinner, hvis begge spiller optimalt.
Finnes det egentlig en sikker vinnerstrategi i dette spillet?
La oss benevne tilstanden i spillet som X-Y-Z, hvor bokstavene angir hvor mange som er igjen av hver farge i stigende rekkefølge (X er antall av den fargen med færrest brikker igjen, Y med nest-færrst, Z med flest).
Begynner med å finne ut hvilke tilstander som medfører sikkert tap for den som skal trekke. To åpenbare tilstander er 1-1-1 og 0-2-2. Utifra dette ser man fort at 1-2-3 også medfører tap (uansett hva spilleren gjør kan neste spiller på sitt trekk enten vinne eller gjøre tilstanden til 1-1-1 eller 0-2-2, som medfører vinn på et par trekk). Videre kan man se at 0-X-X (X > 1) også medfører tap. Ved denne stillingen vil den tapende spiller måtte trekke av en av de to gjenværende fargene, og neste spiller vil trekke av den andre slik at det blir like mange av hver farge igjen. Til slutt fører dette til 0-2-2 (hvis ikke motspilleren trekker prøver å unngå 0-2-2 ved å trekke til 0-1-X isteden for 0-2-X, men da har han obviously tapt også).
Så nå har vi at spilleren som skal trekke taper ved følgende tilstander: 1-1-1, 1-2-3 og 0-X-X (X > 1). Så hvem vinner?
Det er lett å se at hvis spiller 1 tar fra orange eller blå, så kan spiller 2 gjøre tilstanden til en av de som sikrer vinn på neste tur (det er såpass få mulige trekk at man kan ta det case-by-case). Det kun ETT trekk spiller 1 kan gjøre for ikke å tape, og da vil faktisk spiller 2 ikke kunne ha noen som helst trekk for å unngå å tape på neste tur (altså spiller 1 vinner!). Trekket er å ta 2 fra svart (tar han bare 1 fra svart vil neste spiller reversere det hele ved å ta en til fra svart). Nå kan ikke spiller 2 redusere tilstanden til sikker vinn, og må gjøre et trekk som tillater spiller 1 å gjøre akkurat dette neste tur.
EDIT: Fikset på feil.
Begynner med å finne ut hvilke tilstander som medfører sikkert tap for den som skal trekke. To åpenbare tilstander er 1-1-1 og 0-2-2. Utifra dette ser man fort at 1-2-3 også medfører tap (uansett hva spilleren gjør kan neste spiller på sitt trekk enten vinne eller gjøre tilstanden til 1-1-1 eller 0-2-2, som medfører vinn på et par trekk). Videre kan man se at 0-X-X (X > 1) også medfører tap. Ved denne stillingen vil den tapende spiller måtte trekke av en av de to gjenværende fargene, og neste spiller vil trekke av den andre slik at det blir like mange av hver farge igjen. Til slutt fører dette til 0-2-2 (hvis ikke motspilleren trekker prøver å unngå 0-2-2 ved å trekke til 0-1-X isteden for 0-2-X, men da har han obviously tapt også).
Så nå har vi at spilleren som skal trekke taper ved følgende tilstander: 1-1-1, 1-2-3 og 0-X-X (X > 1). Så hvem vinner?
Det er lett å se at hvis spiller 1 tar fra orange eller blå, så kan spiller 2 gjøre tilstanden til en av de som sikrer vinn på neste tur (det er såpass få mulige trekk at man kan ta det case-by-case). Det kun ETT trekk spiller 1 kan gjøre for ikke å tape, og da vil faktisk spiller 2 ikke kunne ha noen som helst trekk for å unngå å tape på neste tur (altså spiller 1 vinner!). Trekket er å ta 2 fra svart (tar han bare 1 fra svart vil neste spiller reversere det hele ved å ta en til fra svart). Nå kan ikke spiller 2 redusere tilstanden til sikker vinn, og må gjøre et trekk som tillater spiller 1 å gjøre akkurat dette neste tur.
EDIT: Fikset på feil.
Sist redigert av Badeball den 15/06-2009 19:44, redigert 1 gang totalt.
Tilstanden 0-1-X sikrer i9kke tap, men sikrer vinn om man spiller optimalt.
Hvis vi antar at begge spillerne spiller optimalt, og at første spiller alltid trekker 2 fra svart, slik du foreslår.
Da får vi tilstandene
T0=3-4-5
T1=1-4-5
Om begge spiller optimalt vil spiller 2 nå trekke 1 fra orange.
T2=1,3,5
La oss nå se på alle trekkene spiller 1 kan gjøre:
Om S1 (Spiller 1) nå trekker den siste sorte, vil S2 trekke 2 blå, og S1 taper.
Om S1 trekker 1 orange, vil S2 trekke 2 blå. Tilstanden blir 1-2-3 og S1 taper.
Om S1 trekker 2 orange, vil S2 trekke 4 blå. Tilstanden er nå 1-1-1, og S1 taper.
Om S1 trekker 1 blå, vil S2 trekke 2 blå. Tilstanden er nå 1-2-3, og S1 taper.
Om S1 trekker 2 blå, vil S2 trekke enten 1 blå eller 1 orange. Tilstanden blir 1-2-3, og S1 taper.
Om S1 trekker 3 blå, vil S2 bli være i situasjonen 1-2-3, og S1 vinner!
Om S1 trekker 4 blå, vil S2 trekke 2 orange. Tilstanden blir 1-1-1 og S1 taper.
Dak an vi konkludere at i en spill der begge spillerne spiller optimalt, vil den som begynner alltid vinne. Den optimale tilstandsrekka blir:
T0 : 3-4-5 Starten avspillet
T1 : 1-4-5 S1 trekker 2 svarte
T2 : 1-3-5 S2 trekker 1 orange
T3 : 1-2-3 S1 trekker 3 blå
S2 har tapt.
Hvis vi antar at begge spillerne spiller optimalt, og at første spiller alltid trekker 2 fra svart, slik du foreslår.
Da får vi tilstandene
T0=3-4-5
T1=1-4-5
Om begge spiller optimalt vil spiller 2 nå trekke 1 fra orange.
T2=1,3,5
La oss nå se på alle trekkene spiller 1 kan gjøre:
Om S1 (Spiller 1) nå trekker den siste sorte, vil S2 trekke 2 blå, og S1 taper.
Om S1 trekker 1 orange, vil S2 trekke 2 blå. Tilstanden blir 1-2-3 og S1 taper.
Om S1 trekker 2 orange, vil S2 trekke 4 blå. Tilstanden er nå 1-1-1, og S1 taper.
Om S1 trekker 1 blå, vil S2 trekke 2 blå. Tilstanden er nå 1-2-3, og S1 taper.
Om S1 trekker 2 blå, vil S2 trekke enten 1 blå eller 1 orange. Tilstanden blir 1-2-3, og S1 taper.
Om S1 trekker 3 blå, vil S2 bli være i situasjonen 1-2-3, og S1 vinner!
Om S1 trekker 4 blå, vil S2 trekke 2 orange. Tilstanden blir 1-1-1 og S1 taper.
Dak an vi konkludere at i en spill der begge spillerne spiller optimalt, vil den som begynner alltid vinne. Den optimale tilstandsrekka blir:
T0 : 3-4-5 Starten avspillet
T1 : 1-4-5 S1 trekker 2 svarte
T2 : 1-3-5 S2 trekker 1 orange
T3 : 1-2-3 S1 trekker 3 blå
S2 har tapt.
Oops, ja, jeg skrev bare feil i oppsummeringen min om 0-1-X. Det jeg mente står litt lenger opp, og det er at hvis spilleren som skal trekke på 0-X-X trekker slik at stillingen blir 0-1-X, så har han tapt. Det var for å forklare at 0-X-X ikke trenger å føre til tap kun via reduksjon til 0-2-2, men også til f.eks. 0-1-X (eller 0-0-X for den slags skyld), men spilleren ønsker å tape enda fortere.
Jeg ser forresten ikke hvorfor du (tilsynelatende) mener at det kun finnes en optimal spillesekvens. Hvis spiller 2 skjønner opplegget, så ser han at han har tapt uansett hva han gjør, så hva vil du si at å spille optimalt betyr for spiller 2? Å hale ut tiden lengst? Isåfall bør spiller 2 sitt første trekk være å danne 1-4-4 (spillet gjennomgår i 10 tilstander), ikke 1-3-5 (spillet gjennomgår 8 tilstander). Hvis jeg har regna rett.
Kan jo argumentere at det optimale for spiller 2 er å tape fortest mulig, for å ikke sløse bort tiden sin. Men på den andre siden, hvis han ikke vet om spiller 1 kjenner optimal strategi, så lønner det seg å hale ut spillet, fordi spiller 1 kan gjøre en feil og tape. Hi-hi.
Jeg ser forresten ikke hvorfor du (tilsynelatende) mener at det kun finnes en optimal spillesekvens. Hvis spiller 2 skjønner opplegget, så ser han at han har tapt uansett hva han gjør, så hva vil du si at å spille optimalt betyr for spiller 2? Å hale ut tiden lengst? Isåfall bør spiller 2 sitt første trekk være å danne 1-4-4 (spillet gjennomgår i 10 tilstander), ikke 1-3-5 (spillet gjennomgår 8 tilstander). Hvis jeg har regna rett.
Kan jo argumentere at det optimale for spiller 2 er å tape fortest mulig, for å ikke sløse bort tiden sin. Men på den andre siden, hvis han ikke vet om spiller 1 kjenner optimal strategi, så lønner det seg å hale ut spillet, fordi spiller 1 kan gjøre en feil og tape. Hi-hi.