Connect 4 Game Design на C ++

Я работаю над созданием простой версии Connect 4. игра.

Вот мой первый черновик кода. Я хотел бы получить отзывы по этому поводу, а также требовать изменения для следующих вопросов:

  1. Добавьте немного интеллекта в игроков, чтобы оптимально подобрать колонну.
  2. Как вы сделаете игру универсальной, чтобы в ней можно было проверять 16 точек в строке / столбце / диагонали
  3. Как вы справитесь с огромной сеткой?

Что касается item3, я думаю, что, поскольку я не храню всю сетку, мой подход является масштабируемым. Буду признателен за любые рекомендации или отзывы.

class Connect4 {

vector <pair<int, map< pair<int,int>,int > > > rows;
vector <pair<int, map< pair<int,int>,int > > > cols;
vector <pair<int, map< pair<int,int>,int > > > diag;
int r;
int c;
int player;
public:
  Connect4 (int rr, int cc):r(rr), c(cc){
     rows = vector <pair<int, map< pair<int,int>,int > > >  (rr);
     cols = vector <pair<int, map< pair<int,int>,int > > > (cc);
     diag = vector <pair<int, map< pair<int,int>,int > > > (min (rr,cc));
  }
  
  int move(int row, int col, int player){
      int score = (player ==1)?1:-1;   // count player-1 socres with positive and player-2 with negative numbers 
      
      rows[row].first +=score;
      rows[row].second[{row,col}]=score;
      if (abs(rows[row].first) ==4 && isValid(rows[row].second) )
            return player;
      
      cols[col].first += score;
      cols[col].second[{row,col}]=score;
      if (abs(cols[col].first) ==4 && isValid(cols[col].second) )
            return player;
      
      if(row ==col+2){
        diag[0].first +=score; 
        if (abs(diag[0].first) ==4 ) //if the score is 4 no extra checking is needed
            return player;
           
      } else if (row ==col+1) {
        diag[1].first += score; 
        if (abs(diag[1].first) ==4 && isValid(diag[1].second) )
            return player;
        
      } else if (row ==col) {
         diag[2].first += score;  
         if (abs(diag[2].first) ==4 && isValid(diag[2].second) )
            return player;
         
      } else if (row+1 ==col) {
         diag[3].first += score; 
         if (abs(diag[3].first) ==4 && isValid(diag[3].second) )
            return player;
         
      } else if (row+2 ==col) {
         diag[4].first += score;
         if (abs(diag[4].first) ==4 && isValid(diag[4].second) )
            return player;
         
      } else if (row+3 ==col) {
        diag[5].first += score; 
        if (abs(diag[5].first) ==4 )
            return player;
      }
  }
  
  bool isValid(map<pair<int,int>, int> verify) {
      int cnt=1;
      map<pair<int,int>, int>::iterator itr = verify.begin();
      int prev= itr->second;
      itr++;
      for (;itr!= verify.end(); ++itr){
        int score = itr->second ; 
        if(prev == score){
            cnt++;
            if(cnt ==4)
              return true;
        } else {
           cnt=0;
        } 
        prev = score;
      }
      return (cnt>=4);
  }
};

Здесь обсуждается логика вычисления диагонали: в сетке 6×7 мы можем получить диагональный балл> = 4 только в следующих матричных индексах:

Если у нас одинаковые оценки в следующих (X, Y):

  • (2,0), (3,1), (4,2), (5,3) -> диаг[0]
  • (1,0), (2,1), (3,2), (4,3), (5,4)
  • (0,0), (1,1), (2,2), (3,3), (4,4), (5,5)
  • (0,1), (1,2), (2,3), (3,4), (4,5), (5,6)
  • (0,2), (1,3), (2,4), (3,5), (4,6)
  • (0,3), (1,4), (2,5), (3,6) -> диаг[6]

1 ответ
1

Именование вещей

Избегайте использования односимвольных имен переменных, если только они не используются очень часто, например i для индекса цикла. Учитывать r и c, даже если вы думаете, что это как-то связано с координатами, это положение или размер? Я бы лично использовал width и height вот как однозначные названия размеров сетки.

Обратите внимание, что в списке инициализаторов конструктора для параметра можно использовать то же имя, что и для переменной-члена, например:

int width;
int height;

public:
Connect4(int width, int height): width(width), height(height) {...}

Не всем нравится такой стиль; некоторые люди хотят устранить неоднозначность между параметром и переменной-членом, написав:

Connect4(int width_, int height_): width(width_), height(height_) {...}

И вы также видите проекты, в которых все переменные-члены имеют префикс m_, так это будет выглядеть так:

int m_width;
int m_height;

public:
Connect4(int width, int height): m_width(width), m_height(height) {...}

Другие имена переменных, которые можно улучшить:

  • cnt -> count
  • itr -> it (последнее более идиоматично)
  • diag -> diagonal
  • verify -> line

