[c++] Boter kaas en eieren maken

[Verwijderd]

Ik ben bezig met boter kaas en eieren.

Heeft er iemand een idee hoe je zou kunnen bijhouden of een rij vol is? Ik maak hem namenlijk in 3d en dan heb je 100 mogelijkheden om te winnen.

Hoe zou je dit makkelijk kunnen doen?

[Dennis]

Drie geneste for loopjes
x, y en z coördinaten

[Verwijderd]

Ook wel een leuke manier:

3x3x3 = 27 vakken

neem nu een unsigned long (32 bits) voor elke speler.
Elke gesette bit daarin stelt voor die speler voor dat daar het kruisje/rondje staat.

Maak een array met alle mogelijke wincombinaties (maakt niet uit welke speler). Voor 3D zijn dit dan 100 unsigned longs (volgens je eigen woorden). De code hiervoor kan je door een tweede progje te schrijven genereren. Elke long geeft een winsituatie aan (doordat bepaalde bits gezet zijn).

Wanneer je nu wilt weten of een speler gewonnen heeft, dan ga je alle unsigned longs af en XOR je deze met die van je speler. Komt hier nu 0 uit (32 niet gesette bits) voor 1 van die combinaties, dan heeft die speler gewonnen.

Dit doe je dus voor alle spelers.

Wanneer je wilt weten of een speler een bepaalde zet mag doen, kan je het volgende doen: check voor alle andere spelers of die, die bepaalde bit geset heeft (in hun unsigned long) (welke bit bereken je door gewoon het product x+y*x_max+z*z_max te nemen (voor x,y,z elementen uit 0, 1 en 2)). Zo ja, dan kan die zet niet gedaan worden.

Een nieuw spel begin je door alle unsigned longs van de spelers op 0 te stellen. De 100 elementen tellende unsigned long array kan je globaal definieren als bijvoorbeeld:

unsigned long wincombinaties[] = { 1241432, 23542345, ... };

Op deze manier maakt het zelfs niet uit hoeveel spelers er meedoen...

Maar goed, je moet dus eerst die array met 100 winmogelijkheden genereren. Hoe je dat zou kunnen doen: alle mogelijkheden afgaan... ff denken, zijn dat niet (3x3x3)! mogelijkheden? (27! = groot)... dus op die manier gaat dat niet.

[Verwijderd]

Oh boy. Ikke ga ff newbie spelen :-)

Ben nog maar een beginner dus ff wat vraagjes.

Unsigned dat betekent dat die groter is dan 0 toch?

Enne, zo'n unsigned long als dat dan bv 111 is dan betekent dat dat er bv helemaal linksonder(x=1,y=1,z=1) een tekentje staat ofzo?

[Orphix]

Als je niet weet wat unsigned betekent, misschien moet je dan eerst proberen een 'gewoon' 2D boter-kaas-en-eieren te maken. Bv met een onoverwinnelijke computer speler. Hierdoor krijg je meer inzicht in het spelletjes alsmede de taal waardoor je het in '3D' uiteindelijk makkelijker zal kunnen maken dan dat je nu met veel moeite het in 1x probeert.

[Verwijderd]

Ik ben hem ook eerst ff in 2d aan het maken maar het ging mij vooral ff om het principe

[Verwijderd]

Ik heb een manier gevonden om de wincombinaties te vinden voor een 3d bother kaas en eieren, als je de manier gebruikt zoals ik die hierboven heb neergezet.

Vanavond heb ik een of ander saai feestje, dus ik zal er dan even over nadenken en misschien vandaag of morgen nog wel even wat code posten.

[Killemov]

3D-Array ([3][3][3]) van bytes, 0 = Leeg, 1 = X, 2 = O

Je moet dan iteren over alle vakken met 3 geneste for-loops (X, Y, Z) en dan in de binnenste loop een aantal keer de functie 'checkline (X, Y, Z, RX, RY, RZ)' aanroepen met alle combinaties van 1, 0, -1 (dus weer 3 geneste for-loops) voor RX, RY en RZ, behalve 0, 0, 0. RX, RY en RZ zijn dan dus richtingsvectoren. Binnen checkline moet je dan boundary-checking doen en een lijn proberen te volgen met de richting RX, RY, RZ. voorbeeld checkline (0, 0, 0, 1, 1, 1) Kijkt dus vanaf 0, 0, 0 diagonaal richting de andere hoek van de kubus.

