vervolg spellen uitrekenen (recursief)

[Verwijderd]

Ik ben bezig met een opdracht over het bekende spel "4 op een rij". De laatste optie die mij rest is om het aantal mogelijke vervolg spellen uit te rekenen die nog gespeeld kunnen worden.
Het gaat om een recursief algoritme, hieronder in c++ weergegeven.
Het gaat echter fout bij het limiteren van het maximaal aantal aanroepen. Het zou namelijk immens lang duren om een leeg bord uit te rekenen(Ik zou zeggen om het bord vol te spelen al 2^42 min de mogelijkheden dat iemand tussendoor 4 op een rij heeft). Daarom wil ik de "diepte" limiteren.

Mijn ingeving is dat als ik bij de eerste aanroep diepte 10 zou geven,dat hij na 10 'recursies' terug zou gaan vallen en uiteindelijk returnen aan de aanroeper. Blijkbaar heb ik hier in een gedachtefout gemaakt want het eindigt in een oneindige loop. Ziet iemand wat ik verkeerd heb gedaan?

C++: vervolgspellen

// berekent recursief het aantal vervolgpartijen
int bord::vervolgpartijen(int diepte){
  int vervolgp = 0; // aantal vervolgpartijen
  // als het spel "klaar is" is dat 1 manier op het uit te spelen
  // geef dus 1 terug
  if(gewonnen() || veldvol()) 
    return 1;
  if(diepte == 0) // hij moet er dus uitspringen bij diepte 0
    return 0;
  // loop steeds de breedte van het bord af
  for(int i=0;i<bordbreedte;i++){
    if(toegestaan(i)){ // als er een zet gedaan mag worden
    doezet(i,aanzet); // doe dan deze zet
    aanzet *= -1; // wissel van gebruiker
    // roept zichzelf aan om deze routine te herhalen per aanroep
    // zo wordt in vervolgp steeds de waarde van de vorige recursie opgetelt
    // uiteindelijk bevat dit dus het aantal vervolgpartijen
    vervolgp += vervolgpartijen(diepte--); // zet het steeds in de variabele
    ontdoezet(i); 
    }
  }
  
  return vervolgp;
}

[ Voor 0% gewijzigd door Verwijderd op 26-11-2009 21:59 . Reden: typo ]

[RobIII]

Verwijderd schreef op donderdag 26 november 2009 @ 21:38:
Ziet iemand wat ik verkeerd heb gedaan?

Wat je in ieder geval verkeerd doet is dat je niet aangeeft wat je zelf al hebt geprobeerd en gewoon je code hier neer plempt zonder daar verder op in te gaan. Heb je al gedebugged en zo ja: wat waren de bevindingen? En waarom staat dit in SEA als het om een implementatiedetail gaat?

Debuggen: Hoe doe ik dat?
Waar hoort mijn topic?
SEA >> PRG

Hint: Output meteen na het binnenkomen van de functie eens "diepte" naar je console/stdout/log/whatever. En bedenk even wat diepte-- precies doet.

[ Voor 10% gewijzigd door RobIII op 26-11-2009 22:24 ]

[Soultaker]

@Thier89: Je uitleg klinkt zinnig, maar komt niet overeen met wat je programma doet. Kijk nog eens goed naar regel 18, en vraag je dan af wat de waarde van diepte is bij de eerste aanroep, dan bij de tweede, et cetera. Als je het niet zelf kunt bedenken, print dan bovenaan de functie de waarde van diepte en de inhoud van het speelveld. Daarmee moet je er toch uit kunnen komen.

[.oisyn]

Heb je überhaupt al eens gedebugged? Ik denk het niet, ander was je er zelf ook al achter. Op regel 18 verminder je diepte steeds, maar ook voor de huidige aanroep!

.edit: oplossing verwijderd, zoek het zelf idd maar eerst uit

[ Voor 40% gewijzigd door .oisyn op 26-11-2009 22:22 ]

[Verwijderd]

