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

Тема в разделе "Свободное общение", создана пользователем Kernel, 25 окт 2003.

Статус темы:
Закрыта.
  1. Kernel

    Kernel Гость

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

    admin Well-Known Member

    Регистрация:
    8 авг 2003
    Сообщения:
    2.811
    Симпатии:
    0
    Kernel
    Поясни что это такое :) А то трудно укладывается в голове :)
     
  3. ArtuR

    ArtuR Гость

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

    Kernel Гость

    Короче, идет последовательность ходов задаваемая целочисленными векторами в 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-хмерного случая :)
     
  5. admin

    admin Well-Known Member

    Регистрация:
    8 авг 2003
    Сообщения:
    2.811
    Симпатии:
    0
    Kernel
    Ладно. С алгоритмическим мышлением у меня труба :) Как ты хоть такой чемп провести хочешь? Что в качестве приза выставим?
     
  6. Vagor.ini

    Vagor.ini Гость

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

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

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

    --------

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

    Kernel Гость

    Кодт @ www.rsdn.ru
    Для тех кто не очень хорошо умеет читать повторяю
    Если не понятно что в случае 5-и мерных крестиков ноликов 6 относится к длинне линии ... т я уж деже не знаю как обьяснить.
     
  9. Гость

    <!--QuoteBegin-Kernel+26:02:2004, 09:55 -->
    <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 в ряд.
     
  10. Kernel

    Kernel Гость

    Поэтому и сказал что возможно придется длинну линии сделать семь. Шесть взято только потому что когда мы в своё время в универе на парах пытались играть - поняли что "вруную" 6 - вполне достаточно. За пару сыграть если кто-то не лажанул не успеваеш, а на вторую мы к этому времени уже редко ходили :). Хотя и для компов тоже можешь попробовать оценить выч. время ... не так уж и мало получется если не пытаться свести это к плоскости ...
     
Загрузка...
Похожие Темы - мерные крестики нолики
  1. Rpp
    Ответов:
    1
    Просмотров:
    812
  2. Малгано
    Ответов:
    0
    Просмотров:
    1.292
  3. Lizzz
    Ответов:
    1
    Просмотров:
    1.246
  4. Fazer77777
    Ответов:
    1
    Просмотров:
    1.667
  5. 203
    Ответов:
    12
    Просмотров:
    2.449
Статус темы:
Закрыта.

Поделиться этой страницей