Even 4 voorbeeldscenario's.

Staat er op 0,0,0 een 0 ? => return 0.
Staat er op 0,0,0 een 1? Staat er op 1,1,1 een 1 ? Staat er op 2,2,2 een 1? => return 1
Staat er op 0,0,0 een 2? Staat er op 1,1,1 een 2? Staat er op 2,2,2 een 2? => return 2
Staat er op 0,0,0 een 1? Staat er op 1,1,1 een 1 ? Staat er op 2,2,2 een 2? => return 0

Het meest elegant is een recursieve oplossing. Veel succes ermee.

[Verwijderd]

Zoals beloofd, hier een voorbeeld. Hij is echter niet grafisch (text based, en je zult de vorige zetten moeten onthouden).

Afgezien van de lange declaratie van de victory conditions is dit denk ik een van de korste codes die je kan krijgen...
in ieder geval korten dan de versie van degene die hier recent z'n boter, kaas en eieren code gepost had voor een schoolopdracht.

Geen 100% garantie dat het ook daadwerkelijk werkt (wel net even een potje tegen mezelf gespeelt, en de uitslag klopte wel).

code:

#include <stdio.h>
#include <stdlib.h>

typedef unsigned long int  Table;

#define N_VICTORY_CONDITIONS 49
const Table victory_conditions[N_VICTORY_CONDITIONS] = { 262657,7,73,1049601,36865,273,525314,73730,1050628,147460,2101256,56,584,8396808,4202512,8405024,16810048,448,4672,67174464,84,33620096,67240192,3584,37376,139776,28672,299008,229376,2392064,43008,1835008,19136512,263172,266304,71565312,532608,1065216,14680064,153092096,2105376,117440512,1224736768,16843008,22020096,270592,67117057,16785412,1056832 };

#define N_PLAYERS 2
Table   player[N_PLAYERS];

unsigned char win(const Table player)
{
    register unsigned char i;

    for(i=0; i < N_VICTORY_CONDITIONS; i++)
      if ((player & victory_conditions[i]) == victory_conditions[i])
        return 1;

    return 0;
}

unsigned char in_use(unsigned char pos)
{
    register unsigned char i;

    for (i=0; i < N_PLAYERS; i++)
      if (player[i] & (1u<<pos))
        return 1;
    
    return 0;
}


int main(void)
{
    unsigned char    p_index;
    unsigned char    end_game;
    unsigned char    pos_buf[3];
    char            pos_str[3] = {'x','y','z'};
    char            read_index;
    unsigned char    pos;

    for(;;)
    {
      end_game=0;
      for(p_index=0; p_index < N_PLAYERS; p_index++)
        player[p_index] = 0;

      do
      {
        for(p_index=0; p_index < N_PLAYERS; p_index++)
        {
            for(;;)
            {
              printf("\nPlayer %u move:\n", p_index+1);

              for(read_index=0; read_index < sizeof(pos_str); read_index++)
              {
                do
                {
                    fflush(stdin);
                    printf("  %c: ", pos_str[read_index]);
                }
                while(fscanf(stdin, "%c", pos_buf+read_index) != 1 || pos_buf[read_index] <= '0' || pos_buf[read_index] > '3');
              }

              pos = (pos_buf[0]-'0'-1) + 3*(pos_buf[1]-'0'-1) + 9*(pos_buf[2]-'0'-1);
              if (in_use(pos))
                printf("Positie in gebruik: overnieuw");
              else
                break;
            }

            player[p_index] |= 1<<(pos);

            if (win(player[p_index]))
            {
              printf("\nPlayer %u heeft gewonnen!\n\n", p_index+1);
              puts("druk op een toets voor een nieuw spel of ctrl+c om af te sluiten");
              fflush(stdin);
              getchar();
              end_game = 1;
              break;
            }
        }
      }
      while(!end_game);
    }

    return 0;
}

