Проверка, кто выиграл Tic Tac Toe более эффективный C ++

Question

Я пишу Tic Tac Toe Game, и я хотел бы знать, как я могу сделать эффективную функцию, чтобы проверить, кто победил. Двумерный массив, состоящий из X, O или пробелов, представляет доску.

  char CheckWin(const char board[][NUM_COLS], int& sum) // tic tac toe board - IN
{
    char tmp;
    int lcv;
    tmp = ' ';

    if (sum == 9)
    {
        return 'T';
    }
    else if (sum != 9)
    {
        if (((tmp = board[1][1]) != ' ' && board[0][0] == tmp && board[2][2] == tmp) || (board[2][0] == tmp && board[0][2] == tmp))
        {
            return tmp;
        }

        for (lcv = 0; lcv < 3; lcv++)
        {
            if ((tmp = board[lcv][0]) != ' ' && board[lcv][1] == tmp && board[lcv][2] == tmp)
            {
                return tmp;
            }
            else if ((tmp = board[lcv][0]) != ' ' && board[lcv][1] == tmp && board[lcv][2] == tmp)
            {
                return tmp;
            }
        }
    }

    return 'N';
}

Кроме того, чтобы делать что-то похожее на это снова и снова, как я могу проверить, кто выиграл, и вернуть Х, если Х выиграл, О, если О имеет один, Т, если это ничья, и N, если ни у кого нет еще. Заранее спасибо. Я пытаюсь познакомиться с C ++ и программированием в целом.

РЕДАКТИРОВАТЬ: я просто пошел с простым методом, но я как-то испортил, кто-нибудь знает как? Похоже, он ничего не возвращает, потому что когда я вызываю его в главном после того, как игрок выбирает строку и столбец (это работает нормально), он ничего не выводит

Answer 1

Вы можете преобразовать массив в два девятиразрядных значения, одно для позиций O, другое для позиции X и количество пробелов:

x_mask = 0
y_mask = 0
empty_count = 0
mask = 1
for each square
  if x then x_mask |= mask
  if y then y_mask |= mask
  if empty then empty_count++
  mask <<= 1

Затем сравните x_mask и y_mask с восемью возможными выигрышными комбинациями:

for each player
  for each winning combination
    if player_mask & winning_mask == winning_mask then player has won

, а затем разберитесь с делами, которые ни один из игроков не выиграл:

if neither player won
  if empty_count == 0
    its a tie
  else
    moves still available

Answer 2

Полагаю, вы могли бы присвоить каждой выигрышной доске число (в основном хеш-значение), а затем проверить, соответствует ли текущая доска любому из значений в таблице, сгенерировав ее хеш-значение.С другой стороны, я бы не советовал тратить слишком много времени на то, чтобы сделать функцию CheckWin сверхэффективной.Если это не вызывается миллионы раз или что-то и должно быть очень быстрым, тратьте время на что-то другое - это, вероятно, не будет узким местом.

Answer 3

Простой "структурированный" подход

Если вы думаете о доске как:

A  B  C
D  E  F
G  H  I

Тогда один минимальный выбор блоков, к которому должен прикоснуться любой выигрышный макет:

A B C
D
G

Вы можете представить движение из любого из этих мест в выигрышной линии в терминах смещения на 0, 1 или -1 позиции в каждом из направлений X и Y. Мы можем перечислить движения, которые вам нужно проверить:

A: (++x) (++x, ++y) (++y)
B: (++y)
C: (++y) (--x, ++y)
D: (++x)
E: (++x)

В C ++ вы можете создать список / вектор координат x / y начальных точек и показанных выше дельт движения + / - / 0 x / y, а затем использовать три вложенных цикла для оценки каждой линии на доске. .

Это значительно больше работы, чем просто жесткое кодирование двух циклов по координатам x и y и двум диагоналям (ниже), но это более алгоритмический подход, который может быть интеллектуально привлекательным: больше похоже на то, что вам, возможно, придется делать, если вы обрабатываете намного большая доска.

---

Очевидное приближение грубой силы

Для простоты, этот более простой подход будет выглядеть так:

int x;
for (row = 0; row < 3; ++row)
    if ((x = board[row][0]) != Empty &&
        board[row][1] == x && board[row][2] == x)
        return x;
// similar loop for columns...
...
// hardcode diagonals...
if ((x = board[1][1]) != Empty &&
    (board[0][0] == x && board[2][2] == x ||
     board[2][0] == x && board[0][2] == x))
    return x