Крестики Нолики (Алгоритм проверки перекрестий)

[BratSinot]

Доброе утро/день/вечер/ночь.
Вопрос по алгоритму проверки перекрестий. Например:

Код: Выделить всё

X|2|3
-------
4|X|6
-------
7|8|X

Как проверить что оно пересеклось? Выписать все варианты, не вариант ибо это громоздко, и нельзя будет использовать, например, при увеличении поля.
Пробовал вещи типа:

Код:

n=n+1=n+2 n=n+4=n+8 n=n+6=n+3 n=n-1=n+1 n=n-1=n-2 n=n+2=n+4 n=n-3=n+3 n=n-2=n+2 n=n-4=n+4 n=n-1=n+2 n=n-3=n-6 n=n-2=n-4 n=n-4=n-8

Это то-же не вариант потому-что например

Код: Выделить всё

X|2|X
-------
4|X|6
-------
7|8|9
-------

И

Код: Выделить всё

1|2|X
-------
4|X|6
-------
X|8|9
-------

будет считаться одним и тем-же.(n=n-4=n-8)
Помогите кто чем может.

P.S. Мне желательно алгоритм, а не код на языке программирования.

[deadhead]

алгоритм крестики нолики?

[BratSinot]

алгоритм крестики нолики?

Единственное что я нашел более менее это:
http://www.beluch.narod.ru/algkres.htm
А мне нужен алгоритм. И там двумерный массив, а у меня одномерный. И вообще, там непонятно что.

[t.t]

А мне нужен алгоритм. И там двумерный массив, а у меня одномерный. И вообще, там непонятно что.

А зачем одномерный? Задача-то двумерная. Но если очень хочется одномерный, есть простые и очевидные формулы пересчёта из него в двумерный и обратно:
a=x+n*y
y=a/n, x=a%n
Здесь x, y -- координаты в двумерном массиве, a -- в одномерном, n -- размер стороны квадрата; / -- целочисленное деление, % -- остаток от деления.

[BratSinot]

А зачем одномерный? Задача-то двумерная.

А зачем двумерный? Одномерного хватает. От 1-9. 9 клеток, все как полагается.

Но если очень хочется одномерный, есть простые и очевидные формулы пересчёта из него в двумерный и обратно:
a=x+n*y
y=a/n, x=a%n
Здесь x, y -- координаты в двумерном массиве, a -- в одномерном, n -- размер стороны квадрата; / -- целочисленное деление, % -- остаток от деления.

Ну, вопрос остается открытым. Все алгоритмы которые я видел рассчитаны на 3x3, а мне нужен универсальный, который будет работать 3x3, 5x5, 5x10 и т.д.

Сейчас на SourceForge исходники перерываю.
Блин! Нифига нету. Там процентов 60 это просто переборка вариантов, а остальное заточенное под 3x3.

[/dev/random]

А зачем двумерный? Одномерного хватает. От 1-9. 9 клеток, все как полагается.

Затем, что если бы был двумерный, вы бы моментально поняли, как это реализовать. В принципе, те же методы легко адаптируются и для одномерного, но при работе с одномерным менее вероятно, что они придут в голову. Т.к. поле всё-таки двумерное.

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

[BratSinot]

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

Я в самом первом сообщении описал это и написал почему не подойдет.

[/dev/random]

Я в самом первом сообщении описал это и написал почему не подойдет.

А я написал, почему вы заблуждаетесь. И как из этого тупика выйти.

[BratSinot]

Я в самом первом сообщении описал это и написал почему не подойдет.

А я написал, почему вы заблуждаетесь. И как из этого тупика выйти.

Еще раз: Почти у всех и у вас в том числе рассчитано на 3x3. Этот способ не подойдет при 5x5, 10x9, 1x10 и т.д., а мне нужен независимый алгоритм для одномерного массива.

[/dev/random]

Этот способ не подойдет при 5x5, 10x9, 1x10 и т.д.

Подойдёт.

[BratSinot]

Этот способ не подойдет при 5x5, 10x9, 1x10 и т.д.

Подойдёт.

Десятимерный массив чтоль делать?

[/dev/random]

Десятимерный массив чтоль делать?

Зачем?! Вы вообще, поняли, что я вам писал? У вас что, десятимерное поле?

[t.t]

Этот способ не подойдет при 5x5, 10x9, 1x10 и т.д.

Подойдёт.

Десятимерный массив чтоль делать?

С какой стати? Поле всегда двумерно. Ну, бывают и трёхмерные крестики-нолики (поле -- куб, а не квадрат), но этот вариант Вы, я так понимаю, не рассматриваете. Вы явно спутали размерность с размером.

[BratSinot]

