Bestaat dit spel voor 2 spelers

[kee]

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).

Ik heb ook enkele uitbreidingen overwogen. Ik denk dat de strategie dan meestal zal terug te leiden zijn naar de simpele basisversie.

[Benm]

De O-notatie komt eigenlijk een beetje voort uit algoritmes om datasets te sorteren, waarbij de slechtere iets i de orde van N-kwadraat operaties nodig hebben om te voltooien, en de beter in de orde van N.log(N). Sorteerfuncties die bewust slecht gemaakt zijn hebben faculteit-N operaties (of nog erger) nodig om het proces te voltooien.

Ik vermoed dat dit spel is op te lossen met N-kwadraat operaties, mogelijk zelfs nog iets beter dan dat.

Het is echter geen realistisch spel, dus ik kan me voorstellen dat de oplossing niet zomaar voor het oprapen ligt.

[kee]

Het is de 'N1' die mij niet duidelijk is. Is dit faculteit-N?

Sowieso is de complexiteit lager dan O~(N^(2+N^2)), maar dat is zeer ruim gerekend:
* maximale lengte van de rij is N^2
* voor elke positie zijn er N mogelijke karakters
* bij toevoeging van het laatste karakter van een rij van lengte N^2 kan je berekenen of deze zet geldig is met O~(N^2) complexiteit
Totaal is O~(N^2 * N^(N^2)) of O~(N^(2+N^2)).

Als je weet hoe dit met complexiteit N^2 op te lossen, laat maar weten. Dat zou ik beschouwen als een eenvoudige strategie die wellicht ook zonder de computer uit te rekenen is voor niet al te hoge waardes van N (maximum 10 lijkt logisch) wanneer dit spel gespeeld zou worden.

Wat bedoel je met geen realistisch spel? Je kan dit spel gewoon spelen als je wil. Met het algoritme in mijn programma heb ik het zo geschreven dat je het ook kan spelen, terwijl hij erbij zet welke zetten degene zijn waarmee je een winnende strategie behoudt. Ik denk als je geen computer gebruikt dat het realistisch gespeeld kan worden door mensen die er geen ervaring mee hebben als je speelt met N=3.

[Benm]

Ik keek er eigenlijk even anders naar: wat is de maximale lengte van de reeks die je kunt maken voor een gegeven N:

Bij N=1 is de eerste en laatste zet '1' met een lengte van 1
Bij N=2 wordt het iets als 1221 (of 2112) met lengte 4
Voor N=3 heb je gevonden dat 123113321 een van de beste oplossingen is met lengte 9

Ik zag dat je ook tot N=7 hebt uitgerekend... hoe lang zijn die reeksen?

Ergens heb ik een vermoeden dat dit een 'bekende' reeks moet zijn, maar zou niet direct weten welke... de eerste 3 termen zijn de kwadraten, maar zo simpel is het vast niet. Voor het bepalen van de winnaar is alleen van belang of de reeks een even of oneven aantal cijfers heeft, hoe de reeks er precies uitziet maakt niet zoveel uit.

[kee]

123113321 was eigenlijk gewoon een voorbeeld van een spelverloop, het kon ook iets anders zijn. Er is dus niet zoiets als één reeks. Je zou bvb wel de reeks kunnen maken waarbij de speler met de winnende strategie steeds het eerst mogelijke karakter neemt om de winnende strategie te behouden, en de andere speler het eerste toegelaten karakter. De reeks zou dan dit worden: 1122132, dus wel niet hetzelfde. Er is ook niet zoiets als een 'beste' oplossing. Als een speler geen winnende strategie heeft kan je moeilijk over goede/beste/optimale zetten spreken voor die speler, tenzij mss de zet(ten) die hem verzekeren van een zo lang mogelijk uitstel van executie (maar indien die de andere speler een eenvoudige strategie geven zijn dat mss toch niet altijd de 'beste' zetten, dat hangt dus af van je definitie van 'beste').

Bvb bij het spel Nim is dat mss duidelijker. Als je geen winnende strategie hebt bij Nim zou je steeds 1 item van een oneven hoopje kunnen nemen (indien mogelijk). De andere speler moet dan 1 item van het andere oneven hoopje nemen om zijn winnende strategie te behouden, waardoor je op die manier lang uitstel van executie kan krijgen. Maar omdat de strategie voor de tegenspeler niet moeilijk te noemen is kan je dat mss niet als de 'beste' zetten beschouwen.

