Was zum Knobel.

Fischkopf2009

hallo programmiere gerde ein TicTacToe Spiel und möchte nun wissen wie viele EndZustände es gibt. Also wenn man alle Möglichkeiten ermittelt ( ohne Berücksichtung eines Gewinners ) kommt man auf 9!
So nun möchte ich aber wissen wie viele Möglickeiten es gibt wenn man diese Fälle berücksichtigt. Sprich wenn einer gewonnen hat, wird kein weiteres Kreuz gemacht . Kann mir jeamnd helfen ? Danke

SeppJ

Da bietet sich doch ein Brute-Force Ansatz an. Eventuell auch noch unter Ausnutzung der Symmetrie des Problems, damit man sich ein paar Rechnungen spart. Allzuviele Stellungen sollte es nicht geben.

Wie kommst du eigentlich auf 9! als Obergrenze? Das kommt mir irgendwie falsch vor, ich hätte nämlich eher 9 über 5 = 126 gesagt, was wesentlich weniger ist.

Begründung: Der erste Spieler macht 5 Kreuzchen, irgendwo auf dem Spielfeld von 9 Feldern. Die Anzahl der Möglichkeiten 5 Kreuzchen auf 9 Felder zu verteilen ist dann 126.

Fischkopf2009

Moment : es geht darum 3 steine in einer reihe , spalte oder diagonal anzuordnen.
es wird immer abwecheselnd gezogen. und nun ist die frage wie viele endzustände es gibt.
der erste spieler hat 9 möglichkeiten seine ersten stein zu setzten. der zweite hat nun noch 8 usw. das macht 9!

SeppJ

Fischkopf2009 schrieb:

Moment : es geht darum 3 steine in einer reihe , spalte oder diagonal anzuordnen.
es wird immer abwecheselnd gezogen. und nun ist die frage wie viele endzustände es gibt.
der erste spieler hat 9 möglichkeiten seine ersten stein zu setzten. der zweite hat nun noch 8 usw. das macht 9!

Das sind 9! Spielverläufe, aber wesentlich weniger Endzustände. Denn es ist dem Endzustand ja egal, welcher Stein zuerst lag.

Oder als Beispiel:

XXX
XXO
OOO

Es gibt 5! Möglichkeiten wie die X gesetzt werden könnten, damit sie am Ende so liegen wie hier und 4! Möglichkeiten die O zu setzen, also 5!*4! Möglichkeiten diesen einen Endzustand zu erreichen.

Deine Frage beantwortet dies natürlich noch nicht, aber diese Überlegung schränkt vermindert die Anzahl der möglichen Brettstellungen erheblich.

volkard

Gibt es unerreichbare Stellungen? Ja, ein paar.

XXX
OOO
XXO

Von den 126 bröckeln also noch ein paar weg.

Leider gibt es auch vorzeitiges Ende wie bei

XOO
XX.
X.O

Ich nehme mal pro Feld drei Zustände an und 3^9=19683. Der Platz reicht sicher aus.

Oder ich mache es für verschiedene Steinezahlen getrennt.
9 Steine:
Wie schon gezeigt:
9 über 5 = 126

8 Steine mit Sieg von X:
8 Möglichkeiten einer Dreiher-Reihe für X: 8
Und ein X kann frei anders (auf 6 verbleibenden Feldern) liegen: 6
Und die O haben noch 5 freie Plätze: 5 über 4 = 5
8 * 6 * 5 = 240

Und die Zahlen wachsen erstmal und es ist viel zu aufwendig, bzw vom Computer abzählen zu lassen ist viel zu einfach.

SeppJ

Ich fand das ja mal ganz reizend und habe mal die Brute-Force Methode ausprobiert:

#include<set>
#include<vector>
#include<iostream>

using namespace std;

int are_equal_and_non_zero(unsigned x1, unsigned x2, unsigned x3, vector<int> &board)
{
  if ((board[x1] == board[x2]) && (board[x2] == board[x3]) && board[x3]) return board[x3];
  else return 0;
}

bool won(vector<int> &board)
{
  int there_is_a_winner = 0;
  there_is_a_winner |= are_equal_and_non_zero(0,4,8,board); // Diagonalen
  there_is_a_winner |= are_equal_and_non_zero(2,4,6,board);
  for (int i=0; i<3; ++i)
    {
      there_is_a_winner |= are_equal_and_non_zero(3*i+0,3*i+1,3*i+2,board); // Waagerechte
      there_is_a_winner |= are_equal_and_non_zero(i+0,i+3,i+6,board); // Senkrechte
    }
  return there_is_a_winner;
}