en dan hier de source-code van het progje dat ik geschreven heb om de victory condities te genereren. Dit progje is overigens heel wat langer (ik reken het niet mee tot de lengte van de source-code van hierboven ).
Deze kan trouwens flink geoptimaliseert worden... bijv: alles toevoegen aan de victory condities array, en op het laatst een quicksort en vervolgens alle niet gebruikte elementen eruit smijten.

code:

#include <stdio.h>
#include <stdlib.h>

typedef unsigned long int  Table;

#define MAX_VICTORY_CONDITIONS  128

Table   victory_conditions[MAX_VICTORY_CONDITIONS];



void add_toTable(Table *tbl, unsigned char *size, const Table cond)
{
    if (*size == MAX_VICTORY_CONDITIONS)
    {
      puts("MAX_VICTORY_CONDITIONS too low!");
      exit(-1);
    }

    tbl[*size] = cond;
    (*size)++;
}

unsigned char is_inTable(const Table *tbl, const unsigned char size, const Table cond)
{
    register unsigned char  i    = 0;
    const Table      *ptr = tbl;

    while(i < size)
    {
      if (*ptr == cond)
        return 1;

      ptr++;
      i++;
    }

    return 0;
}


unsigned char count_onebits(const Table cond)
{
    register unsigned char   i;
    register unsigned char   c=0;

    for (i=0; i < (unsigned char)(sizeof(Table)<<3); i++)
      if (cond & ((Table) 1u<<i))
        c++;

    return c;
}


int main(void)
{
    Table        condition;
    unsigned char   i;
    unsigned char   size=0;

    for (i=0; i < 27u; i++)
    {
      /* 1: up/down */
      condition  = 1u<<i;
      condition |= 1u<<((i+9)%27);
      condition |= 1u<<((i+18)%27);

      if (!is_inTable(victory_conditions, size, condition))
        add_toTable(victory_conditions, &size, condition);

      /* 2: left/right */
      condition  = 1u<<(3*(i/3));
      condition |= 1u<<(3*(i/3)+((3*(i/3))+1)%3);
      condition |= 1u<<((3*(i/3))+((3*(i/3))+2)%3);

      if (!is_inTable(victory_conditions, size, condition))
        add_toTable(victory_conditions, &size, condition);

      /* 3: forward/backward */
      condition  = 1u<<(i-(i-(9*(i/9)))%3);
      condition += 1u<<((i-((i-(9*(i/9)))%3))+3);
      condition += 1u<<((i-((i-(9*(i/9)))%3))+6);

      if (!is_inTable(victory_conditions, size, condition))
        add_toTable(victory_conditions, &size, condition);

      /* 4: downleft/upright */
      if (i<9 && !(i%3))
      {
        condition  = 1u<<i;
        condition |= 1u<<(i+10);
        condition |= 1u<<(i+20);

        if (/*count_onebits(condition) == 3 &&*/ !is_inTable(victory_conditions, size, condition))
            add_toTable(victory_conditions, &size, condition);
      }

      /* 5: upleft/downright */
      if (i>=18 && !(i%3))
      {
        condition  = 1u<<i;
        condition |= 1u<<((i+19)%27);
        condition |= 1u<<((i+11)%27);

        if (/*count_onebits(condition) == 3 &&*/ !is_inTable(victory_conditions, size, condition))
            add_toTable(victory_conditions, &size, condition);
      }

      /* 6: forwardtop/backwarddown */
      if (i>=18&&i<21)
      {
        condition  = 1u<<i;
        condition |= 1u<<((i+21)%27);
        condition |= 1u<<((i+15)%27);

        if (/*count_onebits(condition) == 3 &&*/ !is_inTable(victory_conditions, size, condition))
            add_toTable(victory_conditions, &size, condition);
      }

      /* 7: forwarddown/backwardtop */
      if (i<3)
      {
        condition  = 1u<<i;
        condition |= 1u<<(i+12);
        condition |= 1u<<(i+15);

        if (/*count_onebits(condition) == 3 &&*/ !is_inTable(victory_conditions, size, condition))
            add_toTable(victory_conditions, &size, condition);
      }

      /* 8: leftforward/rightbackward */
      if (!(i%9))
      {
        condition  = 1u<<i;
        condition |= 1u<<(i+4);
        condition |= 1u<<(i+8);

        if (/*count_onebits(condition) == 3 &&*/ !is_inTable(victory_conditions, size, condition))
            add_toTable(victory_conditions, &size, condition);
      }

      /* 9: leftbackward/rightforward */
      if ((i%9) == 6u)
      {
        condition  = 1u<<i;
        condition |= 1u<<(i-2);
        condition |= 1u<<(i-4);

        if (/*count_onebits(condition) == 3 &&*/ !is_inTable(victory_conditions, size, condition))
            add_toTable(victory_conditions, &size, condition);
      }
    }

    /* basic conditions */
    condition = 1u<<(18) | 1u<<(13) | 1u<<(8);
    add_toTable(victory_conditions, &size, condition);

    condition = 1u<<(26) | 1u<<(13) | 1u<<(0);
    add_toTable(victory_conditions, &size, condition);

    condition = 1u<<(2) | 1u<<(13)  | 1u<<(24);
    add_toTable(victory_conditions, &size, condition);

    condition = 1u<<(6) | 1u<<(13)  | 1u<<(20);
    add_toTable(victory_conditions, &size, condition);

    
    printf("#define N_VICTORY_CONDITIONS %u\r\n", size);
    printf("const Table victory_conditions[N_VICTORY_CONDITIONS] = { ");

    if (!size)
    {
      puts("FAILED!");
      exit(-1);
    }

    for(i=0; i < size; i++)
    {
      if (i==(size-1))
        printf("%u", victory_conditions[i]);
      else
        printf("%u,", victory_conditions[i]);
    }

    printf(" };\r\n");


    return 0;
}

