Oppgava er svært enkel, og basert på spelet Master Mind, med enkelte modifiseringer.

Brettet du skal spele på har her 5 felt bortover, organisert slik:
I tillegg er det uendelig langt. I kvart av felta <tall> vil det vere eit tall mellom 0 og F (heksadesimalt). Det burde gi 16^5 kombinasjoner, altså 1048576. Ved vill gjetting (bruteforce) burde det ta i snitt 524288 forsøk. Imidlertid så skal det gå fint å lage ei god algoritme som løser dette på betydlig færre forsøk.

Oppgava er å lage et program som gjetter seg fram til kombinasjonen av dei 5 talla så fort som mulig, med færrast mulig forsøk. Når programmet blir starta vil det begynne med å printe ei linje med fem valgfrie tall slik:
Deretter vil "spillet", mastermind, svare med 0, 1 eller 2 for kvart felt. 0 vil sei at tallet er heilt galt. 1 vil sei at tallet finst i koden, men er feil plassert. 2 vil sei at tallet er rett plassert. Dersom vi tenker oss at det tallet vi skal gjette oss fram til er A 0 3 2 9 så vil spillet svare med følgande:
som da indikerer at A er rett plassert, D ikkje finst i tallet en skal gjette seg fram til, og at 9 finst, men er feilplassert.

La oss ta et fullt eksempel fram til ferdig løst kode. Det hemmelige tallet vi skal gjette oss fram til er 1 2 3 4 5 her, for enkelheitsskuld.
Når programmet er ferdig skal det printe kor mange forsøk det brukte på å komme fram til rett resultat.

Kjøretid er uviktig, det viktige her er tall forsøk som blir brukt.

Programmet vil bli testa med 10 ulike, tilfeldige, tallsett. Det er gjennomsnittlig tall forsøk i løpet av dei 10 rundane som teller.

Når det gjelder tillate språk så er det veldig enkelt. Eg har eit par vilkår:

1. Eg skal kunne kjøre det uten alt for mykje bry.
2. Du kan bruke eksterne bibliotek dersom du vil. I såfall må dei finnast til Linux
3. Ikkje lag GUI. Eg vil ha tekst-versjon for å automatisere testinga av dei.
4. Du må skrive ut tall forsøk du brukte på slutten
5. Kildekoden må vere tilgjengelig for meg, ellers vil det ikkje bli kjørt!
6. Generelt blir eg glad om det blir i ett av følgande språk: c, c++, java, php, perl eller brainfuck. Gigantisk bonus til dei som gjennomfører det i BrainFuck.

Er det en deadline, og er dette en slags konkurranse?
Neither way, I'm in.

kan jeg spørre hvorfor du vil ha et slikt program?

se på det som en konkuranse med inspirasjon fra bruteforcetråden. =)

Dette er altså forskjellig ved at du får svar som er rettet mot hvert individuelle felt?

Hater_mordin: Det er en programmeringsoppgave (det står i tittelen), og gøy for de som liker programmering og/eller konkurranser. (Vet ikke helt om dette er en konkurranse)

Ikke akkurat en konkurranse, mest for moro og for å se om man får til selve oppgaven. Det er ikke alltid like enkelt å finne på oppgaver selv, derfor er slike tråder glimrende til akkurat dette.

Hater_mordin: Som Grantax påpeker; det er en morooppgave for for å teste programmeringsferdigheter, ikke et program han trenger i praksis.

Fordi han er n00b.
Java = teh horror.

Ei runde kan ha duplikate tall ja. Det er tilfeldig trekt, uavhengig av resten av serien.

Og sjølvsagt kan folk skrive i python, glømte bare å skrive det opp på lista.

Og m0b har nok rett. Det er ingen formell konkuranse, bare ei oppgave eg har tenkt litt på, og er spent på å sjå resultatet. Tenkte å sjå gjennom resultatet om ei ukes tid og kåre "vinneren" i den som har best algoritme.

Vil vinneren da bli kåret ut fra gjennomsnittlig antall forsøk som trengs for å knekke koden?

Ja. Det er tal forsøk som trengst som tel.

hm, så på kildekoden din mens jeg lagde selve spillet selv og la merke til noe jeg lurer på...

Vidarlos eksempel:
1 2 3 4 5
M: 9 4 8 1 4
S: 0 1 0 1 0

her tror jeg spillet ditt ville svart "S: 0 1 0 1 1" istedenfor "S: 0 1 0 1 0" pga. at spillet ditt bare sjekker om 4 i "M: 9 4 8 1 4" er der eller ikke. Så spillet ditt sjekker begge firerne i "M: 9 4 8 1 4" og setter 1 som respons på begge de mens vidarlo sin ikke gjør det.

Så det jeg lurer på er om spillet skal svare "S: 0 1 0 1 1" eller "S: 0 1 0 1 0" til "M: 9 4 8 1 4" der løsningen er "1 2 3 4 5".

Dette ble kanskje litt kaotisk, men håper dere skjønner spørsmålet...