Вообщем, низкий вам поклон. Сделал вещь типа:

Код: Выделить всё

if(sk[i]=='X'&&sk[i+1]=='X'&&sk[i+2]=='X') exit(1);
if(sk[i]=='X'&&sk[i+3]=='X'&&sk[i+6]=='X') exit(1);
if(sk[i]=='X'&&sk[i+4]=='X'&&sk[i+8]=='X') exit(1);

Просто, кода мало, а работает

[NickLion]

Алгоритм: ставим в соответствие каждой ячейке 4 числа - длина линии по горизонтали, вертикали, диагонали 1 и диагонали 2. Если Х - число положительное, если О - отрицательное, если ячейка пуста - 0. обрабатываем сверху вниз, слева направо (у Вас линейный массиво - просто по порядку). Для каждой ячейки число рассчитывается так (пусть ширина - w, высота - h, длина ряда - r):

• Если ячейка i пуста, то все 4 числа = 0.
• Если Х, то:
  
  • Если первое число ячейки i-1 > 0, то значение первого числа для данной равно (первое число ячейки i-1) + 1, иначе = 1
  • Если второе число ячейки i-w > 0, то значение второго числа для данной равно (второе число ячейки i-w) + 1, иначе = 1
  • Если третье число ячейки i-w-1 > 0, то значение третьего числа для данной равно (третье число ячейки i-w-1) + 1, иначе = 1
  • Если четвёртое число ячейки i-w+1 > 0, то значение четвёртого числа для данной равно (четвёртое число ячейки i-w+1) + 1, иначе = 1
• Если О - то же самое, только "< 0" и "- 1"

Проверки на выходы за пределы не забудьте.

Выигрыш/проигрыш, если в какой-то ячейке, любое из чисел стало равно r или -r.

подходит такое?

[drBatty]

на поле 3х3 всего 3 варианта линий, остальное - результат поворотов и отражения. на поле 5х5 - 4 линии.
не сложно задать 3 или 4 варианта, а остальное проверять на повороты и отражения.

Там процентов 60 это просто переборка вариантов

дык что перебирать из 3х вариантов? в данном случае это самое простое и возможно - самое быстрое решение...

[eddy]

Интересно, а в игре с большим полем, где нужно больше пяти крестиков/ноликов в ряд поставить, тоже методом перебора пользуются? Хотя, это, конечно, достаточно быстро, но все-таки, как-то не по-математически

[t.t]

Интересно, а в игре с большим полем, где нужно больше пяти крестиков/ноликов в ряд поставить, тоже методом перебора пользуются? Хотя, это, конечно, достаточно быстро, но все-таки, как-то не по-математически

Больше пяти нигде не нужно. На большом поле как раз пять в ряд требуется. А что касается метода, то перебрать-то нужно всего восемь направлений от новой фишки; какой же это "метод перебора"?

[drBatty]

Интересно, а в игре с большим полем, где нужно больше пяти крестиков/ноликов в ряд поставить, тоже методом перебора пользуются? Хотя, это, конечно, достаточно быстро, но все-таки, как-то не по-математически

потому как это не математика, а комбинаторика. в такой тривиальной задачи просто нет смысла использовать более сложные построения. А для больших досок задача не определена (в первом посте нет определения "перекрестий", я понял только для варианта 3х3 и 5х5).

ЗЫЖ что касается самих крестиков-ноликов, то их проще всего решить совсем не математическим способом - с помощью ГА - ведь состояний всего 3^9 (точнее - заведомо меньше 3^9), и можно построить простейшую программу, которая оценивает вероятность выигрыша для каждой из 3^9 позиций. Ну и выбирает случайный ход, причём более вероятны ходы, которые ведут к победе. Натравив две таких программы друг на друга, мы получим через час вполне рабочее решение. а уж 160Кб памяти я думаю найти не сложно...

[BratSinot]

Народ успокойтесь. Я уже решил свою проблему:

Код: Выделить всё

for(i=0; i!=8; i++)
{
 if(sk[i]=='X'&&sk[i+1]=='X'&&sk[i+2]=='X') exit(1);
 if(sk[i]=='X'&&sk[i+3]=='X'&&sk[i+6]=='X') exit(1);
 if(sk[i]=='X'&&sk[i+4]=='X'&&sk[i+8]=='X') exit(1);
}

[/dev/random]

Народ успокойтесь. Я уже решил свою проблему:

Код: Выделить всё

for(i=0; i!=8; i++)
{
 if(sk[i]=='X'&&sk[i+1]=='X'&&sk[i+2]=='X') exit(1);
 if(sk[i]=='X'&&sk[i+3]=='X'&&sk[i+6]=='X') exit(1);
 if(sk[i]=='X'&&sk[i+4]=='X'&&sk[i+8]=='X') exit(1);
}