Tot slot: het zijn dus geen 100 combinates... maar 49

[Sponz]

Op zondag 30 september 2001 02:06 schreef lnfinitive een lap source

Ik denk dat je je doel voorbij schiet. Lees de vraag van de topic starter nog maar eens.

Het gaat om de logica van het spel, niet om bitmanipulatie

Een in-game berekening is mooier (en flexibeler), dus niet win situaties van te voren berekenen.

[Verwijderd]

Volgens mij is Infinite inderdaad met een zware overkill bezig, die ook zeker niet bijdraagt aan de helderheid/onderhoudbaarheid van de code..

Topicstarter:

Vraagje; is diagonaal over 3 dimensies legaal in jouw 3d boter-kaas-en-eieren ?

Verder zou het zeker helpen als je vermeldde in wat voor datastructuur je de huidige status van het speelveld bijhield.

[Verwijderd]

Toch bedankt Infinte voor je code. Ik snap der alleen nog niet veel van maar zal het is rustig gaan lezen.

En ja, een 3d diagonaal is mogelijk. Dus bij een 3d kubus krijg je der nog 4 mogelijkheden bij.

En hoe ik nu de stand van het veld bij houd?

Ik heb wat in 2d zitten experimenten. Ik had een struct gemaakt voor alle 9 hokjes. Die kregen een index en een filled optie. Filled==true dan staat er iets. Maar wat is dat iets dan. Het was dus niet echt een goeie manier maar ik zal de code die infinite postte nog ff rustig doorlezen en als ik iets niet snap dan horen jullie het :-)

[AFR]

Als je efficiente code wilt genereren moet je elke mogelijkheid om 3-op-een-rij te krijgen slechts een keer testen. Het kan handog door te kijken welke vectoren voor winnen kunnen zorgen.

Het algorithme is nogal lastig uit te leggen in een paar regels, maar komt op het volgende neer:

- Kijk eerst naar alle vectoren loodrecht op een zijvlak.
- Kijk vervolgens naar alle vectoren die een hoek van 45' maken met een zijvlak.
- Kijk vervolgens naar vecotren die met alle vlakken een hoek van 45' maken.

Elke mogelijkheid wordt selchts één maal getest. Ook werkt het algorithme voor een veld met willekeurige afmetingen.

PS. Als je er niet uit komt en ik voldoende tijd over heb kan ik evt proberen om een stukje code in C++ of M te posten.

[wasigh]

recursie is wederom de makkelijkste manier (damn i love that word

uit de search: [topic=146446/1/25]

[Tsjipmanz]

Tip: maak gebruik van de symmetrie in de "winposities", dat kan nogal wat code schelen!