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

    Игрок может предложить только такой ЧШ, N которого больше, чем у предыдущего ЧШ. Кто предложит ЧШ с самым большим N- тот победил.

    Например, игра начинается с ЧШ(1-2-3-4-5-6), у которого N=7, так как суммируя числа, расположенные подряд, можно получить числа 1,2,4,5,6,7, но 8 получить не получается.

    Следующий участник может предложить, например, ЧШ(1-2-4-4-5-6) с N = 22. Тогда следующему нужно предложить такой ЧШ, у которого N>22. Сможете?

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


        Круто!

        Цитата Vesper @
        У меня всего один ответ пока что - [спойлер], N=25. Пока не вышло найти больше или доказать, что этот максимальный.


        Кто больше?
          Цитата ya2500 @
          В это играют шестигранниками, в углах которых расположены числа. Из суммы чисел, расположенных подряд(от 1 до 6 чисел)
          Начну с придирок.
          У меня неплохое пространственное воображение, но оно отказывает, когда я пытаюсь представить такое тело.
          Непонятно, что такое угол многогранника (углы и стороны есть в многоугольниках, а в многогранниках только грани, рёбра и вершины)
          Почему числа расположены подряд? И каков смысл размещать эти числа на шестиграннике?

          А теперь из того, что понял. Числа расположены в линию или по циклу? Можно ли суммировать последнее с первым? Можно ли использовать числа больше 6?

          Цитата Vesper @
          Пока не вышло найти больше или доказать, что этот максимальный.
          Чтобы получить числа от 1 до 5 нам необходимы слагаемые 1, 2 и 4. Так что, если максимальное число ограничено 6, то эта последовательность максимальная.
          Всё написанное выше это всего лишь моё мнение, возможно ошибочное.
            Ваще не понял как суммировать.

            Добавлено
            Цитата ya2500 @
            можно получить числа 1,2,4,5,6,7,

            Тут тройка пропущена. Т.е. ряд может быть не полный, что ли?

            Добавлено
            А сколько слагаемых можно брать? У меня бесконечный ряд натур. чисел получился :lol:
            (1-1-1-1-1-1)
              Цитата Суровый @
              А сколько слагаемых можно брать?
              Полагаю, любое количество идущих подряд (считая, что первое идёт за последним, то есть последовательность можно прокручивать), но только в пределах одного круга. Так что каждое берётся не более одного раза.
              Всё написанное выше это всего лишь моё мнение, возможно ошибочное.
                Цитата amk @
                Полагаю, любое количество идущих подряд (считая, что первое идёт за последним, то есть последовательность можно прокручивать), но только в пределах одного круга. Так что каждое берётся не более одного раза.

                Блин, написал бы 6 слагаемых, делов то.
                Сообщение отредактировано: Суровый -
                  Скрытый текст
                  ExpandedWrap disabled
                    type
                     
                      TDigit = array [1..6] of Integer;
                     
                      TDigitRec = record
                        D: TDigit;
                        N: Integer;
                      end;
                     
                      TDigits = array of TDigitRec;
                     
                    procedure SwapDigit(var D1,D2:TDigitRec);
                    var
                      T: TDigitRec;
                    begin
                      T:= D1;
                      D1:= D2;
                      D2:= T;
                    end;
                     
                    function DigitStr(const D:TDigitRec): string;
                    var
                      I: Integer;
                    begin
                      Result:= '';
                      for I:= 1 to 6 do
                        Result:= Result+Format('%d-',[D.D[I]]);
                      SetLength(Result,Length(Result)-1);
                      Result:= Format('%d:  %s',[D.N,Result]);
                    end;
                     
                    procedure PrintDigit(Memo:TMemo; const Digit:TDigits);
                    var
                      I: Integer;
                    begin
                      Memo.Clear;
                      for I:= 0 to Length(Digit)-1 do
                        Memo.Lines.Add(DigitStr(Digit[I]));
                    end;
                     
                    function Summa(const D:TDigit; const Pos,Cnt:Integer): Integer;
                      function GetD(I:Integer): Integer;
                      begin
                        I:= I mod 6;
                        if I=0 then I:= 6;
                        Result:= D[I];
                      end;
                    var
                      I: Integer;
                    begin
                      Result:= 0;
                      for I:= 0 to Cnt-1 do
                        Inc(Result, GetD(Pos+I));
                    end;
                     
                    function GetN(const D:TDigit): Integer;
                    var
                      I,C: Integer;
                      S: array [1..37] of Integer;
                    begin
                      Result:= 0;
                      for I:= 1 to 37 do S[I]:= 0;
                      for I:= 1 to 6 do
                        for C:= 1 to 6 do
                          Inc(S[Summa(D,I,C)]);
                     
                      for I:= 1 to 37 do
                        if S[I]=0 then
                          Exit(I-1);
                    end;
                     
                    { TForm1 }
                     
                    procedure TForm1.Button1Click(Sender: TObject);
                    var
                      I1,I2,I3,I4,I5,I6: Integer;
                      D: TDigit;
                      N: Integer;
                      A: TDigits;
                    begin
                      for I1:= 1 to 6 do
                        for I2:= 1 to 6 do
                          for I3:= 1 to 6 do
                            for I4:= 1 to 6 do
                              for I5:= 1 to 6 do
                                for I6:= 1 to 6 do
                                  begin
                                    D[1]:= I1;
                                    D[2]:= I2;
                                    D[3]:= I3;
                                    D[4]:= I4;
                                    D[5]:= I5;
                                    D[6]:= I6;
                                    N:= GetN(D);
                                    if N<>0 then
                                      begin
                                        SetLength(A,Length(A)+1);
                                        A[Length(A)-1].D:= D;
                                        A[Length(A)-1].N:= N;
                                      end;
                                  end;
                     
                      for N:= Length(A) downto 1 do
                        for I1:= 1 to N do
                          if A[I1-1].N<A[I1].N then
                            SwapDigit(A[I1-1],A[I1]);
                     
                      PrintDigit(Memo1,A);
                    end;

                  Прикреплённый файлПрикреплённый файлResult.zip (73,59 Кбайт, скачиваний: 79)

                  Добавлено
                  Vesper, как ты свою последовательность нашел? Каждое число в ручную проверял, что ли?
                    Цитата Суровый @
                    Каждое число в ручную проверял, что ли?
                    Цепочка 2, 1, 4 сама напрашивается. Дополнить шестёрками и вот она - последовательность.

                    С суммой 25 все последовательности идентичны (отличаются только прокруткой и направлением)
                    Всё написанное выше это всего лишь моё мнение, возможно ошибочное.
                      Если слагаемые ограничены величиной 6, то наилучшая сумма 25 с последовательностью:
                      Скрытый текст
                      1, 4, 6, 6, 6, 2

                      А если величину слагаемых не ограничивать, то можно получить и все суммы до 31:
                      Скрытый текст
                      1, 3, 2, 7, 8, 10


                      Добавлено
                      Оба варианта единственные.
                      Всё написанное выше это всего лишь моё мнение, возможно ошибочное.
                        Цитата amk @
                        А если величину слагаемых не ограничивать, то можно получить и все суммы до 31:

                        А как ты узнал?
                          Так же как и ты, программу написал. Перебрал все комбинации из 6 чисел от 1 до некоторого значения. Проверять слагаемые больше 16 нет смысла, так как иначе не удастся набрать 15 (общая сумма равна 31)

                          Но с единственностью второго решения я наврал (в первый раз проверял числа только до 10). На самом деле их пять
                          Скрытый текст
                          1, 3, 2, 7, 8, 10
                          1, 2, 7, 4, 12, 5
                          1, 2, 5, 4, 6, 13
                          1, 3, 6, 2, 5, 14
                          1, 7, 3, 2, 4, 14


                          Добавлено
                          А вот и программа (файл выдачи сортировал потом отдельно)
                          ExpandedWrap disabled
                            #! /usr/bin/env python3
                            # -*- coding: utf-8 -*-
                             
                            from itertools import product
                             
                            N = 6
                            M = 16
                             
                            def all_variants(s):
                                r = range(len(s))
                                for i in r:
                                    yield s[i:] + s[:i]
                                    yield s[i::-1] + s[:i:-1]
                             
                            def variants(n, m):
                                for s in product(range(1, m+1), repeat=n):
                                    if all(s <= v for v in all_variants(s)):
                                        if sum(s) == 31: yield s
                                        #yield s
                             
                            def sums(s):
                                n = len(s)
                                r = {sum(s)}
                                for l in range(1, n):
                                    for i in range(n):
                                        r.add(sum((s + s)[i: i+l]))
                                return r
                             
                            def main():
                                t = set(range(1, N*(N - 1) + 3))
                                outfile = open('SeqSums.txt', 'wt')
                                for s in variants(N, M):
                                    r = sums(s)
                                    x = min(t.difference(r)) - 1
                                    print('%3d'%x, s, file=outfile)
                                outfile.close()
                             
                            if __name__ == '__main__':
                                main()
                          Всё написанное выше это всего лишь моё мнение, возможно ошибочное.
                            Победителем признаётся amk.

                            Цитата amk @
                            если величину слагаемых не ограничивать, то можно получить и все суммы до 31:

                            Цитата ya2500 @
                            Из суммы чисел, расположенных подряд(от 1 до 6 чисел),


                            Величина слагаемых не ограниченна. Однако, ограничено их кол-во; и, да- каждое можно использовать лишь один раз.

                            Однако, игры не получилось и не получится- слишком близок к полу потолок.

                            А что если получать не "последовательно числа натурального ряда, до некоторого N включительно", а, например, "последовательно простые числа, до некоторого N включительно" ?? - если хочется чего-то, над чем голову поломать ))
                                Цитата Суровый @
                                Vesper, как ты свою последовательность нашел? Каждое число в ручную проверял, что ли?

                                Логикой. На бумажке. Обнаружил, что если единицу поставить между 2 и 4, получается весело, и следующее число, которое надо добавить в ЧШ, должно быть 6. В итоге шестерками добил, прифигел, выложил.

                                Цитата ya2500 @
                                "последовательно простые числа, до некоторого N включительно"

                                Ну опять, надо иметь 2 и 3 заведомо (или 2 и 1, но смысла в единице нет для дальнейших простых чисел - они нечетные), дальше полный перебор. Потолком будет число P(31)=127, но из-за нерегулярности ряда потолок наверно не достать. А проверяется точно так же как у amk.
                                Долог путь в бессмертие... я еще вернусь.
                                Профильный скилл "Телепатия" 8%
                                ТРОЛЛЬ - Троян Разрушительный Опасный, Лучше ЛинятЬ (с) Freezing Spell
                                Прошу потестить игру.
                                  Цитата 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
                                                              Прошу потестить игру.
                                                                Цитата
                                                                Набор очков прекращается в том и только том случае, когда текущий игрок набирает в сумме 12 очков.


                                                                Vesper, не менее 12 очков.

                                                                Добавлено
                                                                Смысл в том, что если 12 очков есть, то следующим ходом противник гарантированно устроит игроку пройгрыш, выбрав десятку.
                                                                  Непонятна ваша мысль, Vesper, ибо:
                                                                  1. пусть у 1-го 7 очков;
                                                                  2. пусть у второго - 10;
                                                                  3. Набирает первый: и выпало в сумме 5 пальцев;
                                                                  4. Стало 12 очков у первого. Набор прекращён.
                                                                  5. У первого в итоге больше, он победил. Нет никакой победы вторым. :whistle:
                                                                    Цитата Славян @
                                                                    1. пусть у 1-го 7 очков;
                                                                    2. пусть у второго - 10;
                                                                    3. Набирает первый: и выпало в сумме 5 пальцев;
                                                                    4. Стало 12 очков у первого. Набор прекращён.
                                                                    5. У первого в итоге больше, он победил. Нет никакой победы вторым.


                                                                    Немного не так. Сначала набирает очки первый игрок, поэтому у второго игрока ноль очков. Как только первый(с участием и второго) наберёт 12 или более очков, то(если не случилось перебора), набирает очки второй игрок(с участием и первого).

                                                                    Добавлено
                                                                    Короч, вот ссыль на игру(21 на пальцах без рандома) онлайн: https://logic-games.spb.ru/twentyone/
                                                                    Сообщение отредактировано: ya2500 -
                                                                      Цитата Славян @
                                                                      4. Стало 12 очков у первого. Набор прекращён.
                                                                      5. У первого в итоге больше, он победил. Нет никакой победы вторым.
                                                                      Получается сильный перекос в пользу первого игрока. Поскольку при такой интерпретации выигрывает игрок, первым набравший 12 очков.
                                                                      В описании написано не совсем конкретно, но, похоже, при достижении игроком суммы 12 и более игра не прекращается, прекращается набор очков для этого игрока. А для другого он продолжается, пока он тоже не наберёт 12 или более.
                                                                      На это намекает оговорка про гарантированный перебор.

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


                                                                        Когда для первого игрока набор очков прекращается, тогда начинается набор очков второго игрока.
                                                                          Цитата amk @
                                                                          Думаю преимущество у второго, так как при наборе им очков известно количество очков, уже набранных первым игроком.
                                                                          Мне тоже так показалось вначале (всё-таки это информация, кою можно в плюс загнать как-то), но после подумалось, что знание это несколько искусственно, а (в итоге) снивелируется увеличенным риском вылететь, так что пока склонен думать про ничью в среднем. :-?
                                                                            Цитата Славян @
                                                                            Мне тоже так показалось вначале (всё-таки это информация, кою можно в плюс загнать как-то), но после подумалось, что знание это несколько искусственно, а (в итоге) снивелируется увеличенным риском вылететь, так что пока склонен думать про ничью в среднем.
                                                                            Вообще, я когда писал про преимущество, имел в виду что вероятность завершения всей партии в пользу второго игрока выше вероятности завершения её в пользу первого. Но я и тогда не был уверен, что эта вероятность выше 50% (есть ведь ещё и случай, когда набрано равное количество очков).
                                                                            Дело в том, что в зависимости от набранного противником числа очков меняются вероятности выбора числа пальцев, и средний выигрыш слегка повышается.
                                                                            Так что, думаю, если по результатам партии проигравший отдаёт выигравшему монетку, то монетки в конце концов все перекочуют ко второму игроку.
                                                                            Всё написанное выше это всего лишь моё мнение, возможно ошибочное.
                                                                              Цитата amk @
                                                                              в зависимости от набранного противником числа очков меняются вероятности выбора числа пальцев, и средний выигрыш слегка повышается.
                                                                              Несколько мутное утверждение. :blush:
                                                                              Мысленно: предполагаем, что набрано противником a1 очков - получаем одни шансы, a2 - другие, и т.д. В итоге же, все эти знания о набранных очках кочуют в те или иные вероятности, что (как мне думается) сведёт всё к 50%.
                                                                              Но, бесспорно, неплохо бы точнее посчитать. :yes:
                                                                                Тогда реально нетривиальная игра. С учетом того, что выбор синхронный, получается, что первым ходом выбирать надо 10 первому, но если второй выберет два, первый перестает набирать - тогда надо выбирать 9, соперник тогда может выбрать 3 и первый в пролете, но имеет шансы загнать второго в 12 и выиграть... в этом случае первому нужно на первом ходу выбирать чистый рандом, причем ХЗ откуда, то ли от 2, то ли от 0 вообще. А это уже неинтересно.
                                                                                Долог путь в бессмертие... я еще вернусь.
                                                                                Профильный скилл "Телепатия" 8%
                                                                                ТРОЛЛЬ - Троян Разрушительный Опасный, Лучше ЛинятЬ (с) Freezing Spell
                                                                                Прошу потестить игру.
                                                                                  Это вообще сильно смахивает на банальную игру с одним кубиком-костью: кто больше выкинет. Когда первый выкинул, очевидно, что шансы второго весьма уточняются: чаще выигрыш или проигрыш. Но т.к. играть=кидать обязательно, то оказывается, что в итоге вероятности равны, по 50% на брата. :whistle:
                                                                                    Цитата Славян @
                                                                                    Это вообще сильно смахивает на банальную игру с одним кубиком-костью


                                                                                    Существенная разница в том, что в этой игре совсем нет "генераторов случайности", кроме самих игроков. То есть, вся случайность - результат их выбора.

                                                                                    Добавлено
                                                                                    Цитата Vesper @
                                                                                    Тогда реально нетривиальная игра. С учетом того, что выбор синхронный, получается, что первым ходом выбирать надо


                                                                                    Что надо выбрать - не такой простой вопрос в нетривиальной игре. Тут думать надо.
                                                                                      Цитата amk @
                                                                                      В принципе игру можно проанализировать с точки зрения теории игр, хотя это будет и сложно. Оптимальной выигрышной стратегии не получится (игра с неполной информацией без седловой точки), но возможна смешанная стратегия,


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

                                                                                      Например, для N = 12, у Игрока есть простая выигрышная стратегия:

                                                                                      На первом ходу Игрок показывает "10"
                                                                                      Если у Игрока 10 очков, то показывает "1"
                                                                                      Если у Игрока 11 очков, то показывает "0"
                                                                                      Если у Игрока более 11 очков, то он победил))

                                                                                      - и здесь есть шанс "зависания", если и Игрок и Противник всё время будут выбирать "0". Будем считать это ничьей(блин, никуда от неё не деться), но если Игрок считает 12 очков желаемым результатом, то он и ничью будет считать желаемым результатом. А в дальнейшем, может и не будет такой херни возникать.

                                                                                      А вот для N = 13 анализ будет уже значительно сложнее.
                                                                                        Подобными играми занимается так называемая теория игр (часть более общей теории принятия решений - теории оптимального управления). Другое, более серьёзное название - теория оценки рисков. Ни в школе, ни в вузе не изучается, хотя по ней существует полно литературы, в том числе популярной. К её анализу приложили руку великие математики прошлого, Паскаль, Эйлер, Лейбниц и др.
                                                                                        От непосредственно рассматриваемых там эта игра отличается только наличием нескольких раундов, между которыми состояние игры различается.
                                                                                        Но среди этих состояний есть конечные, в которых определено, кто выиграл.
                                                                                        Среди оставшихся много позиций ведут в эти конечные.
                                                                                        То есть для каждого раунда (начиная с предконечных состояний) можно построить таблицу игры. Все эти таблицы лишены седловых точек, поэтому на каждом раунде оптимальной стратегией будет выбор одного из чисел с определённой вероятностью. Такая стратегия обеспечивает некоторое матожидание выигрыша. Отступление от такой стратегии только уменьшит выигрыш (увеличит проигрыш) игрока.
                                                                                        Несколько усложняет анализ наличие нулевого хода, когда оба игрока выбирают 0 но и с ним можно справиться, тем более, что вероятность такого отыгрыша, благодаря смешанной (вероятностной) стратегии, невелика.

                                                                                        Цитата ya2500 @
                                                                                        Можно упростить анализ, рассматривая отдельно набор очков одним Игроком с его Противником.
                                                                                        Увы. Такое упрощение приведёт тебя к гарантированному проигрышу
                                                                                        Цитата ya2500 @
                                                                                        Например, для N = 12, у Игрока есть простая выигрышная стратегия:

                                                                                        На первом ходу Игрок показывает "10"
                                                                                        Если у Игрока 10 очков, то показывает "1"
                                                                                        Когда у игрока 10 очков, противник показывает тоже 1 и игрок останавливает набор на 12 очках. Противнику достаточно набрать больше 12 очков и он выиграл.

                                                                                        Как я уже написал выше, никакая чистая стратегия в этой игре оптимальной быть не может.


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

                                                                                        Можно заставить играть друг против друга две такие машины. Естественно лучше не использовать коробки и бусины, а написать программу. Или заставить машину играть саму с собой.
                                                                                        Всё написанное выше это всего лишь моё мнение, возможно ошибочное.
                                                                                          Цитата ya2500 @
                                                                                          Существенная разница в том, что в этой игре совсем нет "генераторов случайности", кроме самих игроков. То есть, вся случайность - результат их выбора.
                                                                                          Существенность разницы запросто может вылиться в нулевое отличие. Так, если игроки на пальцах выкидывают очки и при чётной сумме - победа первому, а при нечётной - второму, то вроде как и выбор, но на деле - тупой кубик-кость. :yes-sad: ;)
                                                                                            Цитата amk @
                                                                                            Когда у игрока 10 очков, противник показывает тоже 1 и игрок останавливает набор на 12 очках. Противнику достаточно набрать больше 12 очков и он выиграл.


                                                                                            Эмм... нет:

                                                                                            Цитата ya2500 @
                                                                                            Можно упростить анализ, рассматривая отдельно набор очков одним Игроком с его Противником. Для начала рассмотрим второго игрока, считая, что у него есть цель набрать не менее N очков, что будет его выигрышем и проигрышем противника(так мы исключим из рассмотрения ничьи, желательность которых можно будет рассмотреть позже). И затем, когда будет готов этот анализ, можно будет на его основе провести анализ для первого игрока - к набору какого количества очков ему нужно стремиться? - на мой взгляд, это правильный вопрос.


                                                                                            - то есть, я рассматривал стратегию набора очков вторым игроком, которому уже известно, сколько набрал первый игрок.

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


                                                                                            Да, но в ЭТОЙ игре не так-то просто понять, с какой вероятностью какие числа выбирать.

                                                                                            Добавлено
                                                                                            Цитата amk @
                                                                                            Не совсем уверен, но вроде бы в подобные игры хорошо учится играть спичечно-бусинная машина.


                                                                                            Да, я думал об этом. Она хороша нахождения выигрышной стратегии.

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


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

                                                                                              Добавлено
                                                                                              Но интереснее, конечно, было бы найти не вероятности, а стратегию.
                                                                                                Цитата Славян @
                                                                                                Существенность разницы запросто может вылиться в нулевое отличие. Так, если игроки на пальцах выкидывают очки и при чётной сумме - победа первому, а при нечётной - второму, то вроде как и выбор, но на деле - тупой кубик-кость. :yes-sad: ;)

                                                                                                Эта игра, кажется, на это похожа. То есть оптимальная стратегия - кидать рандом, причем для обоих игроков.
                                                                                                Долог путь в бессмертие... я еще вернусь.
                                                                                                Профильный скилл "Телепатия" 8%
                                                                                                ТРОЛЛЬ - Троян Разрушительный Опасный, Лучше ЛинятЬ (с) Freezing Spell
                                                                                                Прошу потестить игру.
                                                                                                  Цитата Vesper @
                                                                                                  Эта игра, кажется, на это похожа. То есть оптимальная стратегия - кидать рандом, причем для обоих игроков.


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

                                                                                                  Да и касательно других ситуаций - рандом может быть разным. Не факт, что он должен быть равновероятным выбором от 0 до 10. И даже наверняка не должен. То есть, плохая стратегия снизит шансы на победу. А это уже означает, что игра непохожа в чём-то существенном.

                                                                                                  Добавлено
                                                                                                  Цитата ya2500 @
                                                                                                  А вот для N = 13 анализ будет уже значительно сложнее.


                                                                                                  Сходу - в некоторых ситуациях получается, что стратегия и Игрока и Противника сводится к выбору 50/50 из двух вариантов. Подробнее смогу расписать, когда доберусь толком, выделю время на это.

                                                                                                  НО действительно, хорошо бы поиск стратегии как-то автоматизировать. Или по методу бусинной машины или как-то ещё.
                                                                                                  Сообщение отредактировано: ya2500 -
                                                                                                    У меня где-то есть несколько книг по теории игр. Ещё советских времён издания. Но я их читал ещё в школе и институте - когда распределился, не до них стало, к тому же по работе мне эти знания не сказать чтобы полезны были (была бы персоналка, как сейчас, я бы конечно приспособил их к работе, я тогда даже помнится, пытался компилятор Паскаля свой написать, и даже написал, но проверить, работает ли, не на чем было). Есть вполне удобоваримый метод вычисления вероятностей, дающих максимально ожидаемый выигрыш при оптимальной игре противника (при не оптимальной выигрыш только возрастает). За 30 лет я его совершенно забыл. Впрочем, при желании, можно самому вывести.
                                                                                                    Всё написанное выше это всего лишь моё мнение, возможно ошибочное.
                                                                                                      Цитата amk @
                                                                                                      Не совсем уверен, но вроде бы в подобные игры хорошо учится играть спичечно-бусинная машина.

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


                                                                                                      И, всё-таки, похоже, такая машина - лучший способ нахождения стратегии. Чтобы хорошо проработать все веточки, задаём изначально вероятность 50% для выбора хода случайным образом. То есть, 50/50 либо следуем стратегии, либо равновероятно выбираем любой ход из возможных. Затем, постепенно, снижаем эту вероятность до 0%.

                                                                                                      После того, как 2 машины играют сами с собой чётко по своей стратегии, крутим это дело, а через каждые 1000 игр отслеживаем момент останова:

                                                                                                      Цитата ya2500 @
                                                                                                      остановимся тогда, когда новые игры будут незначительно(менее заданной точности) влиять на результат.
                                                                                                      0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                                                                                      0 пользователей:


                                                                                                      Рейтинг@Mail.ru
                                                                                                      [ Script Execution time: 0,3679 ]   [ 19 queries used ]   [ Generated: 18.11.19, 21:31 GMT ]