Bestaat dit spel voor 2 spelers

[kee]

Ik bedacht volgend spel voor twee spelers.

Bepaal vooraf een set van N karakters.

Spelverloop:
1. Start met een lege rij.
2. Elke speler doet om beurten een zet door een van de mogelijke karakters aan de rij toe te voegen. Hierbij mogen de laatste 2 karakters in de nieuwe rij niet al eerder in deze volgorde in de rij voorkomen. Ook mag de speler niet hetzelfde karakter zetten als bij zijn vorige zet.

Einde van het spel:
Een speler verliest als hij geen geldige zet meer kan doen.

Voorbeeld:

Om het eenvoudig te houden nemen we N = 3. Karakterset is {1,2,3}.

Spelverloop van de rij:
1 (speler1 start met 1)
12 (speler2 koos voor 2)
123 (speler1 mocht bij zijn tweede zet niet opnieuw voor 1 kiezen, omdat hij dit koos bij zijn vorige zet. Hij kon 2 of 3 kiezen en koos voor 3)
1231 (speler2 kon 1 of 3 kiezen)
12311 (speler1 kon hier enkel voor 1 kiezen omdat 12 al in de rij staat en omdat hij vorige keer voor 3 koos)
123113
1231133
12311332
123113321
Nu is speler 2 aan zet. Hij kan echter geen geldige zet meer doen en verliest het spel.

Vragen:
1. Bestaat dit spel al onder een of andere naam?
2. Is er een (al dan niet eenvoudige) winnende strategie? Indien die er is zou het spel niet echt waardevol zijn. Een klein (inefficiënt) programma leert dat als ik het goed heb de winnende strategie als volgt vastligt bij het begin van het spel:

N=1, speler2
N=2, speler1
N=3, speler1
N=4, speler2
N=5, speler2

Voor grotere N was mijn programma op dit moment te inefficiënt geschreven om het snel berekend te hebben.

Een winnende strategie (zonder de boom te moeten berekenen) kon ik nog niet ontdekken.

[Professor Puntje]

Ik ben in dat vakgebied zelf niet goed thuis maar wellicht helpt onderstaande link je verder (als je die niet al gezien hebt):

https://en.wikipedia.org/wiki/Combinatorial_game_theory

[Math-E-Mad-X]

Is er een (al dan niet eenvoudige) winnende strategie?

Een winnende strategie bestaat sowieso voor één van de twee spelers, want er is altijd maar een eindig aantal mogelijke rijen, dus je kunt in principe met een computerprogramma altijd nagaan welke zet de beste is, en een gelijkspel is niet mogelijk (voor zover ik begrijp uit je beschrijving).

Ik denk dus dat je je vraag beter op kan splitsen in de volgende drie deelvragen:

1) welke van de twee spelers heeft een winnende strategie?
2) Is die winnende strategie eenvoudig genoeg voor een computer om hem uit te rekenen voor grote N?

En, in het geval het antwoord op de vorige vraag 'ja' is,

3) Is de winnende strategie ook envoudig genoeg om zonder computer uit te kunnen rekenen?

[Benm]

Ergens denk ik dat de winnende strategie best te doen is zonder hulp van een computer op het moment van het spel: Je kunt vooraf min of meer berekenen wat de beste strategie is en daarmee foutloos winnen als je in een voordelige positie start.

Als je het echt speelt is er natuurlijk wel een kans dat je tegenstander een fout maakt, waardoor je strategie niet meer werkt en je iets anders moet verzinnen... even aangenomen dat je tegenspeler een mens is die niet altijd de optimale keuzes zal maken.

[Math-E-Mad-X]

Als je het echt speelt is er natuurlijk wel een kans dat je tegenstander een fout maakt, waardoor je strategie niet meer werkt en je iets anders moet verzinnen... even aangenomen dat je tegenspeler een mens is die niet altijd de optimale keuzes zal maken.

