5-мерные крестики-нолики

  • Автор темы Kernel
  • Дата начала
Статус
Закрыто для дальнейших ответов.
K

Kernel

#1
Есть мысль провести чемпионат среди программ по 5-мерным крестикам-ноликам ... 5 это как раз самое то число где уже трудно получать точные алгоритмы игры, но размышление над ходом ещё можно уложить ~ в минуту, так что имхо соревноватся будет достаточно интересно
 

admin

Well-known member
08.08.2003
2 754
0
#2
Kernel
Поясни что это такое :) А то трудно укладывается в голове :)
 
A

ArtuR

#3
а как это 5-ти мерные ?
знаю только трехмерную графику.... :)
 
K

Kernel

#4
Короче, идет последовательность ходов задаваемая целочисленными векторами в 5-мерном пространстве - о графике речи и не идёт. И не пытайтесь представить - всё-равно наврядли получится. Если проекцию 4-хмерных обьектов на 3-хмерное пространство ещё представить можно, то пятимерных уже весьма затруднительно. Но это и не нужно. Вся работа идет чисто с цифрами. Ну типа:
x(0,0,0,0,0)
o(1,0,1,1,1)
x(1,1,1,1,1)
o(0,1,0,1,1)
Задача как и в обычных крестиках ноликах, отличается только длинной линии и размерностью пространства ... в данном случае это скорее всего будет 6 (хотя возможно придется усложнить до 7)
Специально для любителей формализма -- линия это последовательность из N крестиков(ноликов) x[k[0]]..x[k[n-1]] для которых выполняются следующие условия:
1. abs(x[k][j]-x[k[i+1]][j])<=1; i=0..n-2; j=0..4
2. x[k][j]-x[k[i+1]][j]=x[k[i+1]][j]-x[k[i+2]][j]; i=0..n-3; j=0..4
Вот в принципе и вся игра. Если не очень понятно попробуйте представить как бы это выглядело для всем известного 2-хмерного случая :)
 

admin

Well-known member
08.08.2003
2 754
0
#5
Kernel
Ладно. С алгоритмическим мышлением у меня труба :) Как ты хоть такой чемп провести хочешь? Что в качестве приза выставим?
 
V

Vagor.ini

#6
Kernel
Супер, мое сегодняшное затуманенное сознание театральными сферами:) отдыхает, завтра попробую снова прочитать...
 
G

Guest

#7
Слишком простая выигрышная стратегия для первого игрока.
Даже для трёхмерных - выигрывает первый игрок.

х1 222
о2 1** кроме 11* (всегда можем повернуть систему координат :) )
х2 111 (угроза 333)
о2 333
х2 112 (угроза 332 и 113, вилка)

--------

Кроме того, состояние игры в пятимерные крестики-нолики описывается (3^5)-мерным вектором с элементами {_,x,o}, то есть мощность множества состояний не превосходит 3^6.
Это очень мало, следовательно, можно построить полное дерево игры, найти в нём выигрышные стратегии и запрограммировать конечный автомат ТекущееСостояние -> Ход.
 
K

Kernel

#8
Кодт @ www.rsdn.ru
Для тех кто не очень хорошо умеет читать повторяю

Задача как и в обычных крестиках ноликах, отличается только длинной линии и размерностью пространства ... в данном случае это скорее всего будет 6
Если не понятно что в случае 5-и мерных крестиков ноликов 6 относится к длинне линии ... т я уж деже не знаю как обьяснить.
 
G

Guest

#9
<!--QuoteBegin-Kernel+26:02:2004, 09:55 -->
<span class="vbquote">(Kernel @ 26:02:2004, 09:55 )</span><!--QuoteEBegin-->Кодт @ www.rsdn.ru
Для тех кто не очень хорошо умеет читать повторяю

Задача как и в обычных крестиках ноликах, отличается только длинной линии и размерностью пространства ... в данном случае это скорее всего будет 6
Если не понятно что в случае 5-и мерных крестиков ноликов 6 относится к длинне линии ... т я уж деже не знаю как обьяснить. [/quote]
Ааа. Понимаю.

Просто - есть двумерные крестики-нолики - на поле 3*3, и 3-мерные 3*3*3 (держал в руках доску для игры в них :) )

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

С целью уравнять шансы, придумана игра рендзю. В ней первый игрок ограничивается (не имеет права делать некоторые вилки, строить более 5 в ряд).

Крестики-нолики, гомоку и рендзю - это разные игры. Поэтому я и не понял сразу.

Так вот, вне зависимости от размерности пространства и длины линии, в гомоку всегда лучшие шансы именно у первого игрока.

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

Если первый игрок выстроил 5 в ряд (а, обладая выигрышной стратегией в двумерном гомоку, он это сделает), то вокруг этой пятёрки можно попробовать поставить вилки.
Вполне возможно (нужно исследовать), что даже в трёхмерном пространстве будет достаточно возможностей выстроить 6 в ряд.
 
K

Kernel

#10
Поэтому и сказал что возможно придется длинну линии сделать семь. Шесть взято только потому что когда мы в своё время в универе на парах пытались играть - поняли что "вруную" 6 - вполне достаточно. За пару сыграть если кто-то не лажанул не успеваеш, а на вторую мы к этому времени уже редко ходили :). Хотя и для компов тоже можешь попробовать оценить выч. время ... не так уж и мало получется если не пытаться свести это к плоскости ...
 
Статус
Закрыто для дальнейших ответов.