Есть мысль провести чемпионат среди программ по 5-мерным крестикам-ноликам ... 5 это как раз самое то число где уже трудно получать точные алгоритмы игры, но размышление над ходом ещё можно уложить ~ в минуту, так что имхо соревноватся будет достаточно интересно
-
Познакомьтесь с пентестом веб-приложений на практике в нашем новом бесплатном курсе
- Статус
Короче, идет последовательность ходов задаваемая целочисленными векторами в 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-хмерного случая
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-хмерного случая
Kernel
Ладно. С алгоритмическим мышлением у меня труба Как ты хоть такой чемп провести хочешь? Что в качестве приза выставим?
Ладно. С алгоритмическим мышлением у меня труба
Как ты хоть такой чемп провести хочешь? Что в качестве приза выставим?Kernel
Супер, мое сегодняшное затуманенное сознание театральными сферами отдыхает, завтра попробую снова прочитать...
Супер, мое сегодняшное затуманенное сознание театральными сферами
отдыхает, завтра попробую снова прочитать...Слишком простая выигрышная стратегия для первого игрока.
Даже для трёхмерных - выигрывает первый игрок.
х1 222
о2 1** кроме 11* (всегда можем повернуть систему координат )
х2 111 (угроза 333)
о2 333
х2 112 (угроза 332 и 113, вилка)
--------
Кроме того, состояние игры в пятимерные крестики-нолики описывается (3^5)-мерным вектором с элементами {_,x,o}, то есть мощность множества состояний не превосходит 3^6.
Это очень мало, следовательно, можно построить полное дерево игры, найти в нём выигрышные стратегии и запрограммировать конечный автомат ТекущееСостояние -> Ход.
Даже для трёхмерных - выигрывает первый игрок.
х1 222
о2 1** кроме 11* (всегда можем повернуть систему координат
)х2 111 (угроза 333)
о2 333
х2 112 (угроза 332 и 113, вилка)
--------
Кроме того, состояние игры в пятимерные крестики-нолики описывается (3^5)-мерным вектором с элементами {_,x,o}, то есть мощность множества состояний не превосходит 3^6.
Это очень мало, следовательно, можно построить полное дерево игры, найти в нём выигрышные стратегии и запрограммировать конечный автомат ТекущееСостояние -> Ход.
Кодт @ www.rsdn.ru
Для тех кто не очень хорошо умеет читать повторяю
Для тех кто не очень хорошо умеет читать повторяю
Если не понятно что в случае 5-и мерных крестиков ноликов 6 относится к длинне линии ... т я уж деже не знаю как обьяснить.
<!--QuoteBegin-Kernel+26:02:2004, 09:55 -->
<span class="vbquote">(Kernel @ 26:02:2004, 09:55 )</span><!--QuoteEBegin-->Кодт @ www.rsdn.ru
Для тех кто не очень хорошо умеет читать повторяю
Ааа. Понимаю.
Просто - есть двумерные крестики-нолики - на поле 3*3, и 3-мерные 3*3*3 (держал в руках доску для игры в них )
А есть игра гомоку - где нужно ставить 5 в ряд на достаточно большом поле.
Несложно показать (неконструктивно), что в гомоку у первого игрока есть беспроигрышная стратегия (если бы выигрышная была у второго - то первый сделал бы ход куда подальше и играл как второй).
С целью уравнять шансы, придумана игра рендзю. В ней первый игрок ограничивается (не имеет права делать некоторые вилки, строить более 5 в ряд).
Крестики-нолики, гомоку и рендзю - это разные игры. Поэтому я и не понял сразу.
Так вот, вне зависимости от размерности пространства и длины линии, в гомоку всегда лучшие шансы именно у первого игрока.
Возможно, что стратегия игры проста донельзя.
Первый делает ход примерно в центр пространства и выбирает для себя, в какой плоскости (так! даже не гиперплоскости) он будет оставаться.
Если второй ходит в выбранную плоскость - первый отвечает как если бы он играл на плоскости. Если мимо - то пользуется полученным преимуществом (как бы пропущенным ходом).
Но тут нужно посмотреть... есть подводные камни.
Если первый игрок выстроил 5 в ряд (а, обладая выигрышной стратегией в двумерном гомоку, он это сделает), то вокруг этой пятёрки можно попробовать поставить вилки.
Вполне возможно (нужно исследовать), что даже в трёхмерном пространстве будет достаточно возможностей выстроить 6 в ряд.
<span class="vbquote">(Kernel @ 26:02:2004, 09:55 )</span><!--QuoteEBegin-->Кодт @ www.rsdn.ru
Для тех кто не очень хорошо умеет читать повторяю
Если не понятно что в случае 5-и мерных крестиков ноликов 6 относится к длинне линии ... т я уж деже не знаю как обьяснить. [/quote]
Ааа. Понимаю.
Просто - есть двумерные крестики-нолики - на поле 3*3, и 3-мерные 3*3*3 (держал в руках доску для игры в них
)А есть игра гомоку - где нужно ставить 5 в ряд на достаточно большом поле.
Несложно показать (неконструктивно), что в гомоку у первого игрока есть беспроигрышная стратегия (если бы выигрышная была у второго - то первый сделал бы ход куда подальше и играл как второй).
С целью уравнять шансы, придумана игра рендзю. В ней первый игрок ограничивается (не имеет права делать некоторые вилки, строить более 5 в ряд).
Крестики-нолики, гомоку и рендзю - это разные игры. Поэтому я и не понял сразу.
Так вот, вне зависимости от размерности пространства и длины линии, в гомоку всегда лучшие шансы именно у первого игрока.
Возможно, что стратегия игры проста донельзя.
Первый делает ход примерно в центр пространства и выбирает для себя, в какой плоскости (так! даже не гиперплоскости) он будет оставаться.
Если второй ходит в выбранную плоскость - первый отвечает как если бы он играл на плоскости. Если мимо - то пользуется полученным преимуществом (как бы пропущенным ходом).
Но тут нужно посмотреть... есть подводные камни.
Если первый игрок выстроил 5 в ряд (а, обладая выигрышной стратегией в двумерном гомоку, он это сделает), то вокруг этой пятёрки можно попробовать поставить вилки.
Вполне возможно (нужно исследовать), что даже в трёхмерном пространстве будет достаточно возможностей выстроить 6 в ряд.
Поэтому и сказал что возможно придется длинну линии сделать семь. Шесть взято только потому что когда мы в своё время в универе на парах пытались играть - поняли что "вруную" 6 - вполне достаточно. За пару сыграть если кто-то не лажанул не успеваеш, а на вторую мы к этому времени уже редко ходили . Хотя и для компов тоже можешь попробовать оценить выч. время ... не так уж и мало получется если не пытаться свести это к плоскости ...
. Хотя и для компов тоже можешь попробовать оценить выч. время ... не так уж и мало получется если не пытаться свести это к плоскости ...- Статус
Обучение наступательной кибербезопасности в игровой форме. Начать игру!