Nekromanti Hur Skriver Man Ett Spel?

[Rising]

"Nej, bara för att man utforskat hela trädet av möjliga partier så behöver det inte innebära att det finns en gren som automatiskt leder till seger utan att motståndaren kan leda in den på en annan gren."

Om det inte finns en väg till direkt seger för den som börjar spela, så är det så att motståndaren kan försäkra sig om att vinna (ja, om han känner till hela trädet). Ett bra exempel på det är Nim om man exempelvis börjar med två stackar med lika många pinnar i vardera.

Jag är mycket nyfiken på hur ett träd skulle kunna se ut som inte garanterar vinst för endera sidor.

Rita gärna upp en trädstruktur med grenar som slutar i V och F (Vinst resp. Förlust) där en person som får välja vem som ska börja spela inte kan försäkra sig om att vinna till slut. Jag lyckas inte med det, hur jag än försöker.

/Rising

 

[Rising]

Re: Nim [OT]

"Det finns ett liknande, med den enda skillnaden att man inteär låst till 90-gradersvinklar och att man inte har tvåspelarvariant.

Kan dock inte komma på namnet. Reflections?"

Jo, jag har haft ett sådant till min Amiga (och gjort ett par sådana spel i Amos (där jag även i några versioner hade svarta hål som drog till sig ljuset, och en del andra sköna specialeffekter (rörliga föremål i bakgrunden som man skulle undvika, bland annat)).

Men då har spelet blivit något helt annat; ett precisionsspel. Då liknar det biljardspel i större utsträckning än ett logiskt intelligensspel, så även om ytan kan te sig lik så har det ändå blivit två oerhört olika spel.

...och så förstås, inget annat spel har (mig veterligen) gått ut på att leda en stråle så lång väg från start till mål, vilket ju är hela poängen med Speglar och Propellrar.

/Rising

 

[Troberg]

Rita gärna upp en trädstruktur med grenar som slutar i V och F (Vinst resp. Förlust) där en person som får välja vem som ska börja spela inte kan försäkra sig om att vinna till slut. Jag lyckas inte med det, hur jag än försöker.

Jag lyckas inte heller, men det beror antagligen på att mina försök är för små. Grejen är att i en lång sekvens av drag med många möjligheter så tror jag att det är svårt att hitta en gren som leder till vinst oavsett vad motståndaren gör. Det är ju det man måste hitta, en gren där allt motståndaren gör leder till grenar som man kan styra till vinst. Jag tror inte en sådan måste finnas, men misstänker att det är klurigt att bevisa.

 

[Rising]

"Grejen är att i en lång sekvens av drag med många möjligheter så tror jag att det är svårt att hitta en gren som leder till vinst oavsett vad motståndaren gör."

Grejen är att med lite enkel matematik så kan man ganska snabbt beskära trädet. Varje förgrening som ligger ett jämnt antal steg från utgångspunkten som leder till ett V kan du helt ta bort och ersätta med ett V. Samma sak kan du göra med alla förgreningar som ligger ett udda antal steg från utgångsläget, och som leder till ett F.

När man gjort det så leder varje slutförgrening i trädet till antingen en massa V eller en massa F, och kan sålunda ersättas mot enskilda V resp. F.

Repeterar man dessa två principer så skär man systematiskt bort grenarna från trädet steg för steg med matematisk, okuvlig precision. Det spelar ingen roll hur stort trädet är; hur lång hierarkin är eller hur många olika alternativ som varje förgrening leder till: En förgrening är ju antingen ett jämnt eller ett udda antal steg från utgångsläget, oavsett hur stort trädet är. På så vis hugger man bort alla förgreningar som inte slutar i andra förgreningar, steg efter steg, en efter en, in mot stammen tills själva utgångspunkten har blivit antingen ett V eller ett F.

Man vet alltså om det är vit eller svart som kommer vinna i schack, om båda spelare är allvetande datorer, alltså. Det finns ett tredje alternativ: Att man bara kan spela fram till en viss punkt och sedan får gå fram och tillbaka med några meningslösa pjäser i all evighet, för att den första som gör ett meningsfullt drag dömer sig själv till undergång. Kanske är det så att man redan från början bara får hoppa fram och tillbaka med sina hästar, för att den förste som rör en bonde framåt ofelbart kommer åka på torsk.

Schack är ju, till skillnad från Nim och luffarschack, ett spel där man ibland kan återgå till tidigare lägen, och på så vis lira partier som håller på i all evighet.

/Rising

[Ändring: När eftervärlden ska analysera mina inlägg här på forumet för att dokumentera mitt oerhörda snille, då kommer det se lite bättre ut om jag visar att jag, omedelbart efter att jag skrev det här inlägget, självklart kom på att man förstås kan sammanfatta båda procedurerna i en enda metod. Så här skall det se ut:

---
Varje förgrening som ligger ett jämnt antal steg från utgångspunkten och som leder till antingen ett V eller en kombination av förgrening/ar och två eller flera V, kan helt tas bort och ersättas med ett enkelt V. Samma sak kan göras med alla förgreningar som ligger ett udda antal steg från utgångsläget, och som leder till antingen ett F eller en kombination av förgrening/ar och två eller flera F.
---

Så. Bara så att eftervärlden kommer kunna se att jag förstod allt detta mer eller mindre omedelbart efter att jag skrivit inlägget.]

 

[Troberg]

Låter vettigt, och ett litet program jag gjorde verkar bekräfta det. Jag tar alltså tillbaka mina tidigare påståenden och erkänner att jag hade fel.

Schack är ju, till skillnad från Nim och luffarschack, ett spel där man ibland kan återgå till tidigare lägen, och på så vis lira partier som håller på i all evighet.

Bortsett från att en specifik situation bara får uppkomma ett visst antal gånger, sedan blir det remi.

Det här är iofs en akademisk fråga. Jag kommer inte exakt ihåg siffrorna och har ingen vettig räknare här, men det var något i stil med att om man hade en miljard datorer som testar en miljard partier var per sekund så skulle det ta i storleksordningen 10^85 gånger universums nuvarande ålder.

För de som inte är matematiskt bevandrade så är det alltså:

10 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 gånger universums nuvarande ålder. Även med en viss datorutveckling är det tveksamt om man klarar det.

För go blir motsvarande siffra ungefär 10^665, det vill säga:

100 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 gånger universums nuvarande ålder. Om man fuskar och nyttjar spegelvändningar och rotationer kan man nästan ta bort en nolla.

Jag tror inte att go kommer att lösas på ett tag.

 

[Rising]

Tic Tac Toe

"Det här är iofs en akademisk fråga. Jag kommer inte exakt ihåg siffrorna och har ingen vettig räknare här, men det var något i stil med att om man hade en miljard datorer som testar en miljard partier var per sekund så skulle det ta i storleksordningen 10^85 gånger universums nuvarande ålder."

Jag tror att vad man framförallt kommer att bli bättre på i framtiden när det gäller den här sortens beräkningar; det är att kunna se vad man egentligen behöver räkna på. Jag menar; ett enkelt spel som Tic-Tac-Toe på 3x3 rutor har väl 9x8x7x6x5x4x3x2x1=362 880 olika möjliga partier (delat med åtta för olika speglingar och rotationer så blir det 45 360), men det kunde jag knäcka redan i mellanstadiet, och inte gick jag igenom alla de där 40 000 olika möjligheterna, inte.

Jamenar; tänker man på hur underutvecklad min hårddisk innanför skallbenet är (och framförallt var då), så är det rätt arnmärkningsvärt att dryga 40 000 olika möjliga partier betades av till en "trappmatt", en "cowboymatt" och en "rådjursmatt" (samt en lite otrolig "indianmatt"), som jag rätt snabbt kom på, samt (vilket var den riktiga "knäckningen") hur man skulle göra för att försäkra sig om att inte förlora om motståndaren började.

Om man kan få en dator att tänka på det viset, så behöver den inte gå igenom så himla många olika varianter. Den kan döma ut vissa som dåliga på ett ganska tidigt skede, och då kan man slippa alla grenar som sedan växer på den sidan av trädet. Det tror jag kommer vara det avgörande när man ska knäcka schack till slut. Att kunna döma ut partier innan de har slutat. Att kunna räkna ut vilka delar av trädet som den inte behöver generera.

När det gäller ett så tråkigt, platt och dåligt (i mina ögon) spel som Go, så är jag exempelvis övertygad om att även om det finns flera friljoner olika möjliga partier matematiskt sett, så är det så skevt och undermåligt konstruerat speltekniskt sett att det säkert finns en jätteenkel väg genom det som försäkrar den ene spelaren att segra. Det spelar ju ingen roll hur många pyxiljoners fambuljoner olika andra möjliga partier som eventuellt går att uppleva i det spelet, så länge som "lösningen" begränsar motspelarens utrymmesfrihet till att kunna förlora på ett ynka fåtal olika tusental sätt.

Btw:

Trappmatt
Den första matten jag analyserade fram i tic-tac-toe. Jag var så oerhört djäkla stolt när jag kom på den, och jag kommer ihåg vilken uppståndelse det var kring mig när jag började använda den på mina polare. Dagen innan hade jag varit aslökig och förlorat mot typ alla, och sedan nästa dag så bara Pow! Pow! Kablam! Så föll de alla som käglor kring mig, jag var helt oslagbar!

Trappmatten kan man använda så fort som man har börjat och lagt sin pjäs i mitten (såklart) och när motståndaren har satt sin pjäs på någon av de fyra rutor som ligger bredvid mittenrutan. Direkt är han fångad och har förlorat, men han vet inte om det ännu!

Man börjar sedan på ett diagonalt anfall som tvingar motståndaren att placera nästa bricka långt ifrån sin första pjäs, å sedan sätter man ut sin tredje bricka så att det, tillsammans med ens tidigare drag, bildar en vacker "trappa" som kan skjuta åt två håll samtidigt. Omöjlig att stoppa.

Cowboymatt
Egentligen samma sak som trappmatt, bara att den ger en annan slutbild: Man sätter sin tredje bricka i den bortre hörnrutan så att man med sina tre röda brickor bildar en bredbent "cowboy" som står med fötterna brett isär på brädet:

Motståndaren får välja om han vill skjuta cowboyen i axeln (övre vänstra hörnet) eller mellan benen, men i vilket fall som helst så är det cowboyen som vinner och som visslandes kommer rida in i solnedgången när allt är över...

Rådjursmatt
Den som inte börjar måste alltså placera sin pjäs i en av hörnrutorna för att inte åka på en trapp- eller cowboymatt. Men är motståndaren säker så fort hon börjar i en hörnruta, då?

Nej, inte ännu. Det finns faktiskt en riktigt liten lurig manöver man kan försöka sig på som ibland funkar: Att helt enkelt köra rakt mot den pjäs som motståndaren nyss har lagt ut. Det ser helt sjukt ut om man inte är van vid det. "Vad gör du? Skall du hota den enda rutan på brädet där jag redan har placerat ut en pjäs?!" På med helljusen bara och paralysera motståndaren som det lilla rådjur hon är. Om du har flax så händer det nämligen ibland att hon sätter en pjäs på en angränsande ruta till den hon nyss har lagt ut, och vips! så har du återigen läge att lira ut en cowboy som ovan:

Rådjuret kan sedan stånga cowboyen i axeln eller mellan benen, vilket som, vi vet ju redan att det alltid är cowboyen som vinner till slut.

Indianmatt
Det här är en galen chansning, men när den lyckas så är det den mest förnedrande matten som finns i hela spelet. Det är förstås inte alltid den funkar, men den är så otippad att den ibland lurar folk ändå. När Torget hade tic-tac-toe som man spelade på tid (5 sekunder varje drag) så lyckades jag få in den här flera gånger, och det kändes alltid lika skönt.

Återigen måste man börja för att få in den, men det luriga är att man inte sätter sin första pjäs i mittenrutan, utan i en av hörnrutorna. När sedan motståndaren ställer sig i mitten med sina diligenser, så kallar man in resten av indianerna och omringar motståndaren. Eftersom man inte hotar någon enskild ruta så tvingar man honom inte att sätta en pjäs på någon enskild ruta, men om han då av vanan trogen (eller, vanligare på torget, om han var stressad och konfunderad) sätter en pjäs i en av hörnrutorna för att anfalla, så åker han på en rejält otäck överraskning:

...varpå man har två anfall på gång som inte båda kan avstyras. Kul, kul.

/Rising
som gillar att skriva om allvarliga saker på ett korkat sätt, och om korkade saker på ett allvarligt sätt.

 

[Dimfrost]

Man kan ju lösa spel utan att beräkna alla möjliga drag, men när det gäller schack och go är även detta ytterst orealistiskt (det pågår ingen forskning på området eftersom man inte kan vänta sig att lyckas, såvitt jag vet). Däremot, med en schysst kvantdator är det nog inte så omöjligt...


/Dimfrost

 

[Troberg]

Man kan ju lösa spel utan att beräkna alla möjliga drag, men när det gäller schack och go är även detta ytterst orealistiskt (det pågår ingen forskning på området eftersom man inte kan vänta sig att lyckas, såvitt jag vet).

Det sker nog ingen forskning för att lösa dem, men det sker en hel del forskning på kompletta lösningar på delar av lösningen, de delar som är tillräckliga för en garanterad vinst.

Däremot, med en schysst kvantdator är det nog inte så omöjligt...

Jag skulle säga att minst en av två förutsättningar måste fixas först: drastiskt mindre molekyler eller drastiskt snabbare ljushastighet. Med andra ord tror jag inte att det kommer att hända.

 

[Troberg]

Re: Tic Tac Toe

Jag tror att vad man framförallt kommer att bli bättre på i framtiden när det gäller den här sortens beräkningar; det är att kunna se vad man egentligen behöver räkna på.

Exakt, det är det som gör den mänskliga hjärnan så imponerande. En dator plöjer genom miljontals kombinationer för att hitta sin lösning, en människa kan med en snabb blick gallra ner det till 3-4 möjliga drag.

Det är imponerande, och det är det som gör att vi har en chans att matcha maskinerna.

 

[Klon]

Re: Tic Tac Toe

tja... tills dess en adtor kan genomföra alla de miljontals kombinatonerna snabbare än vad vi kan göra ett avgörande vid en anblick i vilket fall...

 

[Mutant]

Re: Tic Tac Toe

Finns inget vi kan ens fantisera som gör det möjligt om datorn bara ska mörcha rakt fram igenom alla kombinationer.

Om vi nu skulle säga att detta gick i framtiden så skulle nog våra hjärnor vara ännu snabbare även dom. så it's fucked either way ^^

 

[Ulfgeir]

Go

När det gäller ett så tråkigt, platt och dåligt (i mina ögon) spel som Go, så är jag exempelvis övertygad om att även om det finns flera friljoner olika möjliga partier matematiskt sett, så är det så skevt och undermåligt konstruerat speltekniskt sett att det säkert finns en jätteenkel väg genom det som försäkrar den ene spelaren att segra. Det spelar ju ingen roll hur många pyxiljoners fambuljoner olika andra möjliga partier som eventuellt går att uppleva i det spelet, så länge som "lösningen" begränsar motspelarens utrymmesfrihet till att kunna förlora på ett ynka fåtal olika tusental sätt.

Nyfiken på vad det är du tycker så illa om i Go (vilket råkar vara ett av mina absoluta favoritspel).

Var intressant uppdelning av Tic-Tac-tot dock.

/Ulfgeir

 

[Hartland]

Spelat -AoR-?

Eller Age of Renecance som det också heter. Dom största likheterna mellan dim kompis spel och AoR är först och främs att man tävlar om marknader samt att det sker i Europa.

AoR går rätt och slätt ut på att man ska "erövra" Europas alla marknader och tjäna pengar som man kan köppa uppgraderingar för, vilket gör att man känar mer pengar. Varje provins men tar över producerar även en vara vilken man kan få nytta eller onytta för beroende på vissa slumpade saker. Kort finns och det finns tre, eller fyra, beroende på deffinition, olika typer av kort. Personlighets kort med historiska perssoner som ger rabatt på uppgraderingar, "Varukort" som gör att du får pengar för en viss vara och special kort. Special korten vill jag dela in i två kategorier nämligen Händelse och Kort för Militärt Övertag. Kort för Militärt Övertag hjälper en att erövra marknader i en runda. Händelse kort kan vara saker som "Pappal Decreal" eller Svarta Döden eller Korståg. Man har även en mätare över hur eländiga folk är i ens provinser ("Missery Index"). =)