Это некорректный вариант, вы здесь не проверяете уход за поле. Он будет приводить к неожиданным проблемам.

[t.t]

Интересно, а в игре с большим полем, где нужно больше пяти крестиков/ноликов в ряд поставить, тоже методом перебора пользуются? Хотя, это, конечно, достаточно быстро, но все-таки, как-то не по-математически

потому как это не математика, а комбинаторика.

С каких это пор комбинаторика -- не математика?

ЗЫЖ что касается самих крестиков-ноликов, то их проще всего решить совсем не математическим способом - с помощью ГА - ведь состояний всего 3^9 (точнее - заведомо меньше 3^9), и можно построить простейшую программу, которая оценивает вероятность выигрыша для каждой из 3^9 позиций. Ну и выбирает случайный ход, причём более вероятны ходы, которые ведут к победе. Натравив две таких программы друг на друга, мы получим через час вполне рабочее решение. а уж 160Кб памяти я думаю найти не сложно...

А вот тут Вы явно усложняете. Для 3x3 есть как беспроигрышная стратегия для второго игрока, так и выигрышная для первого (если второй первым ходом допустил ошибку). Причём обе они весьма просты. Так что размышления о натравлении двух программ друг на друга зедсь совершенно излишни.

[eddy]

Для 3x3 есть как беспроигрышная стратегия для второго игрока, так и выигрышная для первого (если второй первым ходом допустил ошибку). Причём обе они весьма просты.

Вот именно, что 3х3 неинтересно. А вот если взять поле, скажем, 10⁶x10⁶, да рассматривать выигрышными только линии, длиннее, скажем, 10⁴ крестиков или ноликов, то задача будет намного интереснее. И простым тупым перебором компьютер будет думать ооочень долго (не при определении, выиграл ли противник, а при выборе, куда поставить свой значок).
Вот мне и интересно: неужели еще нет математического метода решения подобных задач?

[sash-kan]

неужели еще нет математического метода решения подобных задач?

судя по наличию компьютерной игры four-in-a-row, таки есть.

[BratSinot]

Народ успокойтесь. Я уже решил свою проблему:

Код: Выделить всё

for(i=0; i!=8; i++)
{
 if(sk[i]=='X'&&sk[i+1]=='X'&&sk[i+2]=='X') exit(1);
 if(sk[i]=='X'&&sk[i+3]=='X'&&sk[i+6]=='X') exit(1);
 if(sk[i]=='X'&&sk[i+4]=='X'&&sk[i+8]=='X') exit(1);
}

Это некорректный вариант, вы здесь не проверяете уход за поле. Он будет приводить к неожиданным проблемам.

Это черновой вариант. Просто добавить:

Код: Выделить всё

for(i=0; i!=8; i++)
{
 if(i<=6)
  if(sk[i]=='X'&&sk[i+1]=='X'&&sk[i+2]=='X') exit(1);
 if(i<=2)
  if(sk[i]=='X'&&sk[i+3]=='X'&&sk[i+6]=='X') exit(1);
 if(i==0)
  if(sk[i]=='X'&&sk[i+4]=='X'&&sk[i+8]=='X') exit(1);
}

У меня там основной алгоритм. А уже проверка при выход за поле, уже считается в зависимости от размеров. И потом зачем проверка? Если выйдет из диапазона он будет ложно выдавать, а так и надо.

[/dev/random]

У меня там основной алгоритм. А уже проверка при выход за поле, уже считается в зависимости от размеров. И потом зачем проверка? Если выйдет из диапазона он будет ложно выдавать, а так и надо.

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

И повторю ещё раз: используйте двумерный массив, тогда эти проверки станут для вас очевидными.

[BratSinot]

/dev/random
И как это здесь сделать:

if(sk[i]=='X'&&sk[i+2]=='X'&&sk[i+4]=='X') exit(1);

?

[/dev/random]

/dev/random
И как это здесь сделать:

if(sk[i]=='X'&&sk[i+2]=='X'&&sk[i+4]=='X') exit(1);

?

Использовать ДВЕ координаты (x и y), а не одну (i)

[BratSinot]

Использовать ДВЕ координаты (x и y), а не одну (i)

А БЕЗ этого?

[/dev/random]

А БЕЗ этого?

Вручную проверять все "хорошие" и "нехорошие" положения. К примеру, в первом случае будет не "i<=6", а "i == 0 || i == 3 || i == 6".
Да, это превратится в головную боль при использовании большого поля. Но ничего не поделаешь, вы сами выбрали работу с одномерным массивом.