[kee]

Ik lees nu je post echt goed volledig, dat gebeurt als je met iets anders in je hoofd zit.

De langst mogelijke rij heeft lengte N^2+1. Dit omdat er N^2 verschillende twee-karakter-items zijn, en voor elke positie in de rij een andere combinatie dient te staan.

Voor N=1 is de rij eigenlijk '11' en niet '1'.
Voor N=2 is de rij '11221' ook mogelijk, en deze is 5 lang, de maximale lengte.
Voor N=3 is de maximale lengte 10. Of er ook zo'n rij bestaat van een spelverloop weet ik niet. Mss is er wel een eenvoudige manier om er een te bepalen, maar de restrictie dat je je zet niet mag herhalen bemoeilijkt het wel. Sowieso zal het wel steeds lukken om er een van lengte N^2 te vinden, voor dat laatste karakter moet ik eens kijken of dat altijd lukt.

[kee]

Voor N=3 heeft 3123322113 lengte 10. Een patroon kan gezocht worden dat werkt voor alle N.

[RedCat]

Hierboven een winstboom voor N=3.
De eerste speler is zwart en wint altijd, de tweede speler is rood.
Op elke legale zet van rood is een juiste (= naar winst leidende) respons van zwart gegeven.

Er is niet één constante volgorde voor de zetten van zwart die altijd winnend is voor alle mogelijke zetten van rood:
- als zwart zijn 2e zet altijd 2 zou spelen, wint rood in geval 1 - 2 - 2 ...
- als zwart zijn 2e zet altijd 3 zou spelen, wint rood in geval 1 - 3 - 3 ...


Hieronder een winstboom voor N=4, waarbij speler 2 (= rood) altijd wint.
(hier is de eerste zet van zwart = 1, alle overige 1e zetten van zwart gaan vergelijkbaar met de juiste permutatie van getallen)
De N=3 winstboom kan je nog wel uit je hoofd leren, maar deze is lastiger:

[kee]

In het echt moet je ook uit de voeten kunnen als je tegenspeler de winnende strategie heeft in plaats van jou, dus de boom moet dan nog wat groter worden zodat je gepast kan reageren als hij een fout maakt.

Iets dat kan helpen: Als je een rij eindigt op bvb 223 en 32 al voorkomt, of eindigt op 322 en 33 al voorkomt (2 en 3 kunnen om het even welke karakters zijn), dan kan je er gewoon een 3 achter zetten en win je bij om het even welke N nu, omdat je vanaf nu afwisselend steeds 3 en 2 kan zetten tot er geen zetten meer zijn voor de tegenspeler. De ondervinding leert dat je zeer vaak in dergelijke situaties terechtkomt. Met wat denkwerk moet het mss mogelijk zijn om dit uit te breiden naar een 'eenvoudige' strategie die altijd werkt.

[kee]

Vorige is niet helemaal correct. Het hangt er ook vanaf welke van de andere combinaties al gebruikt zijn. Maar toch zou het denk ik mss mogelijk zijn om, als je dat allemaal in rekening brengt, tenminste met een computer, op een snelle manier de goede zetten te bepalen.

[RedCat]

In het echt moet je ook uit de voeten kunnen als je tegenspeler de winnende strategie heeft in plaats van jou, dus de boom moet dan nog wat groter worden zodat je gepast kan reageren als hij een fout maakt.

Dan heb je de volledige boom nodig: als de tegenspeler een fout maakt dan kan jij gegarandeerd winnen (onder perfect spel), en die fout kan de tegenspeler overal in de boom maken.

Hieronder de N=3 boom (uitgaande van spel-opening door zwart met een 1, je kan eventueel nog iets verder reduceren - zo zijn voor zet 2 (= de eerste zet van rood) de keuzes 2 en 3 equivalent).
De knopen aangegeven met een zwart vierkant zijn winnend voor zwart (= speler 1), die met een rood vierkant voor rood (= speler 2).
Speler rood kan dan altijd het alternatief kiezen van de deelboom met de meeste zwart-rood overgangen in het verdere beloop, zodat zwart in de rest van het spel nog zo veel mogelijk kansen krijgt om een fout te maken.

Nu hiervoor nog een simpele structuur zien te vinden ...