Создать enum class для возможного содержимого ячейки сетки

An enum, а еще лучше enum class, позволяют заранее указать возможные значения ячейки сетки с именами вместо целых значений. Предлагаю вам написать следующее:

class Connect4 {
    enum class Cell: char {
       EMPTY,
       PLAYER1,
       PLAYER2,
    };
};

Вышеупомянутое также явно устанавливает тип в char, поэтому для его хранения необходим только один байт.

Хранение сетки

Есть несколько ошибок в том, как вы храните сетку. Используемая вами структура данных очень неэффективна как для больших, так и для малых сеток, а также для проверки условий выигрыша. Лучше всего использовать один вектор для хранения всех ячеек сетки:

std::vector<Cell> grid;

Это обеспечивает очень компактную компоновку в памяти, а для поиска произвольной ячейки сетки процессору достаточно выполнить одно умножение и два сложения, что очень дешево для современных процессоров, и, как уже упоминал Тоби Спейт, для проверки горизонтальности , вертикальные и диагональные линии тоже очень просты; просто вычислите начальную точку, конечную точку и шаг для использования, а затем на каждом шаге по линии нужно делать только одно добавление, чтобы найти ячейку сетки для проверки.

Я бы добавил функцию для получения ссылки на ячейку сетки по ее координатам, например:

Cell &at(int row, int col) {
    return grid[row * c + col];
}

Работа с огромными сетками

Первое, что следует учитывать при работе с огромными сетками / массивами / матрицами, — будет ли структура данных заполнена плотно или редко. Легко подумать, что он должен быть разреженным, ведь вы начинаете с полностью пустой сетки. Но учтите, что во время финальной игры Connect 4 вы, вероятно, использовали более половины ячеек сетки, поэтому плотная сетка, вероятно, лучший способ сохранить состояние.

С указанным выше Cell типа, вы используете один байт на ячейку сетки. Поскольку у ячейки есть только три возможных состояния, вы можете относительно легко упаковать до пяти ячеек в байт (поскольку 3⁵ = 243) за счет некоторых дополнительных вычислений при чтении / записи данной ячейки. При этом сетка 100 000 на 50 000 умещается чуть меньше гигабайта.

Вы также можете подумать о том, чтобы как-то сжать сетку, но еще раз подумайте, как выглядит игра connect 4 в конце. Наверняка не будет серий из более чем 3 ячеек одного цвета подряд, иначе уже был бы победитель. И вы редко видите повторяющийся узор. Так что это в основном похоже на шум, который не сжимается. Возможно, для сжатия последовательности ходов, сделанных игроками, можно было бы использовать прогнозирующее кодирование, но сжатые данные, скорее всего, не будут в форме, подходящей для отображения сетки и проверки условий выигрыша.

Единственный вариант, который я вижу для значительного уменьшения объема данных, — это учесть, что большая часть ячеек сетки, в которых игроки уже играли, никогда не будет частью 4 связанных ячеек одного цвета. Например, вы можете пометить все ячейки, которые удалены более чем на 3 позиции (как по горизонтали, так и по вертикали) от любых пустых ячеек, как «мертвые». Таким образом, в принципе, вместо того, чтобы хранить $ mathcal {O} (W cdot H) $, вам нужно только хранить $ mathcal {O} (W + H) $ ячейки сетки. Но это будет означать, что вы больше не можете точно показать все сделанные до сих пор ходы.

Проверка условия выигрыша

К сожалению, ваша идея вести счет за каждую строку не очень полезна. Довольно легко создать линию, в которой общее количество очков будет равно четырем, но нет 4 последовательных ячеек с одним и тем же игроком, например, представляющих игроков 1 и 2 с O и X соответственно:

X O O X O O X O O X O O

Есть 8 фигур игрока 1 и 4 игрока 2, поэтому ваш способ подсчета очков приведет к 4 или же -4, но явно ни один игрок еще не выиграл. Однако, если игрок 1 добавит еще два Oв эту строку:

X O O X O O X O O X O O O O

Тогда у игрока 1 4 подряд, но «счет линии» будет 6 или же -6. Так что линейный счет бесполезен.

Простое решение — просто всегда проверять область 9×9, окружающую последнее движение, на наличие горизонтальной, вертикальной или диагональной линии с 4 в ряд. Это может показаться немного расточительным в самом начале игры, когда было сделано всего несколько ходов, в долгосрочной перспективе это не имеет особого значения.

  • Спасибо за ответ. Просто небольшой комментарий по поводу «Проверка условия выигрыша». Функция isValid () проверяет, набрали ли подряд 4 одинаковые игроки подряд, столбец или диагональ. И я намеренно сначала проверил, равен ли счет 4 или -4, а затем вызвал isValid (). Другими словами, isValid вызывается тогда и только тогда, когда abs (score_value) равен 4

    — Ашкан

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *