Was zum Knobel.

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