Крестики и нолики

[Саша85]

Эта задача скорее чисто образовательного характера, хотя я и пишу игру. Хотелось бы найти самый оптимальный и изящный алгоритм определения победителя, если победитель есть, и его местоположение. Тоесть верхний ряд по горизонтали, второй ряд по горизонтали итд.. Можно сделать это просто полным перебором, ведь у нас всего 8 выигрышных вариантов, так что перебрать не так уж и сложно:

If ((x[1][1] != 0) & (x[1][1] == x[1][2]) & (x[1][1] == x[1][3])){
Первый ряд по горизонтали выиграл.
}

Но хотелось бы более изящный алгоритм. Язык программирования значения не имеет.

[Serge_Bliznykov]

Саша, перебором однозначно.
И победитель определяется и выигрышная линия находится.

Просто задумайтесь, если (вдруг) в следующей вашей программе понадобится определить линию длиной более 3-х и на поле размером более, чем 3X3 (см. игру Gomoku, например Turbo-Gomoku), то что Вы будете делать?!
Переборные алгоритмы хороши тем, что хорошо записываются в виде циклов и, следовательно, легко адаптируются под изменяющиеся условия.



p.s. Конкретно для вашего случая вполне можно и 8 переменных задействовать и 8 выражений логических написать (по аналогии с тем, что Вы привели). Хотя я бы не рекомендовал этот способ, но, тем не менее, его вполне можно использовать на практике.

[Arigato]

Можно минимаксом, но я как-то делал крестики-нолики 3*3 простым алгоритмом, так очень простая беспроигрышная стратегия.

[Serge_Bliznykov]

Сообщение от Arigato

Можно минимаксом

угу. точно так. Arigato, только, если я правильно понял смысл вопроса автора топика, его интересует, как проверить наступление выигрыша (три в ряд) и определить, где этот выигрыш произошёл (кстати, непонятно, зачем)...

[Саша85]

Сообщение от Serge_Bliznykov

Только, если я правильно понял смысл вопроса автора топика

Правильно поняли.

Сообщение от Serge_Bliznykov

(кстати, непонятно, зачем)...

Чтобы потом отобразить на игровом поле. Как обычно перечёркивают выигравший ряд.

Теперь буду разбираться с минимаксом. Кажется, что это нечто слишком уж глобальное. Можете подсказать как это можно применить для крестиков и ноликов?

[Аватар]

Неограниченные крести-нолики пять в ряд интереснее. Да и стратегию покруче нужно закладывать

[Саша85]

Сообщение от Аватар

Неограниченные крести-нолики

Которые никогда не закончатся?
На самом деле это только первый шаг и уже на нём, как оказалось не всё так и тривиально. Но глобальная задумка интереснее.

[Кащей]

Но хотелось бы более изящный алгоритм. Язык программирования значения не имеет.

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

Для реализации етого подкину кода magic_wand.h.
К сожалению я его практически не комментировал, основное токашо описал.

float mb_sim_pack(	uchar* buf,
					int a,
					int n,
					int *s){
	int i;
	float cmp = 0.0;
	for(i = 0; i < *s; i++)
		cmp += (buf[a + i] > buf[n + i]) ? buf[n + i] / (buf[a + i] / 255.0) : buf[a + i] / (buf[n + i] / 255.0);
	return cmp / *s;
}