void turn(int player, vector<int> &board, set<int> &winning_positions)
{
  static int pow3[9]={1,3,9,27,81,243,729,2187,6561};
  if (won(board))
    {
      int unique_id=0;
      for (unsigned field=0; field<board.size(); ++field) unique_id += pow3[field]*board[field];
      winning_positions.insert(unique_id);
      cout<<"Found winning position. ID: "<<unique_id<<'\n';
      return;
    }
  for (unsigned field=0; field<board.size(); ++field)
    {
      if (!board[field]){
        board[field]=player;
        turn((player%2)+1, board, winning_positions);
        board[field]=0;
      }
    }
}

int main()
{
  set<int> winning_positions;
  vector<int> board(9);
  turn(1,board,winning_positions);
  cout<<"Found "<<winning_positions.size()<<" unique winning positions."<<endl;
}

Wer Fehler findet, bitte melden!

Dieses Programm kommt auf 942 einzigartige Siegstellungen. Und keine Angst, trotz der vielen Ausgaben zwischendurch läuft es nur ein paar Sekunden. Ohne Ausgaben würde das Ergebnis vermutlich fast instant berechnet werden.

P.S.: Jupp, ohne Ausgabe ist das Ergebnis für einen Menschen nicht wahrnehmbar schnell da.

P.P.S: Das ist natürlich nur ein schneller Hack. Ich warte auf eine Lösung mit TMP. Rekursiv ist es ja schon, sollte sich daher eigentlich recht gut anpassen lassen.

volkard

Zu

int unique_id=0; 
      for (unsigned field=0; field<board.size(); ++field) unique_id += pow3[field]*board[field];

denke ich an

int unique_id=0; 
      for (unsigned field=0; field<board.size(); ++field) unique_id = 3*unique_id + board[field];

Und ich denke bei

bool won(vector<int> &board)
{
  int there_is_a_winner = 0;
  there_is_a_winner |= are_equal_and_non_zero(0,4,8,board); // Diagonalen
  there_is_a_winner |= are_equal_and_non_zero(2,4,6,board);
  for (int i=0; i<3; ++i)
    {
      there_is_a_winner |= are_equal_and_non_zero(3*i+0,3*i+1,3*i+2,board); // Waagerechte
      there_is_a_winner |= are_equal_and_non_zero(i+0,i+3,i+6,board); // Senkrechte
    }
  return there_is_a_winner;
}

an

bool won(vector<int> &board)
{
  if(are_equal_and_non_zero(0,1,2,board)) return true;
  if(are_equal_and_non_zero(3,4,5,board)) return true;
  if(are_equal_and_non_zero(6,7,8,board)) return true;
  if(are_equal_and_non_zero(0,3,6,board)) return true;
  if(are_equal_and_non_zero(1,4,7,board)) return true;
  if(are_equal_and_non_zero(2,5,8,board)) return true;
  if(are_equal_and_non_zero(0,4,8,board)) return true;
  if(are_equal_and_non_zero(2,4,6,board)) return true;
  return false;
}

Fischkopf2009

Okay danke aber bei kommen 295000 raus !!!!!!
Hier mein Programm
[url] http://www.c-plusplus.net/forum/viewtopic.php?p=1928236#1928236 [/url]

SeppJ

Fischkopf2009 schrieb:

Okay danke aber bei kommen 295000 raus !!!!!!
Hier mein Programm
[url] http://www.c-plusplus.net/forum/viewtopic.php?p=1928236#1928236 [/url]

Gehst du die Geschichte nicht etwas kompliziert an?

volkard

SeppJ schrieb:

Wer Fehler findet, bitte melden!

Ich fürchte, Du hast nur die Siegstellungen gefunden und die Unentschieden-Ergebnisse als Endzustände vergessen.

SeppJ

volkard schrieb:

SeppJ schrieb:

Wer Fehler findet, bitte melden!

Ich fürchte, Du hast nur die Siegstellungen gefunden und die Unentschieden-Ergebnisse als Endzustände vergessen.

Ausgerechnet die wichtigsten Stellungen beim TicTacToe .

Hmm, wenn ich das mache, komme ich auf 958. Hätte nicht gedacht, dass es so wenige Unentschiedenstellungen gibt. Vielleicht ist noch ein weiterer Fehler drin. So sieht's jetzt aus (mit volkards Verbesserungen. Manchmal denke ich einfach zu kompliziert. Die if Kaskade war nämlich auch mein erster Gedanke zur Gewinnstellung, aber ich habe dann erstmal lange nachgedacht um ein unnötig kompliziertes Muster zu entdecken.):