jeg ville sagt s: 0 1 0 1 0 ellers vil det jo tolkes som at det skal være 2x 4 i svaret.

Pjukern si tolking er heilt rett. Eg tok med et duplikat-eksempel i håp om å få fram nettopp det.

Han må jo ikke endre noenting. Hvis jeg ønsker ett program som tester ut alle 16^5 kombinasjoner, så har jeg jo lov til det. Det programmet kommer dog sannsynligvis ikke til å vinne.....

I så fall er ms office AI.

Det at programmet reagerer utifra input er ikkje det som blir kallt AI, ettersom du utmerka godt kan skrive perfekt solver for det problemet der, med statisk, enkel algoritme på få linjer, som alltid gjer predefinerte ting.

Les definisjonen på AI du

Den enklaste måten å løyse den oppgava på er med ei fastlagt algoritme, som gjer steg ut frå svaret den får tilbake. Det er ikkje det som blir omtalt som AI, all den tid den ikkje lærer av det, men berre gjer ei heilt fastlagt oppgåve, uten tilfeldige element. Då kan du lage algoritmer som garantert aldri treng meir enn y forsøk.

Om man lager en algoritme som prøver alle kombinasjoner er det bruteforcing, fullt mulig men fantastisk lite effektivt. Donald Knuths algoritme (som er en av de mest kjente for å løse Mastermind på maks 5 iterasjoner) er veldig effektiv men det er ikke kunstig intelligens, algoritmen lærer ikke av tidligere oppgaver den har løst men følger et visst sett regler man gir den (som f.eks å ikke bytte ut felter den allerede har fått positiv respons på).

Man kan også implementere oppgaven som en Genetisk Algoritme, dog ser jeg ikke helt poenget (med mindre oppgaven da blir gitt spesifikt med mål om å lære mer om genetiske algoritmer og nevrale nettverk)

Jeg mener fremdeles at inteligens ikke trenger å være mer avansert enn at man er i stand til å bestemme neste handling ut i fra svaret på forrige handling. Det er jo akkurat det som burde skje her.

Jeg velger å tro at en datamaskin ikke er i stand til å tenke selv. Med 'tenke' mener jeg da å komme opp med ting som ikke er basert på svar på tidligere handlinger (beregninger eller sånt).

Ved siden av veien er jeg forsåvidt ikke helt overbevist om at det finnes noen slik ting som det å tenke selv, ettersom de fleste tingene vi gjør er utløst av en slags programmering (nerdete term) vi mennesker har. Vi føler behov for å gjøre noe, og gjør det. Det kommer fra en plass, og alle gjør ulike ting i ulike situasjoner. Det ligger jo i vår personlighet, som igjen er forhåndsbestemt. Om vi velger å endre på den, så er jo det også forhåndsbestemt. Det finnes et godt ord for denne type tankegang - skjebnen.

Alternativ løsning: Du sier 'far fetched', ikke umulig.

Tias: Jeg mener GA burde være meget bra egnet for nøyaktig dette formålet, jeg leker litt med tanken på å implementere dette og se hvordan det går.

Det burde vel være et minimum... er ikke det bare å teste 0 0 0 0 0, 1 1 1 1 1, osv. til man finner riktige tall? Jeg har kommet frem til en algoritme som ser ut til å trenge maks 6 forsøk, men jeg har ikke implementert den ennå.

mr_eff: skjønner ikke helt hva du mener med "bare teste .." til man finner riktige tall, som du forklarer det tror jeg nok du vil ende på veldig mange forsøk.

Er veldig mange ting som spiller inn her, hvis man f.eks skal ha en virkelig optimal algoritme må man ta hensyn til at når man har fått en "2" så må man deretter bruke den plassen til å teste utestede tall for å eliminere søkerommet videre.
I tillegg så er vanskelig å si hva som er mest effektivt; bør man teste "kjente" tall på random plasser for å prøve å finne korrekt posisjon eller bør man ha en litt mer random fremgangsmåte?

Veldig mange forsøk? Si at tallet er 0 1 2 3 4:

0 0 0 0 0
0 1 1 1 1
0 1 2 2 2
0 1 2 3 3
0 1 2 3 4

Er vel ikke verre enn det? Og selv om det hadde vært høyere tall der, så burde det vel uansett la seg gjøre på rundt 15 forsøk.

Well, no er jo AI eit definert faguttrykk og din bruk faller ikkje inn under det folk tenker som på AI.

Å bestemme ei handling ut fra ei anna vil ikkje sei at maskina kan tenke, det vil bare sei at maskina har ei algoritme som tar hensyn til tilbakemelding/input.

AI vil sei at i to kliss like situasjoner kan maskina gjere ulike ting. Dersom den følger samme algoritme kvar gong vil responsen alltid vere lik ved lik input.

No har eg og TheGEEK diskutert litt på IRC om behandling av duplikate tall. I has algoritme var det stor forenkling å anta at tall vil gi 1 uansett om dei forekjem fleire ganger.

Eg er tilbøyelig til å vere einig med han i at det er den realistiske løysinga.

