Seuraa 
Viestejä9265
Liittynyt10.12.2006

Onko liian monimutkainen? Haluaisin tietää mikä mahtaisi olla tietokoneelta keskimääräinen suoritus tuossa pelissä. Siinä siis on ideana että toinen pelaaja tekee neljän nappulan rivin kahdeksasta eri väristä, ja toinen yrittää arvata sen rivin. Peli etenee niin että toinen lähtee arvailemaan. Jokaista oikeaa väriä kohti laitetaan valkoinen merkki ja jokaista oikeaa väriä, joka myös on oikealla paikalla, kohti laitetaan musta (tai punainen tai muu tummempi väri riippuen pelistä) merkki. Arvaaja yrittää selvitä mahdollisimman vähillä arvausriveillä.

Mikä lienee järkevin tapa lähteä ratkomaan riviä? Itse olen kartoittanut värejä tyylillä että laitan ensin neljä eri väriä ja seuraavaan loput neljä eri väriä. Saan osviittaa ainakin siitä kuinka monta väriä on käytössä ja mitä ne voivat olla..

くそっ!

Kommentit (6)

pöhl
Seuraa 
Viestejä917
Liittynyt19.3.2005

Enkkuwikistä löytyy pari linkkiä. Kannattaa varmaan lukea ne ensimmäiseksi.
[code:30arg932]==Algorithms==
With four pegs and six colors, there are 64 = 1,296 different patterns (allowing duplicate colors).

===Five-guess algorithm===