Kanske kan vara värt att ta en titt och få insperation där ifrån?
Spelets största nackdel är att man måste vara minst tre och på lådan står det "2-6 timmar"

/Hartland - gillar AoR, tycker det är synd att andra inte gör det

 

[Troberg]

Re: Spelat -AoR-?

Spelets största nackdel är att man måste vara minst tre och på lådan står det "2-6 timmar"

För att det ska vara spelbart är nog 5 spelare och 10 timmar minimum.

Hartland - gillar AoR, tycker det är synd att andra inte gör det

Det är OK, även om jag föredrar föregångaren Civ. Reglerna är inte lika rena och prydliga som i Civ.

 

[Hartland]

Re: Spelat -AoR-?

För att det ska vara spelbart är nog 5 spelare och 10 timmar minimum.

Tja... Man KAN ju "fuska" och låta spelare välja fritt bland huvudstäderna... Dock blir det då lätt att man snabbt får slut på cirklar...

Och nej reglerna är ganska otydliga... på engleska dessutom. Otydligheter eller englelska klarar man av men otydligheter på engelska det blir +ob2t6 på tärningsslaget

/Hartland - tror inte att han har spelat första Civ...

 

[Troberg]

Re: Spelat -AoR-?

Hartland - tror inte att han har spelat första Civ...