Dat hangt er vanaf wat je precies met een 'strategie' bedoelt. In de wiskunde (speltheorie) bedoelt men met een strategie meestal een functie die aan elke mogelijke situatie een bepaalde zet toekent. Een 'winnende strategie' is in die zin een strategie die altijd wint, ongeacht wat de tegenstander doet (en merk vooral op dat zo'n winnende strategie ook echt bestaat, voor één van de twee spelers).

[Benm]

Dat verschilt natuurlijk per spel: soms heb je een situatie waarbij de beginnende speler altijd wint of juist verliest als iedereen optimaal speelt.

Aan de andere kant heb je een reeks van spellen die eindigen in een gelijkspel als je beide optimaal speelt, dingen als tic tac toe of 4 op een rij.

Ergens denk ik dat het genoemde spel een kwestie is van wie begint in combinatie met het aantal mogelijke zetten. Blijkbaar is het uitgewerkt voor 5 opties, maar ik vermoed dat het bepaald is voor alle mogelijke opties.

[Math-E-Mad-X]

Aan de andere kant heb je een reeks van spellen die eindigen in een gelijkspel als je beide optimaal speelt, dingen als tic tac toe of 4 op een rij.

Klopt, maar in het spel van dit topic is geen gelijkspel mogelijk.

[Professor Puntje]

Is het zo dat als er geen gelijkspel mogelijk is er dan noodzakelijkerwijs voor één van de spelers een winnende strategie moet bestaan?

[kee]

Ik was een beetje verwarrend in mijn post. Er is sowieso een winnende strategie voor een van de spelers aangezien het spel altijd eindigt na een eindig aantal zetten. Een gelijkspel is inderdaad niet mogelijk. Een winnende strategie houdt in dat die speler altijd wint indien hij de juiste zetten doet, wat de andere speler ook doet.

Het spel wordt gespeeld met een set karakters van een vooraf vastgelegd aantal N. Afhankelijk van de waarde van N zal ofwel de beginnende speler, speler1, ofwel de tweede speler, speler2, steeds een winnende strategie hebben. Met een klein programma heb ik uitgerekend wie een winnende strategie heeft voor verschillende waardes van N. Dit kan eenvoudig op een recursieve manier. Voor grote N duurt de berekening al snel heel lang, ook met een computer, vandaar enkel de resultaten voor kleine N. Voor N=6 is het trouwens speler2 die de winnende strategie heeft. Voor N=7 is het mij onbekend.

Voor heel wat zulke spelletjes is het echter mogelijk via een eenvoudige, snel te berekenen manier, te bepalen welke zet je moet doen om je winnende strategie te behouden, zonder dat je dus de hele boom met alle mogelijke zetten moet gaan uitschrijven of berekenen met de computer. Vraag is of dat hier ook het geval is. Een spel waarbij je steeds eenvoudig kan bepalen hoe je moet spelen is over het algemeen minder interessant. Een uitzondering is mss Nim, wellicht omdat de berekening toch niet zo triviaal is. In dit spel lijkt het probleem dat indien er geen eenvoudig te berekenen strategie is, het moeilijk lijkt om echt regels te kunnen vinden over hoe je toch min of meer de goede zetten eruit kan halen. Het is op zich zonder computer al vrij lastig om bij grotere waardes van N en langere rijen uit te vissen welke zetten nog maar mogelijk zijn, laat staan welke van de mogelijke zetten ook goede zetten zijn.

Ook grappig: Het spel komt eigenlijk uit een droom van twee nachten geleden die ik mij 's morgens nog herinnerde. Ik heb er wel de regel dat je je vorige zet niet mag herhalen aan moeten toevoegen omdat er anders altijd een zeer eenvoudige winnende strategie is voor speler2.

[Math-E-Mad-X]

Is het zo dat als er geen gelijkspel mogelijk is er dan noodzakelijkerwijs voor één van de spelers een winnende strategie moet bestaan?

Ja, tenminste, als het spel altijd in een eindig aantal zetten eindigt (zoals de TS hierboven ook al aangeeft).

[Benm]

Feitelijk is dat de hele kunst: in een even of oneven aantal zetten zorgen dat er geen volgende zet meer mogelijk is. Afhankelijk van N is dat even of oneven, en staat de winnaar vast.

Qua simulaties is het denk ik lastig als je echt aanpakt zoals een mens zou doen, je krijgt een aantal stappen dat oploopt met pakweg de faculteit van N. Dit is denk ik wel te vereenvoudigen: Als je bijvoorbeeld met N=6 werkt en speler 1 begint met 1, maakt het in wezen nog niets uit of speler 2 nou 2 of 6 kiest. Je kan het spelverloop dan simuleren tot het punt waarbij de enige optie een herhaling van een serie van 2 is of het laatste getal moeten kiezen waarbij die speler verloren heeft.

[kee]

Er is inderdaad enige vereenvoudiging mogelijk. Dat brengt je soms een stap verder naar de volgende waarde van N.

Dit is een vereenvoudigde snippet van wat ik nu heb. Je kan zien dat daar deze vereenvoudiging in zit door steeds slechts 1 van alle karakters die nog niet gebruikt waren in de rij tot dan toe te behandelen. In feite maakt een permutatie van alle karakters idd niets uit (rij 58852 is in feite hetzelfde als 12213), maar ik denk dat in het huidige format dat er al min of meer in zit doordat de foreach loop stopt wanneer één keer State.Win wordt teruggegeven.

Het gebruiken van een HashSet waarbij elke twee opeenvolgende karakters worden opgeslaan als een item, ipv een string om in te zoeken, dacht ik zou ook tijdswinst opleveren, maar het steeds opnieuw moeten clonen van de hashset bleek hierin te veel tijd in te nemen (hoewel ik dat toch nog eens opnieuw zou kunnen bekijken of dat niet beter kon).

Volgende dat ik nog kan doen is multithreading gebruiken voor de foreach loop en te stoppen wanneer een van de returns State.Win teruggeeft (idee is hier dat als er een snelle State.Win returned wordt met een later karakter, de vorige karakters, die mss trager tot een resultaat leiden, niet behandeld moeten worden), maar dat moet ik nog eens bekijken wat daar mogelijk is, gezien het ook trager kan zijn doordat je al de berekening start voor alle karakters, wat mss niet nodig is. Voor N=7 is het trouwens opnieuw speler2 die de winnende strategie heeft.

Code: Selecteer alles

private string Characters;

private void ButtonGo_Click(object sender, EventArgs e)
{
	Characters = "123456";
	Messages.ShowMessage(CalculateState("  ", Characters[0]).ToString())
}

private State CalculateState(string written, char character)
{
	if (written[written.Length - 2] == character)
		return State.LooseNow;
	string search = string.Concat(written[written.Length - 1], character);
	if (written.Contains(search))
		return State.LooseNow;
	written = written + character;
	bool noneHandled = false;
	foreach (char ch in Characters)
	{
		if (!written.Contains(ch))
			if (noneHandled)
				continue;
			else
				noneHandled = true;
		if (CalculateState(written, ch) == State.Win)
			return State.LooseFuture;
	}
	return State.Win;
}

[Benm]

Ik denk dat de truc vooral zit in het onderscheiden of een volgend getal 'nieuw' of 'reeds gebruikt' is. Het maakt niet uit welk getal het precies is, enkel of het 'hergebruikt' is en daarmee mogelijk eerder in combinatie met een ander getal is voorgekomen in de reeks.

Die manier van zoeken zou de snelheid kunnen verbeteren van pakweg O~N1 naar O~N^2, wat een enorm verschil maakt bij relatief kleine waarden voor N.

Wellicht is er nog wel een betere mogelijkheid die in de orde van O~log(N) werkt, al zou ik die zo snel niet kunnen bedenken.

Maar goed, zo lang het aantal berekeningen stijgt met het kwadraat van N ipv de faculteit kun je een stuk meer berekenen - bijvoorbeeld tot aan N=100 of N=1000.

Overigens denk ik niet dat er veel verrassends uit zal komen, voor iedere N zal er een strategie zijn waarbij iedere foutloze speler gegarandeerd kan winnen ongeacht wat de tegenstander doet.

[Professor Puntje]

Om het spannender te maken zou je de spelers wellicht een of meer "Jokers" kunnen geven die het mogelijk maken gaande het spel iets aan de toegestane karakters te veranderen (bijvoorbeeld door een reeds gebruikt karakter opnieuw toe te laten of een nieuw karakter aan het spel toe te voegen).

[kee]

Ik weet niet wat je precies bedoelt met O~N1 van complexiteit, maar ik denk dat de complexiteit zwaarder is dan je denkt. Moeillijk om exact te zeggen omdat je recursief niet alles uitrekent, maar je zou er wel een maximale complexiteit op kunnen plakken.

Enkele timing benchmarks in milliseconds met bovenstaande versie van het algoritme:
N=1 - 0ms
N=2 - 1-2ms
N=3 - 3-7ms
N=4 - 6-17ms
N=5 - 79-101ms
N=6 - 28704-32461ms
N=7 - 55672321ms
N=8 - Met deze versie begin ik hier voorlopig niet aan .