Ik weet niet hoe het in C++ is, maar ik meende dat bijv. in PHP, op 't moment dat je $diepte-- doet, dat hij de huidige waarde meegeeft en niet die met 1 er af. Om dat te krijgen moet je dan --$diepte doen. Maar diepte - 1 zou hier denk nog beter op zijn plek zijn.

[Verwijderd]

@RobIII
Het is inderdaad niet slim geweest om niet even mijn bevindingen te posten, dit is me even ontglipt. Ik ben echter van mening dat mijn topic in SEA hoort, omdat de c++ code slechts een manier is om mijn gedachtegang weer te geven over het algoritme, en de code zelf het doel niet is.

Algemeen:
Wat al gedaan was natuurlijk was het debuggen dmv outputresultaten wat herhaaldelijk dezelfde diepte weergaf.

[.oisyn]

Bottom line is dat het een programmeerprobleem is en daarom in PRG hoort, ipv dat je het over software architectuur e.d. hebt.

Maar als je vergeten bent je bevindingen te posten, waarom doe je dat dan niet alsnog?

[Mischa_NL]

Mooie schoolopdracht is dat. Ik heb er ook ff over na zitten denken (volg de studie zelf niet).
Je doet het wel op de 'goede' manier, door recursie te gebruiken.

[RobIII]

Verwijderd schreef op donderdag 26 november 2009 @ 22:38:
Algemeen:
Wat al gedaan was natuurlijk was het debuggen dmv outputresultaten wat herhaaldelijk dezelfde diepte weergaf.

En toen ging je dat onderzoeken, want je bedoelde wel "diepte--" aan maar dat deed 'ie klaarblijkelijk niet...
Ondanks dat het antwoord je nu letterlijk is voorgezegd (thanks GuidoH); weet je nu ook waarom dat zo is? Of ben je tevreden met het antwoord en kun je nu met een gerust hart je opdracht inleveren?

[ Voor 22% gewijzigd door RobIII op 26-11-2009 23:08 ]

[Verwijderd]

Mijn bevindingen van diepte waren zoals hierboven beschreven herhaaldelijk hetzelfde: exact 1 bij input 1. Ik Ik heb het probleem uiteindelijk kunnen tackelen door de diepte buiten de for loop de verminderen en deze als externe variabele call by reference mee te geven. De diepte had ik al op deze manier laten veranderen, maar omdat ik steeds een getal mee gaf aan de functie heb ik niet nagedacht dat dit tussendoor 'opgeslagen zou moeten worden'

[ Voor 25% gewijzigd door Verwijderd op 26-11-2009 23:10 ]

[Ram0n]

Zoals ook in de opdracht staat valt het te verwachten dat het voor lege borden (en zelfs nog vrij veel verder in een spel) te lang gaat duren, maar dat is ook niet erg. Het is hier slechts de bedoeling dat je heel basic bruteforce gaat rekenen, don't worry about the performance

Overigens moet je verder met de hints hierboven ook een eind kunnen komen, je bent een heel eind, maar de oplossing staat hierboven al bijna gegeven. De hint om zoveel mogelijk te outputten (wat ook tijdens de werkgroepen verteld wordt) zal je hier ook flink helpen.

Mocht je er echt niet uitkomen: print zowel aan het begin als het einde van de while loop (dus na "{" en voor "}") eventjes alle variabelen waar je mee werkt.

[edit]
Ik zie dat je ook net postte Je oplossing zal best werken, maar is meer een workaround dan een oplossing voor je probleem. Denk er nog even over na, hoewel ik me kan voorstellen dat je de opdracht al zat bent Dit is echter geen nette oplossing en zou in een echte omgeving waarschijnlijk nog meer kwaad doen.

[ Voor 18% gewijzigd door Ram0n op 26-11-2009 23:09 ]

[RobIII]

Verwijderd schreef op donderdag 26 november 2009 @ 23:07:
Mijn bevindingen van diepte waren zoals hierboven beschreven herhaaldelijk hetzelfde: exact 1 bij input 1. Ik heb het probleem uiteindelijk kunnen tackelen door de diepte buiten de for loop de verminderen en deze als externe variabele call by reference mee te geven.