Då måste du prova det. Man är inte brädspelare förrän man testat det.

 

[entomophobiac]

Re: Spelprojekt - De tre marknaderna

Spelarna tävlar om de tre största marknaderna i Europas städer - Droger, prostitution och vapen.

Enligt en undersökning jag läste var faktiskt konst den tredje största svarta marknaden. Så, knark-vapen-konst blir skalan, helt enkelt, med en hiskelig majoritet för knarket.

Men ett brädspel behöver ju uppfylla ett antal saker:

1: Mål. Hur vinner man.
2: Intresse. Vad gör det värt/kul att vinna?
3: Variation. Vilka olika sätt kan jag vinna på och vilka taktiker finns för att utmanövrera andra/framhäva mig?

...typ.

 

[Rising]

Glömde en självklar regel:

Tjena Arvidos. Den här tråden är kallare än en död Eskimå vid det här laget, men jag kom på att jag glömde min gyllene regel; den bästa spelregeln genom tiderna:

"Det bästa sättet att spela på, skall också vara det roligaste."

Det där är framförallt viktigt när man programmerar datorspel, men även i brädspel så kan det där vara en bra minnesregel att ha i huvudet. Alltså; det låter kanske inte så märkvärdigt, men om man tillämpar den rätt så förstår man hur viktig den regeln i själva verket är. Jag har gjort massor med spel som bara varit baserade på en festlig spelmekanism och som vi lattjat lite med, små strider med varandra eller liknande, under tiden som jag hela tiden har haft en vision om vad man ska göra för att vinna och vilka strategier som skall vara framgångsfulla i spelet, men medan vi speltestat så kan jag ha märkt att det varit något annat som varit det verkligt roliga med spelet. Typ: jag gjorde en gång ett gladiatorspel där man kunde få Fysiska och Psykiska skador; och där alla skador representerades av olika kort som påverkade ens karaktärs prestanda: Typ, fick man ett brutet ben så kunde man inte röra sig så snabbt, och fick man den psykiska sjukdomen "manodepressivitet" så slog man två tärningar för ens förflyttning och valde den lägsta, om inte båda visade samma sak; varpå man fick kuta lika många steg som båda tärningarna tillsammans.