void mb_magic_sim(	uchar* in,
					uchar* out,
					int *w,
					int *h,
					int x,
					int y,
					int *s){
	
	if(	x - 1 >= 0 &&
		x + 1 < *w &&
		y - 1 >= 0 &&
		y + 1 < *h){
			
		out[(y - 1) * *w + x] = (out[(y - 1) * *w + x] == 0) ?
			((mb_sim_pack(in, (y * *w + x) * *s, ((y - 1) * *w + x) * *s, s) > 253.0) ?(1) : (0)) : 0;
		mb_magic_sim(in, out, w, h, x, y - 1, s);
		
		out[(y + 1) * *w + x] = (out[(y + 1) * *w + x] == 0) ?
			((mb_sim_pack(in, (y * *w + x) * *s, ((y + 1) * *w + x) * *s, s) > 253.0) ? (1) : (0)) : 0;
		mb_magic_sim(in, out, w, h, x, y + 1, s);
		
		out[y * *w + x + 1] = (out[y * *w + x + 1] == 0) ?
			((mb_sim_pack(in, (y * *w + x) * *s, (y * *w + x + 1) * *s, s) > 253.0) ? (1) : (0)) : 0;
		mb_magic_sim(in, out, w, h, x + 1, y, s);
		
		out[y * *w + x - 1] = (out[y * *w + x - 1] == 0) ?
			((mb_sim_pack(in, (y * *w + x) * *s, (y * *w + x - 1) * *s, s) > 253.0) ? (1) : (0)) : 0;
		mb_magic_sim(in, out, w, h, x - 1, y, s);
	}
}

uchar* mb_magic_wand(	uchar* in,//Изображение в любом формате(RGB, RGBA или ещё чего)
						int x,//Коодината точки
						int y,//Координата точки
						int w,//Ширина изображения в пиксеоях
						int h,//Высота изображения в пикселях 
						int s){//Количество байт на пиксель
	uchar* out = malloc(w * h);//Это результат, бинаризированное изображение.
	if(out != NULL){
		memset(out, 0, w * h);
		mb_magic_sim(in, out, &w, &h, x, y, &s);
	}
	return out;
}

[Гром]

Довольно банальный вариант:

enum CellState {Empty, X, O};

bool IsWinningLine(CellState** Field, int X0, int Y0, int dX, int dY, uint len)
 {
 CellState StartSt = Field[X0][Y0];
 if (StartSt == Empty)
  return false;
 for (uint i = 1; i < len; ++i)
  if (Field[X0 + i * dX][Y0 + i * dY] != StartSt)
   return false;
 return true;
 }

enum Dir {Horiz = 0, Vert, DiagToRightBottom, DiagToLeftBottom};

bool CheckLineByDirection(CellState** Field, uint Sz, uint WinLen, int x, int y, Dir dir)
 {
 switch (dir)
  {
  case Horiz:
   {
   if (x <= Sz - WinLen)
    return IsWinningLine(Field, x, y, 1, 0, WinLen);
   return false;
   } break;
  case Vert:
   {
   if (y <= Sz - WinLen)
    return IsWinningLine(Field, x, y, 0, 1, WinLen);
   return false;
   } break;
  case DiagToRightBottom:
   {
   if (x <= Sz - WinLen && y < Sz - WinLen)
    return IsWinningLine(Field, x, y, 1, 1, WinLen);
   return false;
   } break;
  case DiagToLeftBottom:
   {
   if (x >= WinLen && y <= Sz - WinLen)
    return IsWinningLine(Field, x, y, -1, 1, WinLen);
   return false;
   } break;
  default: return false;
  }
 }

void CheckWin(CellState** Field, uint Sz, uint WinLen)
 {
 for (int x = 0; x < Sz; ++x)
  for (int y = 0; y < Sz; ++y)
   {
   for (int i = 0; i < 4; ++i)
    {
    if (CheckLineByDirection(Field, Sz, WinLen, x, y, Dir(i)))
     {
     std::cout << "The winner is " <<  CellToString (Field[x][y]) << ". The winning line begins from [" << x + 1 << "][" << y + 1 << "]. Direction is " << DirToString(Dir(i));
     return;
     }
   }
 }

Комментировать, честно говоря, лень, надеюсь, все понятно из кода. Вкратце суть - первая функция проверяет ряд не задумываясь, она универсальна. Вторая проверяет ряд в нужном направлении, делая проверку диапазона и переводя направление в нужные значения dX, dY. Третья просто пробегает по всему полю и в случае победы формирует текстовое сообщение. Используются две не указанные здесь функции, которые просто выдают строковое соответствие своим параметрам.