Я бы рекомендовал использовать стек вызовов в качестве структуры данных стека или, проще, для создания рекурсивной функции.
Рекурсия естественным образом ведет к исчерпывающему поиску возможных ходов, обрезая любые ветви, которые приводят к вынужденным потерям. Формально это называется минимаксным поиском (чтобы найти следующий ход). https://www.cs.cornell.edu/courses/cs312/2002sp/lectures/rec21.htm
Если вы обнаружите выигрышный ход, вы вернете этот факт, и вызывающий игрок узнает, что позиция доски, которую он рассматривал, позволяет противнику добиться победы. Вы хотите, чтобы ваша функция не позволяла оппоненту заставить выиграть, и играйте ходы, которые могут привести к принудительному выигрышу для себя, если он есть. например Рекурсивный алгоритм Tic Tac Toe .
Я бы рекомендовал представлять состояние платы с помощью структуры данных фиксированного размера . Ваши хорошие варианты
массив из 9 байтов символов, таких как пробел, 'X' и 'O' (дополняется до 12, поэтому вы можете скопировать его с помощью 3x lw). то есть в C struct board { alignas(4) char b[9]; };. Вы делаете копии всей этой структуры.
2х растровых изображения (одно для X и одно для O) для так называемой «битовой доски». (В шахматных движках у 64-битных растровых изображений есть один бит на каждый квадрат на доске. В 3x3 крестики-нолики вам нужно всего 9 бит регистра для полной доски). Тогда вы можете придумать бит-хаки для проверки 3-в-ряд, например b & 0b111 == 0b111 (с andi и beq), чтобы проверить, что верхний ряд является одним маркером.
Вы можете найти свободные места на доске, выполнив X|O и отыскивая биты, которые по-прежнему равны нулю.
одна битовая доска с 2 битами на позицию (всего 18 бит, больше чем MIPS немедленно). Возможно, проще было бы искать 2 подряд с пустой 3-й позицией.