Nå, det visade sig ganska snart att en bra match var ganska tråkig; den som var bäst spöade skiten ur den andre; som fick massor av olika skador att tänka på. Det var mycket roligare att bli skadad än att skada motståndaren; för den som var skadad fick ju mest spelmässighet att tänka på. Det roligaste var ju att försöka använda en taktik så att man inte stördes så mycket av skadorna som man hade fått, och det kunde faktiskt bli rejält klurigt om man hade fått många olika handikapp som alla påverkade ens prestanda på olika sätt. Då ändrade jag om spelet så att man bara gav fysiska skador på motståndaren, men att man fick olika psykoser av att tillfoga skada på ens motståndare. På så vis blev spelet helt crazy-psycho, och mycket roligare att spela, särskilt när de riktigt kraftfulla kombinationerna i spelet handlade om att kombinera olika vapen och taktiker med speciella psyksjukdomar.

Ett annat exempel på Risings gyllene regel är ju Speglar och Propellrar, som utvecklades för att jag kom på att det riktigt roliga med den typen av spel var att leda strålen så långt som möjligt runt banan, inte så effektivt som möjligt.

Summan av kardemumman kan alltså vara att vara väldigt öppen när ni gör spelet. Kommer ni på någon del av spelmekanismen som är rolig; se till att den blir framgångsrik också!

/Rising

 

[Zire]

Olösligt?

Jag tror inte att go kommer att lösas på ett tag.

Åtminstone inte om man ska använda Brute Force. Men är problemet NP-komplett?
(Vilka iofs ännu inte är bevisade att de måste lösas med Brute Force)

- Zire, intressant diskussion f.ö.