#include<set>
#include<vector>
#include<iostream>
#include<algorithm>

using namespace std;

int are_equal_and_non_zero(unsigned x1, unsigned x2, unsigned x3, const vector<int> &board)
{
  if ((board[x1] == board[x2]) && (board[x2] == board[x3]) && board[x3]) return board[x3];
  else return 0;
}

bool game_ends(const vector<int> &board)
{
  if(are_equal_and_non_zero(0,1,2,board)) return true;
  if(are_equal_and_non_zero(3,4,5,board)) return true;
  if(are_equal_and_non_zero(6,7,8,board)) return true;
  if(are_equal_and_non_zero(0,3,6,board)) return true;
  if(are_equal_and_non_zero(1,4,7,board)) return true;
  if(are_equal_and_non_zero(2,5,8,board)) return true;
  if(are_equal_and_non_zero(0,4,8,board)) return true;
  if(are_equal_and_non_zero(2,4,6,board)) return true;
  if(count(board.begin(),board.end(),0)==0) return true; // Draw
  return false; 
}

void turn(int player, vector<int> &board, set<int> &end_positions)
{
    if (game_ends(board))
    {
      int unique_id=0;
      for (unsigned field=0; field<board.size(); ++field) unique_id = 3*unique_id + board[field];
      end_positions.insert(unique_id);
      return;
    }
  for (unsigned field=0; field<board.size(); ++field)
    {
      if (!board[field]){
        board[field]=player;
        turn((player%2)+1, board, end_positions);
        board[field]=0;
      }
    }
}

int main()
{
  set<int> end_positions;
  vector<int> board(9);
  turn(1,board,end_positions);
  cout<<"Found "<<winning_positions.size()<<" unique end positions."<<endl;
}

Wikipedia sagt übrigens 138 einzigartige Endstellungen, aber das ist mit Berücksichtigung der Symmetrie, welche hier bewusst außen vor gelassen wird.

volkard

SeppJ schrieb:

Hmm, wenn ich das mache, komme ich auf 958. Hätte nicht gedacht, dass es so wenige Unentschiedenstellungen gibt.

Das ist ja krass.
958-942=16
Uih. Nur 16 verschiedene Unentschieden-Stellungen. Uih.

SeppJ schrieb:

Manchmal denke ich einfach zu kompliziert.

Ja, du bist zu fleißig. Das ist zwar eine Tugend, die Arbeitgeber zu schätzen wissen, aber den endgeilsten Code machen dann doch die arbeitslosen Trolle.

Fischkopf2009

[quote="volkard"]

SeppJ schrieb:

Uih. Nur 16 verschiedene Unentschieden-Stellungen. Uih.

Das kann nicht sein : Es gibt ja nur folgende Möglichkeiten :

Block 1
1 X X O

2 X O X

3 O X X

Block 2
4 O O X

5 O X O

6 X O O

Um nun die möglichkeiten zu ermitteln nimmt man immer 2 Varianten aus Block 1 ( 1, 2 oder 3) und eine Variante aus Block 2 ( 4, 5 oder 6). Dabei ist es ganz wichtig das auch 2 x die gleiche Variante aus Block 1 verwendete werde darf.
Somit können 16 Möglichkeiten nicht sein. Es müssen mehr sein

ipsec

Wikipedia schrieb:

Es gibt 16 Unentschieden-Positionen, die aus folgenden drei durch Spiegelung oder Rotation erhalten werden können:
X|X|O             X|X|O             X|X|O
-+-+-             -+-+-             -+-+-
O|X|X             O|O|X             O|O|X
-+-+-             -+-+-             -+-+-
X|O|O             X|X|O             X|O|X

Der Fehler bei deiner Argumentation: wenn ich z.B. die Varianten 1, 2 und 6 nehme, ist es kein Unentschieden mehr.

SeppJ

Nicht verzagen, wir haben ja schon ein Programm vorliegen, welches uns alle Unentschieden-Stellungen liefert:

XOX XOX XOX XOX
OXX OOX XOO XOX
OXO XXO OXX OXO

XOX XOO XXO XXO
XXO OXX OXX OOX
OXO XXO XOO XOX

XXO OXX OXX OXX
OOX XOO XOO XXO
XXO XOX OXX OOX

OXO OXO OXO OOX
XXO XOX OXX XXO
XOX XOX XOX OXX

Welche sollen denn nun angeblich fehlen?

Fischkopf2009

Ich muss mich bei dir entschuldigen und auch bedanken. Du (und auch Wikiopedia) haben recht. ich hatte einen denkfehler