Eksempel
Tallet vi tenker på er 24985
Tallet datamaskina gjetter er 24204
Svaret fra spillet blir då 22101

Håper dette klargjorde ting.

Joda, men gitt samme input vil samme handling bli gjort om du kjører programmet 3000 ganger. I et AI-program vil det vere element av tilfeldigheit.

Egentlig er spørsmålet da hvilken som skal få tallet 1, og hvorfor.
Men er fortsatt ikke enig med deg at man burde ha "1" for alle tall som er i svaret, det blir jo helt feil.

I min kode laget jeg det sånn at den tar den første fra venstre, også lar resten være 0.

I følge vanlige MasterMind-regler er det jo slik det skal gjøres. Det blir mer riktig enn å villede koden med å reagere på flere eksemplarer av samme tall.

Hva er det du mener jeg ikke har forstått? Jeg er selvfølgelig klar over at det er snakk om hexadesimale tall, derav 15 forsøk (man tester 0 til E, og antar F om man ikke har fått noen treff). Hvor mange tall man skal finne spiller vel ingen rolle, så lenge men kan teste alle samtidig? Jeg går selvfølgelig heller ikke ut i fra at jeg treffer rett på første forsøk, men selv om man begynner med 0 og så inkrementerer hvert tall med én for hvert forsøk, så bør det uansett ikke ta mer enn 15 forsøk for å finne alle tallene.

Nå vet jeg ikke om jeg har tid til å implementere den algoritmen jeg har kommet frem til med det første, men jeg kan jo gi en beskrivelse av den her, i form av et eksempel...

Jeg vet ikke om det siste der bør telle som ett forsøk, siden det mangler bare ett siffer, og gjenstår bare ett tall, så spillet vet hva koden er uten å måtte teste den.

Hvis spillet treffer rett på ett tall (får "2" første gangen tallet prøves) legges dette tallet til igjen på slutten av rekken med tall som gjenstår å prøve, siden tallet kan dukke opp flere ganger:

Jeg hadde tenkt å bruke en klasse som holder styr på alle de 16 tallene, med ett objekt for hver posisjon, dvs. hvert av de fem tallene. 0 som resultat fjerner det testede tallet fra alle posisjonene, 1 fjerner tallet fra posisjonen hvor tallet ble testet, men legger det til som det første tallet som blir testet i alle andre posisjoner (hvor svaret ikke allerede er funnet), 2 gjør det samme som 1, bortsett fra at det legger til tallet som det siste som blir testet. Eksemplene jeg postet tidligere var en litt forenklet versjon av dette.

Kan du gi en forklaring av hvordan du gjør det? Har ikke peiling på Python, og vil helst slippe å prøve å tyde disse scriptene.

Ja, du tenker iallefall veldig likt meg, jeg og gjorde det på den måten der først, men fant ut at det er enklere/raskere å heller holde styr på hvilke tall som er kjent og hvilke posisjoner man har testet de i. Så genererer man bare alle tall/posisjoner fra tall som ikke er prøvd og trekker så fra alle de tallene/posisjonene man har testet. Da ender man opp med en liste over alle utestede tall/posisjoner.
Så er det bare å prøve.
Er nok mange mulige strategier, men jeg velger å prøve alle "ubekreftede" tall _før_ jeg begynner å prøve mulige posisjoner for kjente tall.

Begynte på det i dag, og er nesten ferdig. Jeg vet ikke om jeg har den beste algoritmen i verden, men jeg gidder ikke være lame å google det.

Siden jeg ikke klarer å takke nei til en utfordring så skal du ikke se langt etter brainfuck versjonen, den kommer faktisk til å bli veldig enkel å omskrive fra programmet jeg har vil jeg tro.

Interessant oppgave!

Noe jeg egentlig har hatt litt i bahodet en stund, men aldri somlet meg til å gjøre.

Er ganske rusten på C++ og php er gresk. Kikket på Brainfuck nå nylig, som jeg aldri har vært borti før, og DET var et treffende navn på programmeringsspråk ja!
Uten at jeg vil love noe, så skal jeg se om jeg og kan hoste opp noe. (IKKE i brainfuck nei)

(Oops, klarte å gi en feil KP her, menmen det var ikke så verst det innlegget heller. Vidarlo's var deaktivert for KP? er litt ny ang KP's..)

Jeg har også begynt. Løsningen min fungerer forsåvidt greit nok allerede, men tror jeg skal fine tune gjetningsalgoritmen min litt før jeg leverer.

Hmm, dersom testinga di skal gå så smertefritt som mulig, har du andre villkår som input via argv, eller antall forsøk til en spesiell output stream?

Jeg har et greit antall forsøk, men programmet trenger en siste touch som jeg tror vil gjøre det ganske mye bedre.

Grantax: Applikasjonet skal avvente input fra "bruker" som sier 1 2 0 1 0 1 osv - så du trenger kun å avvente input pr iterasjon og tolke det deretter.

Ops, nå har jeg misforstått mye, jeg har skrevet delen som gir input til programmet mitt også. :/ Jaja. Blir litt omskriving nå.