Minimax: ocena pozycji

Kółko i krzyżyk w konsoli krok po kroku - Podstawy C++ (C++)

Reguły da się ograć. Minimax sprawdza wszystkie dalsze partie: funkcja rekurencyjna stawia znak gracza, który ma ruch, na każdym wolnym polu, woła siebie dla przeciwnika i cofa ruch. Koniec partii ocenia: 1 wygrana komputera (O), -1 przegrana, 0 remis. Komputer wybiera największą ocenę, gracz najmniejszą. Gdy znaleziona ocena jest najlepsza możliwa, dalszych pól nie trzeba sprawdzać (break). Program ocenia trzy pozycje, w których ruch ma O.

#include <iostream>
using namespace std;

// plansza: 9 pol, numer pola = wiersz * 3 + kolumna, '.' = puste
char board[9] = {'.', '.', '.', '.', '.', '.', '.', '.', '.'};

// ruch na pole index; false, gdy pole jest zajete
bool play(int index, char player) {
  if (board[index] != '.') {
    cout << "Pole " << index << " zajete" << endl;
    return false;
  }
  board[index] = player;
  return true;
}

// osiem linii: trzy wiersze, trzy kolumny, dwie przekatne
int lines[8][3] = {{0, 1, 2}, {3, 4, 5}, {6, 7, 8}, {0, 3, 6},
                   {1, 4, 7}, {2, 5, 8}, {0, 4, 8}, {2, 4, 6}};

// numer linii z trzema takimi samymi znakami albo -1
int winningLine() {
  for (int i = 0; i < 8; i++) {
    char a = board[lines[i][0]];
    if (a != '.' && a == board[lines[i][1]] && a == board[lines[i][2]]) {
      return i;
    }
  }
  return -1;
}

bool isFull() {
  for (int i = 0; i < 9; i++) {
    if (board[i] == '.') {
      return false;
    }
  }
  return true;
}

// pole zwycieskiej linii w nawiasach: [X]
void printBoard() {
  int line = winningLine();
  for (int row = 0; row < 3; row++) {
    for (int col = 0; col < 3; col++) {
      int cell = row * 3 + col;
      bool win = line != -1 && (lines[line][0] == cell || lines[line][1] == cell || lines[line][2] == cell);
      cout << (win ? "[" : " ") << board[cell] << (win ? "]" : " ");
      if (col < 2) {
        cout << "|";
      }
    }
    cout << endl;
    if (row < 2) {
      cout << "---+---+---" << endl;
    }
  }
}

void clearBoard() {
  for (int i = 0; i < 9; i++) {
    board[i] = '.';
  }
}

void printResult(char result) {
  if (result == 'R') {
    cout << "Remis" << endl;
  } else {
    cout << "Wygrywa " << result << endl;
  }
}

// gracz X gra pierwsze wolne pole ze swojej listy
int firstFree(int prefs[]) {
  for (int i = 0; i < 9; i++) {
    if (board[prefs[i]] == '.') {
      return prefs[i];
    }
  }
  return -1;
}

// pole, ktore konczy linie gracza who (dwa jego znaki i jedno puste), albo -1
int finishing(char who) {
  for (int i = 0; i < 8; i++) {
    int marks = 0;
    int empty = -1;
    for (int j = 0; j < 3; j++) {
      int cell = lines[i][j];
      if (board[cell] == who) {
        marks++;
      } else if (board[cell] == '.') {
        empty = cell;
      }
    }
    if (marks == 2 && empty != -1) {
      return empty;
    }
  }
  return -1;
}

// komputer (O): wygraj, zablokuj, srodek, rog, bok
int ruleMove() {
  int move = finishing('O');
  if (move == -1) {
    move = finishing('X');
  }
  if (move == -1 && board[4] == '.') {
    move = 4;
  }
  int order[8] = {0, 2, 6, 8, 1, 3, 5, 7};
  for (int i = 0; i < 8 && move == -1; i++) {
    if (board[order[i]] == '.') {
      move = order[i];
    }
  }
  return move;
}

// ocena pozycji dla komputera (O): 1 wygrana, -1 przegrana, 0 remis
// turn = kto ma teraz ruch; obaj graja najlepiej, jak sie da
int minimax(char turn) {
  int line = winningLine();
  if (line != -1) {
    return board[lines[line][0]] == 'O' ? 1 : -1;
  }
  if (isFull()) {
    return 0;
  }
  int best = turn == 'O' ? -2 : 2;
  for (int i = 0; i < 9; i++) {
    if (board[i] != '.') {
      continue;
    }
    board[i] = turn;
    int value = minimax(turn == 'O' ? 'X' : 'O');
    board[i] = '.';
    if (turn == 'O' ? value > best : value < best) {
      best = value;
    }
    if (best == (turn == 'O' ? 1 : -1)) {
      break; // lepszego wyniku juz nie bedzie
    }
  }
  return best;
}

int main() {
  char positions[3][10] = {"XX.O.....", "X...O...X", "XO.X.O..."};
  for (int p = 0; p < 3; p++) {
    for (int i = 0; i < 9; i++) {
      board[i] = positions[p][i];
    }
    printBoard();
    cout << "Ocena dla O: " << minimax('O') << endl << endl;
  }
  return 0;
}

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu Podstawy C++·Zaloguj się, aby zapisać postęp na koncie.