[C++] Mastermind 'valsspeel algoritme'.

[Verwijderd]

Hoi,

Ik ben voor mijn opleiding een tijdje geleden begonnen met het leren van C++, en moet nu onder andere het spel mastermind programmeren. Dit is natuurlijk niet zo heel erg lastig, maar ik moet ook proberen om het de gebruiker zo lastig mogelijk te maken. Dat houdt in dat de computer, op het moment dat de gebruiker de juiste code raadt, de code moet veranderen, zonder dat er tegenstrijdigheden ontstaan met de eerder gegeven aanwijzingen (als dat tenminste mogelijk is)... De computer onthoudt dus de eerder ingevoerde 'gokken' van de gebruiker, en de antwoorden (in de vorm: x goed en y goed, maar verkeerde plaats) die daarbij zijn gegeven, en aan de hand daarvan wordt een (nieuwe) code bepaald die daarmee niet strijdig is. Maar heeft iemand een idee met wat voor algoritme zo'n code snel te vinden is? Alle mogelijke codes afgaan werkt wel voor kleine reeksen, maar het programma moet ook werken met reeksen van lengte 20, en 20 kleuren, dus dan zijn er 20^20 mogelijkheden. Op de een of andere manier moeten een heleboel kansloze combinaties bij voorbaat al worden genegeerd, maar ik heb helaas geen idee hoe ik dat moet aanpakken.

Is d'r hier iemand iemand die een idee of algemene hint heeft om me op de goede weg te helpen?

Alvast bedankt,

Sjoulibsky.

[thomaske]

Heb geen advies over het daadwerkelijk algoritme, maar is het misschien een idee om na iedere beurt bij te houden welke codes nog voldoen, zo spreid je de 'rekenkracht' over de beurten ipv alles aan het einde

[Verwijderd]

thomaske schreef op 06 november 2004 @ 17:05:
Heb geen advies over het daadwerkelijk algoritme, maar is het misschien een idee om na iedere beurt bij te houden welke codes nog voldoen, zo spreid je de 'rekenkracht' over de beurten ipv alles aan het einde

Dat was ook de algemene tip van de docent, en dat zal me ook wel lukken, maar de gebruiker moet ook kunnen instellen dat hij wil spelen met reeksen van lengte 20, en 20 kleuren. Dus als ik voor iedere mogelijkheid wil bijhouden of die code nog mogelijk is, heb ik een array nodig van 20^20 elementen. En dat was dan weer niet de bedoeling...

[MSalters]

thomaske schreef op 06 november 2004 @ 17:05:
Heb geen advies over het daadwerkelijk algoritme, maar is het misschien een idee om na iedere beurt bij te houden welke codes nog voldoen, zo spreid je de 'rekenkracht' over de beurten ipv alles aan het einde

Open deur: Nee, dat is geen goed idee. Weet je hoeveel codes er nog voldoen na beurt 1?

[H!GHGuY]

kun je niet een opbouwend algoritme maken die de eerstvolgende mogelijk combinatie zoekt ipv combinaties te schrappen?

[moto-moi]

mastermind is toch met 4 kleurtjes ? Of heb je er meer ?
Stel dat het 4 kleuren zijn, dan maak je een multidimensionele array, in die array zet je _alle_ mogelijke opties, dus bijv:
AAAAAAAAAAAAAAAAAAAA
BBBBBBBBBBBBBBBBBBBB
CCCCCCCCCCCCCCCCCC
DDDDDDDDDDDDDDDDDD
EEEEEEEEEEEEEEEEEEEEEEE

etc.
Als een beurt is geweest streep je af welke opties er gebruikt zijn, waardoor je dus op het moment dat de juiste keuze wordt gemaakt heel makkelijk kun scannen welke opties je nog over hebt.

[Soultaker]

Volgens mij is dit nog best wel tricky. Kun je het niet probabilistisch aanpakken? Bij een vraag van de speler probeer je maximaal, zeg, een miljoen willekeurige combinaties. Vervolgens kijk je welke daarvan consistent zijn met de eerdere vragen (en jouw antwoorden daarop), en van de combinaties die in aanmerking komen kies je degene die de minste witte en zwarte staafjes als antwoord oplevert (om zo weinig mogelijk informatie te geven). Als je geen consistente combinatie kon vinden, dan moet je maar vasthouden aan de combinatie van de vorige keer (en dan ben je waarschijnlijk genaaid).

