[quote=kee post_id=1131022 time=1580847066 user_id=11468]
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.
[/quote]

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

[img]https://i.ibb.co/xmMxPQW/wtf-N3allegw-QQ8d.png[/img]

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.

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.

[img]https://i.ibb.co/LNbGMYW/wtf-N3tcn-Nna6y.png[/img]

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 - [color=#FF0000]2[/color] - 2 ...
- als zwart zijn 2e zet altijd 3 zou spelen, wint rood in geval 1 - [color=#FF0000]3[/color] - 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:

[img]https://i.ibb.co/93KwryQ/wtf-N4eeihe7d.png[/img]

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

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.

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.

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.

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.

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.

[quote="Professor Puntje" post_id=1130856 time=1580661489 user_id=76038]
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).
[/quote]

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

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

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

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;
}

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]
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;
}
[/code]