In 1977, [[Donald Knuth]] demonstrated that the codebreaker can solve the pattern in five moves or fewer, using an algorithm that progressively reduced the number of possible patterns.{{Cite journal |url = http://www.dcc.fc.up.pt/~sssousa/RM09101.pdf | authorlink = Donald Knuth | last = Knuth | first = Donald | title = The Computer as Master Mind | journal = J. Recr. Math. | issue = 9 | pages = 1–6 | year = 1976–77}}
The algorithm works as follows:

#Create a set ''S'' of remaining possibilities (at this point there are 1296). The first guess is aabb.
#Remove all possibilities from ''S'' that would not give the same score of colored and white pegs if they were the answer.
#For each possible guess (not necessarily in ''S'') calculate how many possibilities from ''S'' would be eliminated for each possible colored/white score. The score of the guess is the least of such values. Play the guess with the highest score ([[minimax]]).
#Go back to step 2 until you have got it right.

Subsequent mathematicians have been finding various algorithms that reduce the average number of turns needed to solve the pattern: in 1993, Kenji Koyama and [[Tony W. Lai]] found a method that required an average of 5625/1296 = 4.340 turns to solve, with a worst case scenario of six turns.{{Cite journal | last = Koyama | first = Kenji | last2 = Lai | first2 = Tony | title = An Optimal Mastermind Strategy | journal = Journal of Recreational Mathematics | issue = 25 | pages = 230–256 | year = 1993}} The [[minimax]] value in the sense of [[game theory]] is 5600/1296 = 4.341.{{cite book |first=Donald |last=Knuth |title=Selected papers on fun and games |publisher=Center for the Study of Language and Information |year=2011 |isbn=9781575865843|page=226}}

===Studies on ''Mastermind'' complexity and the satisfiability problem===

In November 2004, [[Michiel de Bondt]] proved that solving a ''Mastermind'' board is an [[NP-complete]] problem when played with ''n'' pegs per row and two colors, by showing how to represent any [[one-in-three 3SAT]] problem in it. He also showed the same for ''Consistent Mastermind'' (playing the game so that every guess is a candidate for the secret code that is consistent with the hints in the previous guesses).{{cite paper
|last=De Bondt
|first=Michiel C.
|title=NP-completeness of Master Mind and Minesweeper
|publisher=Radboud University Nijmegen
|year=2004
|month=November
|url=http://www.math.ru.nl/onderzoek/reports/rep2004/rep04_18.ps.gz
}}

The ''Mastermind satisfiability problem'' is a [[decision problem]] that asks, "Given a set of guesses and the number of colored and white pegs scored for each guess, is there at least one secret pattern that generates those exact scores?" (If not, then the codemaker must have incorrectly scored at least one guess.) In December 2005, [[Jeff Stuckman]] and [[Guo-Qiang Zhang]] showed in an [[arXiv]] article that the ''Mastermind satisfiability problem'' is NP-complete.[http://arxiv.org/abs/cs.CC/0512049 Mastermind is NP-Complete] Retrieved 2010-09-02.[/code:30arg932]

Taukkino
Seuraa 
Viestejä33
Liittynyt13.2.2011

// Raahen ammattioppilaitoksessa tehty, joskus ennen vuotta 2000

// Ei sisällä graafisia toimintoja, koska tehty niin alkeellisella C:llä.

// Merkeillä ja väreillä, ja varmaan toimii kaikissa C-kääntäjissä?

 

#include

#include

#include

/*         Funktioiden nimet */

 

int oikein(int arvotut[]);

int vaarin(int arvotut[]);

void arvo(int arvotut[]);

 

void main(void)

{

/*         Muutujien alustus */

 

           FILE *innimi;

           FILE *inpisteet;

 

           int nimilist[12][6];

           int nimi[12][6];

           int points[11];

           int pisteet=0,edpisteet=0;

           int arvotut[8],arvovara[4];

           int i,j;

           int ab,a,b;

           int ok,va;

           int poa;

           int merkki=0,merkki2=0;

           int lippu=0,lippu2=0,alku=1;

           int kierros=0,peliki=1,arpoja;

 

 

/*                    Enn„tyslistan alustus*/

   for (i=1;i<11;i++)

   {

   for (j=1;j<6;j++)

           {

           nimi[i][j]=NULL;

           nimilist[i][j]=NULL;

           }

   nimilist[i][1]=65;nimilist[i][2]=75;nimilist[i][3]=73;

   nimilist[i][4]=32;nimilist[i][5]=32;nimilist[i][6]=0;

   }

 

   for (j=1;j<11;j++)

           points[j]=255;

 

/*         Enn„tyslistan lattaaminen muistiin tai jos ei ole,

                       tallennetaan alustettu lista */

 

  if ((innimi = fopen("maminimi.dat","r")) == NULL)

           {

           if ((innimi = fopen("maminimi.dat","w")) == NULL)

           {

                      gotoxy(10,23);

                      printf("En voi avata Master Mindin pistelistaa.\n");

           }

   else

   {

 

           for (j=1;j<11;j++)

           for (i=1;i<6;i++)

                      fputc(nimilist[j][i],innimi);

           fclose(innimi);

    }

   }

   else

   {

   for (i=1;i<11;i++)

   for (j=1;j<6;j++)

           nimi[i][j]=fgetc(innimi);

   fclose(innimi);

 

 

   for (i=1;i<11;i++)

   for (j=1;j<6;j++)

   nimilist[i][j]=nimi[i][j];

 

   }

   if ((inpisteet=fopen("mamipist.dat","r")) != NULL)

   {

   for (i=1;i<11;i++)

           points[i]=fgetc(inpisteet);

   fclose(inpisteet);

   }

   else

   if ((inpisteet=fopen("mamipist.dat","w")) != NULL)

   {

   for (i=1;i<11;i++)

           fputc(points[i],inpisteet);

   fclose(inpisteet);

   }

 

           window(0,0,80,24);

 

 

/*         Alustetaan satunnaisgeneraattori*/

           randomize;

 

/*         P„„luuppi nro:1       */

 

           while(lippu!=10)

           {

 

/*         Tyhj„t„„n n„ytt” */

 

           gotoxy(0,0);

           for (i=1;i<26;i++)

                      printf("                                                                                                   \n");

 

/*         sekoitetaan satunnaisgeneraatoria */

 

           if (alku)

                      {

                                 gotoxy(50,3);

                                 printf("Anna satunnaisluku:1-10");

                                 gotoxy(50,4);

                                 scanf("%d",&arpoja);

                                 if (arpoja>10) arpoja=10;

                                 if (arpoja<1) arpoja=1;

 

                                 for (i=1;i

                                            random(arpoja);

                      }

 

/*         Nollataan liput       */

 

           lippu=0;lippu2=0;alku=0;

 

 /*        Kirjoitetaan n„ytt””n*/

           gotoxy(60,15);

           printf("Kierros: %d/5",peliki);

           gotoxy(50,3);

           printf("      Satunnaisrivi:%d    ",arpoja);

           gotoxy(50,4);

           printf("      ");

           gotoxy(35,1);

           printf("Master Mind");

           gotoxy(1,1);

           printf("Mestarilista:");

           gotoxy(60,2);

           printf("Poistu:A");

           gotoxy(60,1);

           printf("1,2,3,4,5,6,7,8");

           textcolor(15);

 

/*         Mestarilistan kirjoittaminen n„ytt””n       */

 

           for (i=1;i<11;i++)

           {

                      for (j=1;j<6;j++)

                                 {

                                            gotoxy(5+j,i+2);

                                            putch(nimilist[i][j]);

                                 }

 

                      gotoxy(1,i+2);printf("%d",i);

                      gotoxy(15,i+2);printf("%d   ",points[i]);

           }

 

/*         Nappuloiden "reikien" kirjoittaminen */

 

           for (i=1;i<11;i++)

                      {

                                 for(j=1;j<5;j++)

                                 {

                                 gotoxy(35+j*2,24-i*2);

                                 printf("%c",'*');

                                 }

                      }

 

/*         Arvotaan rivi         */

 

           arvo(arvotut);

 

/*         P„„luuppi nro: 2      */

 

           while ((lippu!=10)&&(lippu2!=15))

           {

 

/*         Rivilaskuri j         */

 

           for (j=1;j<11;j++)

           {

 

/*         Printataan arvausrivi*/

 

                      gotoxy(28,24-j*2);

                      printf("ssss_____* * * *");

 

/*         Merkki/nappulalaskuri i          */

 

           for (i=1;i<5;i++)

           {

 

/*         Merkki yl”s muuttujaan merkki    */

 

                      merkki=getch();

 

/*         Jos merkki nro, kirjoitetaan arvaustaulukkoon arvotut[5..8] */

 

                      if ((merkki>48) && (merkki<64))

                                 {

                                            arvotut[4+i]=merkki-48;

                                            gotoxy(35+i*2,24-j*2);

                                            putch(merkki);

                                 }

 

/*         Jos merkki kirjain A, asetetaan poistumislippu */

 

                      if ((merkki==65) || (merkki==97))

                                 {

                                            i=5;j=11;

                                            lippu=10;

                                 }

 

            }

 

                      if (lippu!=10)

                      {

                                 ok=0;va=0;

                                 for (i=1;i<5;i++) arvovara[i]=arvotut[i];

 

/*                               ok: oikeat arvaukset  */

                                 ok=oikein(arvotut);

/*                               va: vaarat arvaukset  */

                                 va=vaarin(arvotut);

 

                                 for (i=1;i<5;i++) arvotut[i]=arvovara[i];

                                 gotoxy(60,12);

                                 printf("t„ysin oikein:%d kpl",ok);

                                 gotoxy(60,13);

                                 printf("v„„r„ paikka:%d kpl",va);

                                 if (ok==4) lippu=20;

                                 if (ok>0)

                                  for (i=1;i

                                            {

                                             gotoxy(27+i,24-j*2);

                                             printf("%c",'.');

                                            }

                                 if (va>0)

                                 for (i=1;i

                                            {

                                             gotoxy(27+ok+i,24-j*2);

                                             printf("%c",'o');

                                            }

 

/*         Miinuksien v„hennyst„, jos 4 eri paikalla */

 

                                 if ((va==4) && (lippu!=5))

                                 {

                                            gotoxy(60,6);

                                            printf("4:n suora!");

                                            gotoxy(60,7);

                                            printf(" -5 pistett„!");

                                            merkki=getch();

                                            gotoxy(60,6);

                                            printf("               ");

                                            gotoxy(60,7);

                                            printf("                ");

                                            pisteet=pisteet-5;

                                            lippu=5;

                                 }

 

/*         Lippu=20, jos arvattiin rivi oikein         */

 

                                 if (lippu==20)

                                 {

                                  pisteet=pisteet+kierros*10+j;

                                  edpisteet=pisteet;

                                  if (pisteet>255) pisteet=255;

                                  if (pisteet<1)       pisteet=1;

                                  lippu=0;

                                  gotoxy(60,10);

                                  printf("Pisteesi: %d",edpisteet);

                                  gotoxy(60,5);

                                  printf("Onnittelut!");

                                  gotoxy(60,6);

                                  printf("%d siirtoa!",kierros*10+j);

                                  gotoxy(60,15);

                                  printf("Kierros: %d/5",peliki);

                                  gotoxy(60,17);

                                  printf("Paina jotakin");

                                  gotoxy(60,18);

                                  printf("n„pp„int„!");

                                  merkki=getch();

                                  arvo(arvotut);

                                  peliki++;

                                  kierros=0;

                                  lippu2=15;

 

/*         Pelikierrokset-muuttuja peliki>5, jos viides kierros   */

 

                                  if (peliki>5)

                                   {

 

/*         Etsit„„n tuloksen paikka enn„tyslistalla    */

 

                                            lippu2=15;

                                            points[11]=pisteet;

                                            peliki=1;

                                            pisteet=0;

                                            edpisteet=0;

                                            b=11;

                                            for (a=10;a>0;a--)

                                            {

                                            poa=points[a];

                                            if (poa>=points[b])

                                            {

                                            points[a]=points[b];

                                            points[b]=poa;

 

                                            for (i=1;i<6;i++)

 

                                                       nimilist[b][i]=nimilist[a][i];

                                            for (i=1;i<6;i++)

                                                       nimilist[a][i]=0;

                                            b--;

                                            }

                                            else a=0;

                                            }

 

/*         Printataan lista uudestaan, jos p„„stiin listalle      */

 

                                            if (b<11)

                                                       gotoxy(1,15);

                                                       printf("Anna 5 merkki„!");

                                                       {

                                                       for (i=1;i<11;i++)

                                                       {

                                                       for (j=1;j<6;j++)

                                                       {

                                                       gotoxy(5+j,i+2);

                                                       putch(nimilist[i][j]);

                                                       }

 

                                                       gotoxy(1,i+2);printf("%d",i);

                                                       gotoxy(15,i+2);printf("%d   ",points[i]);

                                                       }

 

/*         Jos p„„stiin listalle kysyt„„n nimi         */

 

                                                       for (a=1;a<6;a++)

                                                                 {

                                                                  gotoxy(5+a,b+2);

                                                                  merkki2=getch();

                                                                  if (merkki2>32)

                                                                            {

                                                                            putch(merkki2);

                                                                             nimilist[b][a]=merkki2;

                                                                            }

 

 

                                                                 }

 

/*         Tallennetaan mestarilista levylle           */

 

                                                       if((innimi=fopen("maminimi.dat","w"))!=NULL)

                                                                 {

                                                                 for (a=1;a<11;a++)

                                                                 for (b=1;b<6;b++)

                                                                            fputc(nimilist[a][b],innimi);

                                                                  fclose(innimi);

                                                                 }

 

                                                       else

                                                                 {

                                                                  gotoxy(1,23);

                                                                  printf("Listan tallentaminen ei onnistu!");

                                                                 }

                                                       if ((inpisteet=fopen("mamipist.dat","w"))!=NULL)

                                                                 {

                                                                 for (a=1;a<11;a++)

                                                                            fputc(points[a],inpisteet);

                                                                  fclose(inpisteet);

                                                                 }

 

                                                       }

 

 

 

                                     }

                                   i=1;j=11;

                                 }

 

                      }

           }

           if (lippu2!=15) kierros++;

 

           }

           }

 

 

}

 

/*         Funktiot   */

 

int oikein(int arvotut[])

{

           int ab,ok=0;

           for(ab=1;ab<5;ab++)

           {

                      if (arvotut[ab]==arvotut[ab+4])

                      {

                       ok++;

                       arvotut[ab]=10;arvotut[ab+4]=11;

                      }

           }

           return(ok);

}

 

int vaarin(int arvotut[])

{

           int a,b,va=0;

           for (a=1;a<5;a++)

            {

           for (b=1;b<5;b++)

            {

                      if ((a!=b) && (arvotut[a+4] == arvotut[b]))

                                 {

                                 va++;

                                 arvotut[b]=12;

                                 b=5;

                                 }

           }

           }

return(va);

}

 

void arvo(int arvotut[])

{

           int i;

           for (i=1;i<5;i++)

                      arvotut[i]=random(8)+1;

}

Taukkino
Seuraa 
Viestejä33
Liittynyt13.2.2011

Sori includeista oli pudonnut kirjastot stdio.h, conio.h, stdlib.h, ne katosivat koska kulmasulkunotaatio oli käytössä näilä sivuilla muutoin, kuin tekstinä....

 

Suosituimmat

Uusimmat

Uusimmat

Suosituimmat