На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное DigiMania RSS
msm.ru
! Оставь надежду всяк сюда входящий
1) На раздел распространяются все правила форума.
2) Ответы на головоломки необходимо давать только в теге SPOILER. Сообщения в обход этого правила будут удаляться. Постоянное
нарушение данного пункта правил, повлечет за собой наказание.
3) Автор темы должен указать, известно ли ему решения задачи и сроки в которые он опубликует решение.Рекомендуется вести список отгадавших в первом сообщении.
4) При создании новой темы, в описании или в самом названии четко укажите разновидность задачи.
5) Полная версия правил раздела, находится в теме правила раздела.
Модераторы: Братец Лис
Страницы: (4) 1 [2] 3 4  все  ( Перейти к последнему сообщению )  
> Игра гекс-сумм-последовательность
    Цитата Vesper @
    А проверяется точно так же как у amk.
    Да, надо только вместо множества (1..32) множество возможных простых чисел сформировать. И после получения минимального из ненайденных найти для него предыдущее.
    Однако перебор понадобится более глубокий - слагаемые будут участвовать большие по величие.

    Добавлено
    Цитата ya2500 @
    Однако, игры не получилось и не получится- слишком близок к полу потолок.
    Игра не получится по другой причине, на "ходы" здесь не влияет предыстория, что даёт возможность сразу сделать выигрывающий ход.

    В этом смысле перспективнее игры с неполной информацией, когда оба игрока делают ход одновременно и независимо, или с предысторией, когда лучший ход зависит от текущей позиции.

    К, примеру, такая игра:
    Два игрока поочерёдно выписывают на листе бумаги не повторяющиеся числа от 1 до N.
    Если после добавления очередного числа, можно (взяв часть выписанных чисел) набрать сумму, равную M, игрок, сделавший последнее добавление, проигрывает.
    Естественно, N < M, N*(N + 1) > 2*M. А лучше, если больше по крайней мере раза в два.
    Игра гарантированно завершается проигрышем одного из игроков. Стратегия сразу неясна.
    Для начала можно попробовать по-анализировать игры с N=4, M=5 и N=5, M=7.

    Возможен вариант, когда числа можно повторять, но, подозреваю, в этом случае будет существовать какая-нибудь регулярная стратегия, ведущая к выигрышу.
    Всё написанное выше это всего лишь моё мнение, возможно ошибочное.
      Цитата amk @
      Два игрока поочерёдно выписывают на листе бумаги не повторяющиеся числа от 1 до N.
      Если после добавления очередного числа, можно (взяв часть выписанных чисел) набрать сумму, равную M, игрок, сделавший последнее добавление, проигрывает.
      Естественно, N < M, N*(N + 1) > 2*M. А лучше, если больше по крайней мере раза в два.
      Игра гарантированно завершается проигрышем одного из игроков. Стратегия сразу неясна.
      Для начала можно попробовать по-анализировать игры с N=4, M=5 и N=5, M=7.

      N=4, M=5 - выигрывает второй игрок. Если первый игрок играет 1 или 4, второй играет 3 или 2, иначе второй игрок играет 1. После чего первому остается собрать или 2-3, или 1-4 в строке - проигрыш.
      N=5, M=7 - выигрывает первый игрок. Ход 3, дальше либо собрать 3-1-2, либо 3-1-5. Следующее добавление проигрывает. (Есть, правда, проигрышный ход - если первый игрок ходит 4, второй ходит 2, следующее добавление приведет или к 4-2-1, либо к 2-5, либо к 4-3.)
      На таких N и M работает полный перебор дерева, причем почти с первого же хода начинают появляться недопустимые ходы. (Если не считать в этом множестве дублирующие ходы) Я думаю, что написать программу, определяющую, кто выиграет в такой игре при заданных N, M, будет неплохим заданием по программированию на первом курсе :)
      Долог путь в бессмертие... я еще вернусь.
      Профильный скилл "Телепатия" 8%
      ТРОЛЛЬ - Троян Разрушительный Опасный, Лучше ЛинятЬ (с) Freezing Spell
      Прошу потестить игру.
        Цитата Vesper @
        будет неплохим заданием по программированию на первом курсе


        Такие задания мне интересны.

        А если, допустим, N=4*t, M=5*t, где t- номер хода?

        Поясняю:

        ход 1: 1й игрок выбирает одно из чисел 1..4, а проигрышем на этом ходу будет сумма = 5 (что невозможно).

        ход 2: 2й игрок выбирает одно из чисел 1..8, не совпадающее с ранее использованным, а проигрышем на этом ходу будет сумма = 10.

        и тд
          Vesper, При больших N и M дерево сильно разрастается и делать полный анализ становится затруднительно.
          А вообще, полный анализ возможен для любой игры, где игроки делают ходы поочерёдно. В частности сообщалось, что он уже выполнен для шашек. Для шахмат не хватает вычислительных мощностей.
          Для некоторых игр (го, калах) он настолько сложен (даже по сравнению с шахматами) что никто даже не думает за него браться.
          Всё написанное выше это всего лишь моё мнение, возможно ошибочное.
            Цитата amk @
            Vesper, При больших N и M дерево сильно разрастается и делать полный анализ становится затруднительно.
            А вообще, полный анализ возможен для любой игры, где игроки делают ходы поочерёдно. В частности сообщалось, что он уже выполнен для шашек. Для шахмат не хватает вычислительных мощностей.
            Для некоторых игр (го, калах) он настолько сложен (даже по сравнению с шахматами) что никто даже не думает за него браться.


            Интереснее такие игры, в которых: полный перебор слишком сложен И существуют не сложные эвристики, на которые можно опираться и которые можно находить новые и новые. То есть, интерес не в переборе, а в построении стратегии, основанной на наборе относительно не сложных предположений.
              Цитата amk @
              он уже выполнен для шашек

              Про анализ шашек 8х8 слышал, про 10х10 ещё нет, но думаю, что шашки 10х10 не сложнее шахмат, т.е. и их уже могли разобрать.
              Цитата amk @
              калах

              Неужели там так много ходов, что дерево оказывается мощнее шахматного? Или разговор о какой-то конкретной разновидности калаха (их сотни ЕМНИП)?
              Цитата ya2500 @
              А если, допустим, N=4*t, M=5*t, где t- номер хода?

              Это посерьезнее, но из-за расширения возможности ходов ИМХО игра в такой концепции может не закончиться никогда. Хотя в неё можно активно выиграть, если собрать на n-м ходу 5*(n+1), тогда вне зависимости от следующего хода соперник продует. Хм-м-м-м... Такой ход будет возможен в случае, если на столе нет суммы 5, и есть сумма n+5... т.е. например, в ситуации 3-1-6 доступен ход 15 за второго игрока (15<4*4, 1+3+6+15=25), выигрывающий партию. Если сумма 5 есть, то такой ход невозможен, так как проигрывает партию (т.е. 3-5-12 нельзя, так как есть 3+12=15). Как я понимаю, второй игрок тогда выигрывает после хода 5 на своем ходу. Т.е. х-5-у-(5-у, у<5, или 5-х, у>5) выигрывает при любом х и у.

              В случае варьирования параметров вида (a*n,b*n), нужно считать для какого наименьшего n T(n)>b*n, где T(n) - треугольное число (1+2+...+n), потом берем его четность, выигрывает противоположный игрок. То есть всегда в таких играх выигрывает второй игрок :) так как T(2*b+1)===b*(2*b+1). Кстати, в этом случае исход игры не зависит от А, но если a>=2*b, выигрывает первый игрок ходом 2*b.
              Долог путь в бессмертие... я еще вернусь.
              Профильный скилл "Телепатия" 8%
              ТРОЛЛЬ - Троян Разрушительный Опасный, Лучше ЛинятЬ (с) Freezing Spell
              Прошу потестить игру.
                Калах пожалуй сравним с шашками. Глубина дерева не такая уж большая (думаю, редко приходится делать более 50 ходов). Число вариантов хода редко (с учётом условия продолжения хода) превосходит шесть. Число возможных позиций я бы оценил где-то порядка 1010. А не анализировали, потому что мало кто в эту игру умеет играть.
                Разновидностей калаха не так уж много. Отличия между ними в основном касаются укладки последнего камня в калах и в свою пустую ячейку.
                Пожалуй, наиболее известна разновидность, с продолжением хода в первом случае, и перекладке камней из своей и соседней непустой чужой ячейки в калах во втором. Именно эта разновидность когда-то была описана в "Науке и жизни".

                Вот Го действительно сложен для анализа там на первом ходу можно поставить камень в одну из 361 позиций. Партия продолжается 100 ходов и более. Соответственно число возможных позиций огромно (и почти все они теоретически достижимы, даже бессмысленные)
                Всё написанное выше это всего лишь моё мнение, возможно ошибочное.
                  Цитата ya2500 @
                  Интереснее такие игры, в которых: полный перебор слишком сложен И существуют не сложные эвристики, на которые можно опираться и которые можно находить новые и новые.


                  Напр в шашках и шахматах, ориентировочно можно считать, что больше фигур- лучше. А в Го- что хорошо бы не отдавать свои камни. То есть, не чистая абстракция с цифрами.
                    Цитата ya2500 @
                    А в Го- что хорошо бы не отдавать свои камни

                    Не отдавать не камни, а территорию - именно она есть мерило очков в го. Камни просто к ней приравнены. Мало того, "не отдавать" мало, надо ещё захватывать, а это крайне нетривиально. Хотя и эвристически можно поискать подходящие ходы с этой целью. Но видишь - мало этого, понадобилась эпическая нейросеть с обучением (и хз как она в итоге делает выбор хода), но задача таки решена.
                    Долог путь в бессмертие... я еще вернусь.
                    Профильный скилл "Телепатия" 8%
                    ТРОЛЛЬ - Троян Разрушительный Опасный, Лучше ЛинятЬ (с) Freezing Spell
                    Прошу потестить игру.
                      ЗДЕСЬ описана, вроде бы, простая игра с полной информацией, выигрышная стратегия которой ещё не найдена.
                        Цитата ya2500 @
                        ЗДЕСЬ описана, вроде бы, простая игра с полной информацией, выигрышная стратегия которой ещё не найдена.
                        Ну не то, чтобы не найдена. Только она достаточно сложна, чтобы её можно быдло легко описать. По крайней мере программу, которая гарантированно у меня в эту игру выигрывает, я уже написал.
                        В программе используется "табличная" стратегия. Для каждого количества семечек, просто хранится набор из нескольких (вообще-то, достаточно и одного) возможных (при отсутствии ограничений) ходов. Программа отбрасывает те из них, что не проходят ограничения и выбирает один из оставшихся.
                        Сообщение отредактировано: amk -
                        Всё написанное выше это всего лишь моё мнение, возможно ошибочное.
                          Цитата amk @
                          можно быдло легко


                          Ну вот, я стараюсь, ищу задачки, а тут такое :)
                            1. Я считаю, что ЭТА тема - про обсуждение стратегий в различных играх.

                            2. Конкретно сейчас я хочу окончательно поставить точку в парадоксе неожиданной казни.

                            Цитата
                            Однажды в воскресенье начальник тюрьмы вызвал преступника, приговорённого к казни, и сообщил ему: «Вас казнят на следующей неделе в полдень. День казни станет для вас сюрпризом, вы узнаете о нём, только когда палач в полдень войдёт к вам в камеру». Начальник тюрьмы не имел права врать осуждённому на казнь, иначе это считалось нарушением и казнь отменялась.

                            Заключённый подумал над его словами и улыбнулся: «В воскресенье меня казнить не могут! Ведь тогда уже в субботу вечером я буду знать об этом. А, по словам начальника, я не буду знать день своей казни. Следовательно, последний возможный день моей казни — суббота. Но если меня не казнят в пятницу, то я буду заранее знать, что меня казнят в субботу, значит, и её можно исключить». Последовательно исключив пятницу, четверг, среду, вторник и понедельник, преступник пришёл к выводу, что начальник не сможет его казнить, выполнив все свои слова.

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


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

                            А правила этой игры таковы:

                            - Начальник тюрьмы(разумеется, в тайне от заключённого), выбирает день казни(от 1 до 7).

                            - Заключённый имеет шанс утром любого дня заявить о том, что ожидает казни в этот день, НО только один раз!

                            нюанс одного ожидания
                            тут получается некоторая нестыковка с тем, что в последний день заключённый по-любому будет ожидать, что его казнят в этот день; НО это ожидание нивелируется тем, что он ожидал казни и в другой день, когда казнь реально не состоялась. Как-то так. То есть, я(возможно, не вполне корректно) определяю, что заключённый может по-настоящему ожидать казни лишь в один из дней недели, иначе это "неправильное ожидание". Если же я не прав, то заключённый просто может ожидать казни каждый день И это и будет решением парадокса в пользу заключённого.


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


                            1) ЕСЛИ заключённые могут знать и учитывать стратегию начальника, ТОГДА, оптимальная стратегия начальника - равновероятно выбирать число от 1 до 7. Ибо повышение вероятности выбора любых дней перед другими, приведёт к тому, что заключённые будут выбирать один из наиболее вероятных дней и казни будут отменяться чаще. И какой бы хитрой ни была стратегия начальника, всё сводится к тому, что заключённые будут вычислять вероятности выбора каждого дня и выберет один из наиболее вероятных.

                            2) ЕСЛИ заключённые не могут знать стратегию начальника, ТОГДА они будут делать выводы из ранее происходивших казней, наблюдая выбранные начальником дни И выискивая закономерности. И лучшим для начальника будет вариант, когда нет никакой закономерности, а каждый раз любой из семи дней выбирается равновероятно.

                            ===

                            P.S.

                            Если же заключённый таки может ожидать казни более чем в один день, но не каждый день, то рассуждения все те же. Только "дней ожидания" будет больше. Но день казни таки всё равно оптимально выбирать равновероятно, в любой из дней, включая даже самый последний.
                              Игра 21 на пальцах (без рандома)

                              Наткнулся в тырнетах на занятную игру, предлагаю обсудить оптимальную стратегию. Правила таковы:

                              - Цель игры - набрать в сумме больше очков, чем соперник, но не более 21.
                              - Если игрок набирает более 21 очка, он тут же проигрывает.
                              - Игроки делают ход, одновременно выбирая количество пальцев(от 0 до 10).
                              - Сумма пальцев складывается и записывается игроку, который набирает очки на данном этапе.
                              - Очки игроки набирают по очереди(сначала первый, затем второй).
                              - Набор очков прекращается в том и только том случае, когда текущий игрок набирает в сумме 12 очков.

                              Добавлено
                              Ну и, когда обоими игроками прекращён набор очков, то выигрывает тот, у кого их больше(если, конечно, никто из игроков не проиграл раньше, превысив 21).
                                Цитата ya2500 @
                                - Набор очков прекращается в том и только том случае, когда текущий игрок набирает в сумме 12 очков

                                12 или "больше или равно 12"? Если первое, то выигрывает второй, потому как первый будет первым, вылетевшим за 21.
                                Долог путь в бессмертие... я еще вернусь.
                                Профильный скилл "Телепатия" 8%
                                ТРОЛЛЬ - Троян Разрушительный Опасный, Лучше ЛинятЬ (с) Freezing Spell
                                Прошу потестить игру.
                                1 пользователей читают эту тему (1 гостей и 0 скрытых пользователей)
                                0 пользователей:
                                Страницы: (4) 1 [2] 3 4  все


                                Рейтинг@Mail.ru
                                [ Script Execution time: 0,1638 ]   [ 14 queries used ]   [ Generated: 25.08.19, 14:14 GMT ]