Geen idee of dit goed genoeg werkt, maar in ieder geval in het begin kun je op die manier heel vaak heel weinig pinnetjes aan informatie ´weggeven´.

[ Voor 3% gewijzigd door Soultaker op 06-11-2004 18:11 ]

[Soultaker]

Wat je 'eigenlijk' wil, maar wat goed ingewikkeld is, is je antwoord steeds zo kiezen dat de overgebleven mogelijkheden zo veel mogelijk vragen vereisen om op te lossen. Dat is dus nog niet eens hetzeldfe als het antwoord zo kiezen dat je zo veel mogelijk mogelijkheden over houdt (wat ook al lastig is).

[Verwijderd]

denk foutje... lama

[ Voor 100% gewijzigd door Verwijderd op 06-11-2004 18:26 ]

[Grijze Vos]

Soultaker schreef op 06 november 2004 @ 18:14:
Wat je 'eigenlijk' wil, maar wat goed ingewikkeld is, is je antwoord steeds zo kiezen dat de overgebleven mogelijkheden zo veel mogelijk vragen vereisen om op te lossen. Dat is dus nog niet eens hetzeldfe als het antwoord zo kiezen dat je zo veel mogelijk mogelijkheden over houdt (wat ook al lastig is).

En dat is ook meteen onmogelijk op te lossen, volgens mij.

[NetForce1]

Je kunt om te beginnen kleuren die al vast staan dmv zwarte/witte pinnetjes bepalen, je hoeft dan al heel wat minder combinaties na te gaan lijkt me

[Verwijderd]

Hier een link waar op het oplossen wordt ingegaan:
http://www.cut-the-knot.org/ctk/Mastermind.shtml

Het originele spel (4 posities, 6 kleuren, 10 kansen) blijkt eigenlijk de term "spel" niet waard te zijn: de java applet maakt in 5 pogingen max gehakt van elke code. Resistance is futile .

Edit: Respect !

[ Voor 16% gewijzigd door Verwijderd op 06-11-2004 21:47 ]

[odysseus]

Volgens mij is dit wel haalbaar. Je kunt een goede alternatieve oplossing als volgt opbouwen:
zet in je conceptoplossing alle al goed geraden posities 'vast' - deze doen niet meer mee bij het bepalen van een alternatieve oplossing.
Zoek vervolgens uit of er nog kleuren zijn waar nog niets over bekend is voor de gebruiker. Zijn die er, dan vul je alle overgebleven plaatsen op met die kleur en dan ben je klaar.
Zijn die er niet, dan wordt het een stuk lastiger. Je kunt dan aan de slag gaan met kleuren die al wel getest zijn, maar waarvan de gebruiker de plaats nog niet weet. Zet die overal neer behalve op de al geteste plaatsen voor die kleur. Mocht je dan nog niet alle plaatsen hebben opgevuld, dan doe je hetzelfde met een andere kleur waarvan alleen de aanwezigheid en niet de plaats bekend is. Zo blijf je doorgaan - als je op een gegeven moment geen kleuren meer hebt en nog plaatsen 'open' hebt, dan is er geen mogelijke oplossing meer en wint de gebruiker. In alle andere gevallen heb je een nieuwe oplossing gevonden.

Ik twijfel overigens of het inderdaad zo simpel is - anders had iemand het vast al eerder als oplossing aangedragen .

[Mastermind]

Ik denk dat je het beste een binaire boom kunt gebruiken met seperate chain hashing. Hierbij hou je een array met gelinkte lijsten bij, waarbij de hashfunctie je vertelt in welke lijst een item X te stoppen en dan, gedurende een find welke lijst X bevat. Doordat het zoeken door een gelinkte lijst een lineaire operatie is zal het zeer snel gaan.

[Verwijderd]

Je kan de code formuleren op basis van de gestelde vragen door de code kraker. De code staat dan pas bij de laatste vraag (alles goed) vast.

De code kan systematisch gekraakt worden door middel van afkappen van de oplossingsruimte. Het doel van je programma is het zo lang mogelijk te rekken van het afkappen van de oplossingsruimte tot 1 element.

De tijd nodig om de oplossing te vinden blijkt direct gerelateerd te zijn aan de omvang van de oplossingsruimte (Zie mijn post hierboven voor een paar linkjes). Het is de kunst de antwoorden op vragen zo te formuleren dat de oplossingsruimte zo langzaam mogelijk krimpt. Wat het programma moet doen is bij elk mogelijk antwoord nagaan hoe groot de oplossingsruimte daarna nog is. Komt deze op 1, dan is de code gekraakt. Komt deze op 0, dan is het antwoord een onwaarheid . Door het antwoord dat bij de grootste oplossingsruimte hoort te geven wordt het vinden van de code zo lang mogelijk uitgesteld.