Er is een verschil tussen --diepte en diepte--. Dat is hierboven al letterlijk voorgezegd. Verdiep je daar eens in en ontdek het zelf
En daar was je dus achter gekomen als je, ook zoals al meermalen gezegd, even de moeite had genomen om "diepte" te outputten/echo-en/loggen bij elke iteratie.

[ Voor 13% gewijzigd door RobIII op 26-11-2009 23:12 ]

[Verwijderd]

@RobIII
Even om slechte gevoelens uit de lucht te helpen, het gaat me echt niet om dat ik me kleine stukje opdracht correct in te leveren. Met zo'n instelling zou het al ingeleverd zijn Ik probeer vooral te begrijpen hoe de recursie in elkaar steekt en wat inderdaad de diepte op welke plek daarin een rol speelt.

Ik ken het verschil tussen --diepte en diepte--, ik zag alleen eerst niet wat dit kon uitmaken op de manier zoals ik hier gebruikte

[Soultaker]

Besef je nu ook dat --diepte óók verkeerd is, of was je nog niet zover?

[RobIII]

Verwijderd schreef op donderdag 26 november 2009 @ 23:25:


Ik ken het verschil tussen --diepte en diepte--, ik zag alleen eerst niet wat dit kon uitmaken op de manier zoals ik hier gebruikte

Dan ken je het verschil dus niet (goed)

[.oisyn]

RobIII schreef op donderdag 26 november 2009 @ 23:06:
Ondanks dat het antwoord je nu letterlijk is voorgezegd (thanks GuidoH);

Je kunt GuidoH best bedanken, want dat is het probleem helemaal niet zoals Soultaker ook al zegt

Maar aangezien je het nog niet schijnt te zien, hier een hint: je hebt een recursieve aanroep met huidige diepte 4. Dan roep je vanuit die staat een aantal keer mbv een loopje weer dezelfde functie aan. Welke diepte moeten die aanroepen krijgen? En wat krijgen ze nu?

[ Voor 33% gewijzigd door .oisyn op 26-11-2009 23:40 ]

[Verwijderd]

Verwijderd schreef op donderdag 26 november 2009 @ 23:25:
Ik ken het verschil tussen --diepte en diepte--, ik zag alleen eerst niet wat dit kon uitmaken op de manier zoals ik hier gebruikte

Je spreekt jezelf hier een klein beetje tegen...

[RobIII]

.oisyn schreef op donderdag 26 november 2009 @ 23:37:
[...]

Je kunt GuidoH best bedanken, want dat is het probleem helemaal niet zoals Soultaker ook al zegt

Ik moet écht even een keer op tijd gaan slapen

[doskabouter]

Is het maximaal aantal verschillende oplossingen niet iets in de trant van 42!/(2*21!) ?

[Soultaker]

Uitgaande van 6 rijen en 7 kolommen is 3⁴² is in ieder geval een bovengrens (elk vakje is bezet door speler 1, of speler 2 of geen van beide) en dat is al veel minder dan 42!/(2*(21!)). Maar er is zwaartekracht (een bezet vakje kan niet boven een leeg vakje voorkomen) en zetten alterneren.

Als we zwaartekracht in beschouwing nemen is het aantal mogelijkheden per kolom 2⁰ + 2¹ + .. + 2⁶ = 127. ⁷ = 127⁷ = 532,875,860,165,503 en dat is al weer een stuk minder dan 3⁴² (maar veel te veel om allemaal af te gaan).

Als ik meeneem dat zetten alterneren kom ik op 70,728,639,995,483; maar dat is inclusief spiegelingen en onbereikbare stellingen. Het totale aantal bereikbare stellingen zal ongeveer 10¹² zijn.

edit:
Het spel schijnt opgelost te zijn door Victor Allis. Leesvoer: A Knowledge-based Approach of Connect-Four (pdf)

[ Voor 28% gewijzigd door Soultaker op 28-11-2009 17:20 ]