De oplossingsruimte bij n posities en m kleuren bestaat uit m ^ n elementen. Verder bestaat er verband tussen de elementen in de oplossingsruimte en alle gegeven antwoorden: het restant aan elementen past steeds op alle reeds gegeven antwoorden. Dan is het een kwestie van schrappen.

[H!GHGuY]

odysseus schreef op 06 november 2004 @ 22:33:
Volgens mij is dit wel haalbaar. Je kunt een goede alternatieve oplossing als volgt opbouwen:
zet in je conceptoplossing alle al goed geraden posities 'vast' - deze doen niet meer mee bij het bepalen van een alternatieve oplossing.
Zoek vervolgens uit of er nog kleuren zijn waar nog niets over bekend is voor de gebruiker. Zijn die er, dan vul je alle overgebleven plaatsen op met die kleur en dan ben je klaar.
Zijn die er niet, dan wordt het een stuk lastiger. Je kunt dan aan de slag gaan met kleuren die al wel getest zijn, maar waarvan de gebruiker de plaats nog niet weet. Zet die overal neer behalve op de al geteste plaatsen voor die kleur. Mocht je dan nog niet alle plaatsen hebben opgevuld, dan doe je hetzelfde met een andere kleur waarvan alleen de aanwezigheid en niet de plaats bekend is. Zo blijf je doorgaan - als je op een gegeven moment geen kleuren meer hebt en nog plaatsen 'open' hebt, dan is er geen mogelijke oplossing meer en wint de gebruiker. In alle andere gevallen heb je een nieuwe oplossing gevonden.

Ik twijfel overigens of het inderdaad zo simpel is - anders had iemand het vast al eerder als oplossing aangedragen .

dit is nou net wat ik zei, maar een beetje meer uitgebreid...

[De Cowboy]

Misschien een beetje kortzichtig, maar als je iets verandert wat de radende persoon toch nog niet weet, maakt dat toch helemaal niet uit ?

[ Voor 5% gewijzigd door De Cowboy op 07-11-2004 20:29 ]

[Verwijderd]

Hoikes,

Ik ben iemand die uit een oud tijdperk kom en nog ben opgevoed met visual basic, html en css codekes. Ben nu 41 en helemaal uit dat circuit
Heb een kaartdeck zelf ontworpen en wil eindelijk een simpele algoritme C++ inschakelen maar omdat ik zo lui en oud ben geworden...Heb ik een wix.com abonnement, dus gewoon lui een website maken.
Ik herinner mij de mapjes in mijn uploaden en toen ik alles zelf ontwierp was dat eindelijk gemakkelijker.

*knip spam* is mijn website en wil gewoon een code in plaatsen via wix website-maker. Maar heb zo het idee dat onmogelijk is en kan me er niet meer op contrentreren.

Wat is mijn doel en vraag hier?

Doel 40 kaarten , drukknop , willekeurige shuffle .

Ga even Vb geven van een website die zoiets doet.

*knip spam*

Vraag :

Vrij simpel, maar ik kan het niet meer en teveel opzoekwerk. Laat mij een persoonlijke mailtje achter als je mij helpen kan.
Denk de moeilijkheid bij wix zal liggen, daar heb ik al html ingevoegd maar ik zie daar gewoon niks bewegen. Heb nu wel jaar betaald, eventueel kunt u eens in dat systeem zien hoe ik meer controle krijg. De tijden ik scriptjes heerlijk in html gooide is precies van mijn frequentie verdwenen.lol

Sorry

[ Voor 3% gewijzigd door NMe op 19-11-2017 20:59 ]

[NMe]

Ja joh, schop vooral een 13 jaar oud topic dat totaal niet aan je vraag gerelateerd is omhoog met een warboel aan zinnen waar niemand zonder weet van wat je aan het doen bent uit kan komen. Daarnaast spam je ook nog eens je eigen website én vraag je om persoonlijke hulp via mail, wat ook allebei niet de bedoeling is op dit forum.

Lees De Quickstart eens door om te zien hoe het wel hoort en open dan gerust een nieuw topic met je vraag. Dit topic gaat dicht.

[ Voor 19% gewijzigd door NMe op 19-11-2017 20:57 ]