Re: Спасти принцесс
От: biochemist СССР https://www.anekdot.ru/i/caricatures/normal/20/7/27/1595846503.jpg
Дата: 04.03.20 18:09
Оценка:
Здравствуйте, nikholas, Вы писали:

N>Принцессы знают о повадках Злобного Дракона и могли заранее до похищения договориться
Всегда говорить "решка".
«Национализм во мне столь естественный, что никогда никаким интернационалистам его из меня не вытравить»
Менделеев Д. И.
Re[2]: Спасти принцесс
От: Erop Россия  
Дата: 05.03.20 08:08
Оценка:
E>Интересно, можно ли превзойти?


Нашлась симметричная стратегия с вероятностью победы 89/128 (0.6953125)

{0: ( 
     (0, 0, 0, 0),
     (0, 0, 0, 1),
     (0, 0, 1, 0),
     (0, 0, 1, 1),
     (0, 1, 0, 1),
     (0, 1, 1, 1),
     (1, 1, 1, 1)
    ),
 1: ((0, 1, 0, 0), (0, 1, 1, 0), (1, 1, 0, 0), (1, 1, 1, 0)),
 2: ((1, 1, 0, 1),),
 3: ((1, 0, 0, 0), (1, 0, 0, 1), (1, 0, 1, 0), (1, 0, 1, 1))}
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[2]: Спасти принцесс
От: Erop Россия  
Дата: 05.03.20 09:02
Оценка:
Здравствуйте, biochemist, Вы писали:

N>>Принцессы знают о повадках Злобного Дракона и могли заранее до похищения договориться
B>Всегда говорить "решка".

Непер в том, что им надо сказать не "решка", а номер броска в чужой подпоследовательности...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re: Спасти принцесс
От: Erop Россия  
Дата: 05.03.20 09:14
Оценка:
Здравствуйте, nikholas, Вы писали:

N>Принцессы знают о повадках Злобного Дракона и могли заранее до похищения договориться
N>о стратегиях. Как им следует себя вести и чему равна вероятность спасения?


Я тут вспомнил, вдруг, что это таки этюды для программистов
Если ограничиться только конечными последовательностями, то можно пытаться что-то считать.
Для простоты, предлагаю считать, что каждой тупо дают последовательность из N монет и надо выбрать номер в последовательности другой.
Соответственно, стратегия принцессы, в таком случае, это просто отображение любой последовательности длины N на номер от 0 до N-1, включая концы (да, я считаю с 0 )
  "Итого, пишем..." 
def inverse_dictionary( d ) :
    res = { d[k]:set() for k in d}
    for k in d :
        res[d[k]].add( k )
    return { k:tuple( sorted( res[k] ) ) for k in sorted( res ) }


def сartesian_2( set1, set2 ) :
    for i in set1 :
        for j in set2 :
            yield (i, j)

            
def all_seq( n, elements=(0,1) ) :
    """
    возвращает все возможные последовательности из elements
    """
    if n <= 0 :
        yield elements[:0]
    elif n == 1 :
        for i in range(len(elements)) :
            yield elements[i:i+1]
    else :
        for l in all_seq( n//2, elements ) :
            for r in all_seq( n - n//2, elements ) :
                yield l+r
                
def strategy_0( seq ) :
    return 0

def test_of_strategy( n, strategy_l, strategy_r ) :
    win_count = 0
    count = 0
    
    for l in all_seq( n ) :
        i_r = strategy_l(l)
        for r in all_seq( n ) :
            i_l = strategy_r(r)
            win_count += (l[i_l]==r[i_r])
            count += 1
            #if l[i_l]==r[i_r] and win_count < 100:
            #    print( f"{win_count}:{l}, {r}" )
    #print( f"{win_count}/{count}" )
    return win_count/count
        
def get_all_strategies( n ) :
    variants = list( all_seq( n ) )
    results = tuple( range(n) )
    for  r in all_seq( len(variants), results ) :
        yield dict(zip(variants, r))
    pass
 

def test_all_strategies( n ) :
    best_res = 0.5
    best_strategies = (None, None)
    for d_l in get_all_strategies( n ) :
        strategy_l = lambda s : d_l[s]
        for d_r in get_all_strategies( n ) :
            strategy_r = lambda s : d_r[s]
            t = test_of_strategy( n, strategy_l, strategy_r )
            if t > best_res :
                best_res = t
                best_strategies = (d_l, d_r)
                print( best_res, "-"*100 )
                print(d_l)
                if d_l != d_r :
                    print("- "*10)
                    print(d_r)
    return best_res, inverse_dictionary( best_strategies )

Проверим, сравнив с тем, что уже известно:
def strategy_0( seq ) :
    """
    тестовая стратегия, возвращает 0 для любой последовательности
    """
    return 0

test_of_strategy( 10, strategy_0, strategy_0 )
  "печатает (2.35s)" 
0.5
 


for d in get_all_strategies(2) :
    print( d )
  "печатает (6ms)" 
{(0, 0): 0, (0, 1): 0, (1, 0): 0, (1, 1): 0}
{(0, 0): 0, (0, 1): 0, (1, 0): 0, (1, 1): 1}
{(0, 0): 0, (0, 1): 0, (1, 0): 1, (1, 1): 0}
{(0, 0): 0, (0, 1): 0, (1, 0): 1, (1, 1): 1}
{(0, 0): 0, (0, 1): 1, (1, 0): 0, (1, 1): 0}
{(0, 0): 0, (0, 1): 1, (1, 0): 0, (1, 1): 1}
{(0, 0): 0, (0, 1): 1, (1, 0): 1, (1, 1): 0}
{(0, 0): 0, (0, 1): 1, (1, 0): 1, (1, 1): 1}
{(0, 0): 1, (0, 1): 0, (1, 0): 0, (1, 1): 0}
{(0, 0): 1, (0, 1): 0, (1, 0): 0, (1, 1): 1}
{(0, 0): 1, (0, 1): 0, (1, 0): 1, (1, 1): 0}
{(0, 0): 1, (0, 1): 0, (1, 0): 1, (1, 1): 1}
{(0, 0): 1, (0, 1): 1, (1, 0): 0, (1, 1): 0}
{(0, 0): 1, (0, 1): 1, (1, 0): 0, (1, 1): 1}
{(0, 0): 1, (0, 1): 1, (1, 0): 1, (1, 1): 0}
{(0, 0): 1, (0, 1): 1, (1, 0): 1, (1, 1): 1}
 


test_all_strategies( 2 )
  "печатает (15ms)" 
0.625 ----------------------------------------------------------------------------------------------------
{0: ((0, 0), (0, 1), (1, 1)), 1: ((1, 0),)}

(0.625, {0: ((0, 0), (0, 1), (1, 1)), 1: ((1, 0),)}, None)
 


test_all_strategies( 3 )
  "печатает (1h 30m 49s)" 
0.53125 ----------------------------------------------------------------------------------------------------
{(0, 0, 0): 0, (0, 0, 1): 0, (0, 1, 0): 0, (0, 1, 1): 0, (1, 0, 0): 0, (1, 0, 1): 0, (1, 1, 0): 1, (1, 1, 1): 0}
- - - - - - - - - - 
{(0, 0, 0): 0, (0, 0, 1): 0, (0, 1, 0): 0, (0, 1, 1): 0, (1, 0, 0): 0, (1, 0, 1): 2, (1, 1, 0): 0, (1, 1, 1): 0}
0.5625 ----------------------------------------------------------------------------------------------------
{(0, 0, 0): 0, (0, 0, 1): 0, (0, 1, 0): 0, (0, 1, 1): 0, (1, 0, 0): 0, (1, 0, 1): 0, (1, 1, 0): 1, (1, 1, 1): 0}
- - - - - - - - - - 
{(0, 0, 0): 0, (0, 0, 1): 0, (0, 1, 0): 0, (0, 1, 1): 0, (1, 0, 0): 2, (1, 0, 1): 2, (1, 1, 0): 0, (1, 1, 1): 0}
0.59375 ----------------------------------------------------------------------------------------------------
{(0, 0, 0): 0, (0, 0, 1): 0, (0, 1, 0): 0, (0, 1, 1): 0, (1, 0, 0): 0, (1, 0, 1): 1, (1, 1, 0): 2, (1, 1, 1): 0}
- - - - - - - - - - 
{(0, 0, 0): 0, (0, 0, 1): 0, (0, 1, 0): 0, (0, 1, 1): 0, (1, 0, 0): 1, (1, 0, 1): 1, (1, 1, 0): 2, (1, 1, 1): 0}
0.625 ----------------------------------------------------------------------------------------------------
{(0, 0, 0): 0, (0, 0, 1): 0, (0, 1, 0): 0, (0, 1, 1): 0, (1, 0, 0): 1, (1, 0, 1): 0, (1, 1, 0): 1, (1, 1, 1): 0}
- - - - - - - - - - 
{(0, 0, 0): 0, (0, 0, 1): 0, (0, 1, 0): 0, (0, 1, 1): 0, (1, 0, 0): 2, (1, 0, 1): 2, (1, 1, 0): 0, (1, 1, 1): 0}
0.65625 ----------------------------------------------------------------------------------------------------
{(0, 0, 0): 0, (0, 0, 1): 0, (0, 1, 0): 0, (0, 1, 1): 0, (1, 0, 0): 1, (1, 0, 1): 1, (1, 1, 0): 2, (1, 1, 1): 0}
0.6875 ----------------------------------------------------------------------------------------------------
{(0, 0, 0): 0, (0, 0, 1): 0, (0, 1, 0): 1, (0, 1, 1): 0, (1, 0, 0): 2, (1, 0, 1): 2, (1, 1, 0): 1, (1, 1, 1): 0}

(0.6875,
 {0: ((0, 0, 0), (0, 0, 1), (0, 1, 1), (1, 1, 1)),
  1: ((0, 1, 0), (1, 1, 0)),
  2: ((1, 0, 0), (1, 0, 1))},
 None)
 


test_all_sym_strategies( 3 )
  "печатает ( 902ms)" 
0.53125 ----------------------------------------------------------------------------------------------------
{(0, 0, 0): 0, (0, 0, 1): 0, (0, 1, 0): 0, (0, 1, 1): 0, (1, 0, 0): 0, (1, 0, 1): 0, (1, 1, 0): 2, (1, 1, 1): 0}
0.5625 ----------------------------------------------------------------------------------------------------
{(0, 0, 0): 0, (0, 0, 1): 0, (0, 1, 0): 0, (0, 1, 1): 0, (1, 0, 0): 0, (1, 0, 1): 1, (1, 1, 0): 2, (1, 1, 1): 0}
0.625 ----------------------------------------------------------------------------------------------------
{(0, 0, 0): 0, (0, 0, 1): 0, (0, 1, 0): 0, (0, 1, 1): 0, (1, 0, 0): 1, (1, 0, 1): 1, (1, 1, 0): 0, (1, 1, 1): 0}
0.65625 ----------------------------------------------------------------------------------------------------
{(0, 0, 0): 0, (0, 0, 1): 0, (0, 1, 0): 0, (0, 1, 1): 0, (1, 0, 0): 1, (1, 0, 1): 1, (1, 1, 0): 2, (1, 1, 1): 0}
0.6875 ----------------------------------------------------------------------------------------------------
{(0, 0, 0): 0, (0, 0, 1): 0, (0, 1, 0): 1, (0, 1, 1): 0, (1, 0, 0): 2, (1, 0, 1): 2, (1, 1, 0): 1, (1, 1, 1): 0}

(0.6875,
 {0: ((0, 0, 0), (0, 0, 1), (0, 1, 1), (1, 1, 1)),
  1: ((0, 1, 0), (1, 1, 0)),
  2: ((1, 0, 0), (1, 0, 1))})
 


test_all_sym_strategies( 3 )
  "печатает (пока не сошлось...)" 
0.5078125 ----------------------------------------------------------------------------------------------------
{(0, 0, 0, 0): 0, (0, 0, 0, 1): 0, (0, 0, 1, 0): 0, (0, 0, 1, 1): 0, (0, 1, 0, 0): 0, (0, 1, 0, 1): 0, (0, 1, 1, 0): 0, (0, 1, 1, 1): 0, (1, 0, 0, 0): 0, (1, 0, 0, 1): 0, (1, 0, 1, 0): 0, (1, 0, 1, 1): 0, (1, 1, 0, 0): 0, (1, 1, 0, 1): 0, (1, 1, 1, 0): 3, (1, 1, 1, 1): 0}
0.515625 ----------------------------------------------------------------------------------------------------
{(0, 0, 0, 0): 0, (0, 0, 0, 1): 0, (0, 0, 1, 0): 0, (0, 0, 1, 1): 0, (0, 1, 0, 0): 0, (0, 1, 0, 1): 0, (0, 1, 1, 0): 0, (0, 1, 1, 1): 0, (1, 0, 0, 0): 0, (1, 0, 0, 1): 0, (1, 0, 1, 0): 0, (1, 0, 1, 1): 0, (1, 1, 0, 0): 0, (1, 1, 0, 1): 2, (1, 1, 1, 0): 3, (1, 1, 1, 1): 0}
0.53125 ----------------------------------------------------------------------------------------------------
{(0, 0, 0, 0): 0, (0, 0, 0, 1): 0, (0, 0, 1, 0): 0, (0, 0, 1, 1): 0, (0, 1, 0, 0): 0, (0, 1, 0, 1): 0, (0, 1, 1, 0): 0, (0, 1, 1, 1): 0, (1, 0, 0, 0): 0, (1, 0, 0, 1): 0, (1, 0, 1, 0): 0, (1, 0, 1, 1): 0, (1, 1, 0, 0): 2, (1, 1, 0, 1): 2, (1, 1, 1, 0): 0, (1, 1, 1, 1): 0}
0.5390625 ----------------------------------------------------------------------------------------------------
{(0, 0, 0, 0): 0, (0, 0, 0, 1): 0, (0, 0, 1, 0): 0, (0, 0, 1, 1): 0, (0, 1, 0, 0): 0, (0, 1, 0, 1): 0, (0, 1, 1, 0): 0, (0, 1, 1, 1): 0, (1, 0, 0, 0): 0, (1, 0, 0, 1): 0, (1, 0, 1, 0): 0, (1, 0, 1, 1): 0, (1, 1, 0, 0): 2, (1, 1, 0, 1): 2, (1, 1, 1, 0): 3, (1, 1, 1, 1): 0}
0.546875 ----------------------------------------------------------------------------------------------------
{(0, 0, 0, 0): 0, (0, 0, 0, 1): 0, (0, 0, 1, 0): 0, (0, 0, 1, 1): 0, (0, 1, 0, 0): 0, (0, 1, 0, 1): 0, (0, 1, 1, 0): 0, (0, 1, 1, 1): 0, (1, 0, 0, 0): 0, (1, 0, 0, 1): 0, (1, 0, 1, 0): 0, (1, 0, 1, 1): 1, (1, 1, 0, 0): 2, (1, 1, 0, 1): 2, (1, 1, 1, 0): 3, (1, 1, 1, 1): 0}
0.5625 ----------------------------------------------------------------------------------------------------
{(0, 0, 0, 0): 0, (0, 0, 0, 1): 0, (0, 0, 1, 0): 0, (0, 0, 1, 1): 0, (0, 1, 0, 0): 0, (0, 1, 0, 1): 0, (0, 1, 1, 0): 0, (0, 1, 1, 1): 0, (1, 0, 0, 0): 0, (1, 0, 0, 1): 0, (1, 0, 1, 0): 1, (1, 0, 1, 1): 1, (1, 1, 0, 0): 2, (1, 1, 0, 1): 2, (1, 1, 1, 0): 0, (1, 1, 1, 1): 0}
0.5703125 ----------------------------------------------------------------------------------------------------
{(0, 0, 0, 0): 0, (0, 0, 0, 1): 0, (0, 0, 1, 0): 0, (0, 0, 1, 1): 0, (0, 1, 0, 0): 0, (0, 1, 0, 1): 0, (0, 1, 1, 0): 0, (0, 1, 1, 1): 0, (1, 0, 0, 0): 0, (1, 0, 0, 1): 0, (1, 0, 1, 0): 1, (1, 0, 1, 1): 1, (1, 1, 0, 0): 2, (1, 1, 0, 1): 2, (1, 1, 1, 0): 3, (1, 1, 1, 1): 0}
0.578125 ----------------------------------------------------------------------------------------------------
{(0, 0, 0, 0): 0, (0, 0, 0, 1): 0, (0, 0, 1, 0): 0, (0, 0, 1, 1): 0, (0, 1, 0, 0): 0, (0, 1, 0, 1): 0, (0, 1, 1, 0): 0, (0, 1, 1, 1): 0, (1, 0, 0, 0): 0, (1, 0, 0, 1): 0, (1, 0, 1, 0): 2, (1, 0, 1, 1): 1, (1, 1, 0, 0): 3, (1, 1, 0, 1): 3, (1, 1, 1, 0): 2, (1, 1, 1, 1): 0}
0.5859375 ----------------------------------------------------------------------------------------------------
{(0, 0, 0, 0): 0, (0, 0, 0, 1): 0, (0, 0, 1, 0): 0, (0, 0, 1, 1): 0, (0, 1, 0, 0): 0, (0, 1, 0, 1): 0, (0, 1, 1, 0): 0, (0, 1, 1, 1): 0, (1, 0, 0, 0): 0, (1, 0, 0, 1): 0, (1, 0, 1, 0): 3, (1, 0, 1, 1): 1, (1, 1, 0, 0): 3, (1, 1, 0, 1): 2, (1, 1, 1, 0): 3, (1, 1, 1, 1): 0}
0.6015625 ----------------------------------------------------------------------------------------------------
{(0, 0, 0, 0): 0, (0, 0, 0, 1): 0, (0, 0, 1, 0): 0, (0, 0, 1, 1): 0, (0, 1, 0, 0): 0, (0, 1, 0, 1): 0, (0, 1, 1, 0): 0, (0, 1, 1, 1): 0, (1, 0, 0, 0): 0, (1, 0, 0, 1): 1, (1, 0, 1, 0): 1, (1, 0, 1, 1): 1, (1, 1, 0, 0): 2, (1, 1, 0, 1): 2, (1, 1, 1, 0): 0, (1, 1, 1, 1): 0}
0.609375 ----------------------------------------------------------------------------------------------------
{(0, 0, 0, 0): 0, (0, 0, 0, 1): 0, (0, 0, 1, 0): 0, (0, 0, 1, 1): 0, (0, 1, 0, 0): 0, (0, 1, 0, 1): 0, (0, 1, 1, 0): 0, (0, 1, 1, 1): 0, (1, 0, 0, 0): 0, (1, 0, 0, 1): 1, (1, 0, 1, 0): 1, (1, 0, 1, 1): 1, (1, 1, 0, 0): 2, (1, 1, 0, 1): 2, (1, 1, 1, 0): 3, (1, 1, 1, 1): 0}
0.6171875 ----------------------------------------------------------------------------------------------------
{(0, 0, 0, 0): 0, (0, 0, 0, 1): 0, (0, 0, 1, 0): 0, (0, 0, 1, 1): 0, (0, 1, 0, 0): 0, (0, 1, 0, 1): 0, (0, 1, 1, 0): 0, (0, 1, 1, 1): 0, (1, 0, 0, 0): 0, (1, 0, 0, 1): 1, (1, 0, 1, 0): 2, (1, 0, 1, 1): 1, (1, 1, 0, 0): 3, (1, 1, 0, 1): 3, (1, 1, 1, 0): 2, (1, 1, 1, 1): 0}
0.625 ----------------------------------------------------------------------------------------------------
{(0, 0, 0, 0): 0, (0, 0, 0, 1): 0, (0, 0, 1, 0): 0, (0, 0, 1, 1): 0, (0, 1, 0, 0): 0, (0, 1, 0, 1): 0, (0, 1, 1, 0): 0, (0, 1, 1, 1): 0, (1, 0, 0, 0): 1, (1, 0, 0, 1): 0, (1, 0, 1, 0): 3, (1, 0, 1, 1): 1, (1, 1, 0, 0): 3, (1, 1, 0, 1): 2, (1, 1, 1, 0): 3, (1, 1, 1, 1): 0}
0.6328125 ----------------------------------------------------------------------------------------------------
{(0, 0, 0, 0): 0, (0, 0, 0, 1): 0, (0, 0, 1, 0): 0, (0, 0, 1, 1): 0, (0, 1, 0, 0): 0, (0, 1, 0, 1): 0, (0, 1, 1, 0): 0, (0, 1, 1, 1): 0, (1, 0, 0, 0): 1, (1, 0, 0, 1): 1, (1, 0, 1, 0): 1, (1, 0, 1, 1): 1, (1, 1, 0, 0): 0, (1, 1, 0, 1): 0, (1, 1, 1, 0): 3, (1, 1, 1, 1): 0}
0.640625 ----------------------------------------------------------------------------------------------------
{(0, 0, 0, 0): 0, (0, 0, 0, 1): 0, (0, 0, 1, 0): 0, (0, 0, 1, 1): 0, (0, 1, 0, 0): 0, (0, 1, 0, 1): 0, (0, 1, 1, 0): 0, (0, 1, 1, 1): 0, (1, 0, 0, 0): 1, (1, 0, 0, 1): 1, (1, 0, 1, 0): 1, (1, 0, 1, 1): 1, (1, 1, 0, 0): 0, (1, 1, 0, 1): 2, (1, 1, 1, 0): 3, (1, 1, 1, 1): 0}
0.65625 ----------------------------------------------------------------------------------------------------
{(0, 0, 0, 0): 0, (0, 0, 0, 1): 0, (0, 0, 1, 0): 0, (0, 0, 1, 1): 0, (0, 1, 0, 0): 0, (0, 1, 0, 1): 0, (0, 1, 1, 0): 0, (0, 1, 1, 1): 0, (1, 0, 0, 0): 1, (1, 0, 0, 1): 1, (1, 0, 1, 0): 1, (1, 0, 1, 1): 1, (1, 1, 0, 0): 2, (1, 1, 0, 1): 2, (1, 1, 1, 0): 0, (1, 1, 1, 1): 0}
0.6640625 ----------------------------------------------------------------------------------------------------
{(0, 0, 0, 0): 0, (0, 0, 0, 1): 0, (0, 0, 1, 0): 0, (0, 0, 1, 1): 0, (0, 1, 0, 0): 0, (0, 1, 0, 1): 0, (0, 1, 1, 0): 0, (0, 1, 1, 1): 0, (1, 0, 0, 0): 1, (1, 0, 0, 1): 1, (1, 0, 1, 0): 1, (1, 0, 1, 1): 1, (1, 1, 0, 0): 2, (1, 1, 0, 1): 2, (1, 1, 1, 0): 3, (1, 1, 1, 1): 0}
0.671875 ----------------------------------------------------------------------------------------------------
{(0, 0, 0, 0): 0, (0, 0, 0, 1): 0, (0, 0, 1, 0): 0, (0, 0, 1, 1): 0, (0, 1, 0, 0): 0, (0, 1, 0, 1): 0, (0, 1, 1, 0): 0, (0, 1, 1, 1): 0, (1, 0, 0, 0): 1, (1, 0, 0, 1): 1, (1, 0, 1, 0): 2, (1, 0, 1, 1): 1, (1, 1, 0, 0): 3, (1, 1, 0, 1): 3, (1, 1, 1, 0): 2, (1, 1, 1, 1): 0}
0.6796875 ----------------------------------------------------------------------------------------------------
{(0, 0, 0, 0): 0, (0, 0, 0, 1): 0, (0, 0, 1, 0): 0, (0, 0, 1, 1): 0, (0, 1, 0, 0): 1, (0, 1, 0, 1): 0, (0, 1, 1, 0): 0, (0, 1, 1, 1): 0, (1, 0, 0, 0): 2, (1, 0, 0, 1): 2, (1, 0, 1, 0): 3, (1, 0, 1, 1): 2, (1, 1, 0, 0): 1, (1, 1, 0, 1): 1, (1, 1, 1, 0): 3, (1, 1, 1, 1): 0}
0.6875 ----------------------------------------------------------------------------------------------------
{(0, 0, 0, 0): 0, (0, 0, 0, 1): 0, (0, 0, 1, 0): 0, (0, 0, 1, 1): 0, (0, 1, 0, 0): 1, (0, 1, 0, 1): 0, (0, 1, 1, 0): 1, (0, 1, 1, 1): 0, (1, 0, 0, 0): 3, (1, 0, 0, 1): 2, (1, 0, 1, 0): 3, (1, 0, 1, 1): 3, (1, 1, 0, 0): 1, (1, 1, 0, 1): 2, (1, 1, 1, 0): 1, (1, 1, 1, 1): 0}
0.6953125 ----------------------------------------------------------------------------------------------------
{(0, 0, 0, 0): 0, (0, 0, 0, 1): 0, (0, 0, 1, 0): 0, (0, 0, 1, 1): 0, (0, 1, 0, 0): 1, (0, 1, 0, 1): 0, (0, 1, 1, 0): 1, (0, 1, 1, 1): 0, (1, 0, 0, 0): 3, (1, 0, 0, 1): 3, (1, 0, 1, 0): 3, (1, 0, 1, 1): 3, (1, 1, 0, 0): 1, (1, 1, 0, 1): 2, (1, 1, 1, 0): 1, (1, 1, 1, 1): 0}

Пока всё сходится, правда последние две я нашёл уже этим кодом...
Но ту, которая даёт 11/16 потом независимо проверял


  "пока что нашлась симметричная стратегия длины 4 с результатом 89/128 (0.6953125)"
Для удобства чтения я записал не отображение последовательностей на индексы, а отображение индексов на набор последовательностей, которому они соответствуют
{0: ( 
     (0, 0, 0, 0),
     (0, 0, 0, 1),
     (0, 0, 1, 0),
     (0, 0, 1, 1),
     (0, 1, 0, 1),
     (0, 1, 1, 1),
     (1, 1, 1, 1)
    ),
 1: ((0, 1, 0, 0), (0, 1, 1, 0), (1, 1, 0, 0), (1, 1, 1, 0)),
 2: ((1, 1, 0, 1),),
 3: ((1, 0, 0, 0), (1, 0, 0, 1), (1, 0, 1, 0), (1, 0, 1, 1))}


На мой взгляд, можно устроить тут соревнование на лучшее спасение принцесс. Наверное было бы удобно, если бы TC вёл в стартовом сообщении лог, кто чего достиг.
Например, в виде тэга cut с заголовком в котором написана вероятность выигрыша, длина стратегии и кем и когда получена, а внутри описание самой стратегии
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Отредактировано 05.03.2020 9:16 Erop . Предыдущая версия .
Re[2]: Спасти принцесс
От: Nuzhny Россия https://github.com/Nuzhny007
Дата: 05.03.20 11:45
Оценка: 26 (3)
Здравствуйте, Erop, Вы писали:

E>На мой взгляд, можно устроить тут соревнование на лучшее спасение принцесс. Наверное было бы удобно, если бы TC вёл в стартовом сообщении лог, кто чего достиг.
E>Например, в виде тэга cut с заголовком в котором написана вероятность выигрыша, длина стратегии и кем и когда получена, а внутри описание самой стратегии

Кстати, эта задача попалась тут:
  видео

О ней потом поговорили тут:
  видео
Re[3]: Спасти принцесс
От: Erop Россия  
Дата: 05.03.20 12:39
Оценка:
Здравствуйте, Nuzhny, Вы писали:

N>Кстати, эта задача попалась тут:
N>
  видео
N>

N>О ней потом поговорили тут:
N>
  видео
N>


Сейчас смотреть некогда. Они её решили? В смысле, нашли оптимальную стратегию?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[4]: Спасти принцесс
От: Nuzhny Россия https://github.com/Nuzhny007
Дата: 05.03.20 12:47
Оценка:
Здравствуйте, Erop, Вы писали:

E>Сейчас смотреть некогда. Они её решили? В смысле, нашли оптимальную стратегию?

В первом ролике был сам конкурс и задача эта давалась на 5 минут — никаких идей. Во втором ролике шёл обзор стратегий, насколько я помню, самую верную не нашли, а просто рассмотрели несколько возможных.
Re[5]: Спасти принцесс
От: Erop Россия  
Дата: 05.03.20 13:21
Оценка:
Здравствуйте, Nuzhny, Вы писали:

N>В первом ролике был сам конкурс и задача эта давалась на 5 минут — никаких идей.
5 минту -- как-то мало...

N>Во втором ролике шёл обзор стратегий, насколько я помню, самую верную не нашли, а просто рассмотрели несколько возможных.
Не помнишь, 0.7 хотя бы достигли?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[6]: Спасти принцесс
От: Nuzhny Россия https://github.com/Nuzhny007
Дата: 05.03.20 13:54
Оценка: :)
Здравствуйте, Erop, Вы писали:

N>>Во втором ролике шёл обзор стратегий, насколько я помню, самую верную не нашли, а просто рассмотрели несколько возможных.
E>Не помнишь, 0.7 хотя бы достигли?

В самом видео только 0.6(6) и упоминание якобы существующего решения больше 70%. Твоё лучше
Re[7]: Спасти принцесс
От: Erop Россия  
Дата: 06.03.20 07:58
Оценка:
Здравствуйте, Nuzhny, Вы писали:

N>В самом видео только 0.6(6) и упоминание якобы существующего решения больше 70%. Твоё лучше

Ну 2/3 -- это стратегия "называть позицию первой решки" даёт.
А вот .7 -- интересный порог. Я тут что-то перебором с оценкой на Монте-Карло и дифф. эволюцией параметров стратегии пытался искать, пока превзойти эту границу не удалось, хотя удаётся близко приблизится. Но при этом у меня пока не придумалось хорошей параметризации стратегий
Но у меня и личного и машинного времени на эту фигню не так уж и много.
Просто и правда интересно, и, я подозреваю, для теории игр, небезинтересно, но если кто-то что-то уже придумал, то мне проще было бы почитать, чем греть атмосферу переборными алгоритмами

С длиной последовательности очень быстро растёт перебор
Число последовательностей -- это 2**N, число стратегий -- это N**(2**N), так что упс...

Есть несколько гипотез. Например, стратегия в форме набор подстрок последовательностей с указанной позицией. Типа если такая подстрока в такой-то позиции есть, то даём такой-то индекс. Ну и упорядоченный список таких правил. Или "деревянная" стратегия. То есть мы имеем такой алгоритм. На вход получаем последовательность, несколько бросков пропускаем, потом ветвимся на орёл-решка. Получаем что-то вроде структуры (0, (0,), (0, (2, (1,), (3,)), (0, (4,), (2,)))), которая соответствует алгоритму:
def tree_strategy( l ) :
    i = 0                    # (0, 
    if l[i] == 0  :          
        return 0             #    (0,),
    else: 
        i += 1               #    (0, 
        if l[i] == 0 :
            i += 1 + 2       #     (2, 
            if l[i] == 0 :   
                return 1     #        (1,), 
            else :
                return 3     #        (3,)
        else :               #     ), 
            i += 1           #     (0, 
            if l[i] == 0 :
                return 4     #        (4,), 
            else :
                return 2     #        (2,)
                             #     )
                             # )

Конечно это для дифф. эволюции не годится, но разные другие генетические алгоритмы с таким могут работать.

Для дифф. эволюции же надо описание стратегии, в виде честных float. Например, можно задавать стратегию для последовательностей длины N в виде N+1 числа, складывать те из первых N, кому соответствуют орлы, прибавлять последнее, от всего брать целую часть и остаток от деления на N
Только многопараметрическая оптимизация фигово работает и так сильно не все стратегии можно получить.
Ещё есть вариант — кодировать решку -1, а орла 1, потом для каждой позиции выбираем по случайному числу, и считаем, что это полином.
После чего выбираем N (можно и меньше, K, например) чисел, подставляем их в этот полином, считаем суммы значений, и дальше снова целая часть и остаток от деления.
А вот этот набор из K чисел уже подбираем.

Но всё это как-то безыдейно
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[8]: Спасти принцесс
От: Nuzhny Россия https://github.com/Nuzhny007
Дата: 06.03.20 08:40
Оценка: +1
Здравствуйте, Erop, Вы писали:

E>Но всё это как-то безыдейно

Тоже нет времени на это всё. В комментариях есть результаты решений:

69.5% (178/256) при четырёх бросках:
https://imgur.com/xgOcQ5R
Если увеличить до 6 бросков, получается 69.9% (1433/2048).

Так что...
Re[9]: Спасти принцесс
От: RiNSpy  
Дата: 06.03.20 23:36
Оценка:
Здравствуйте, Nuzhny, Вы писали:

N>Если увеличить до 6 бросков, получается 69.9% (1433/2048).

Я что-то не могу понять, а вникать лень.

— каждый бросок монетки дает случайный исход 0 или 1 с одинаковой вероятностью 1/2
— Чита и Гита дают ответы независимо друг от друга и не имеют никакой дополнительной информации

Как при этих условиях может быть вероятность выше 0.5? В чём суть решения?
Re[10]: Спасти принцесс
От: Буравчик Россия  
Дата: 07.03.20 10:31
Оценка: 8 (1) +1
Здравствуйте, RiNSpy, Вы писали:

RNS>Я что-то не могу понять, а вникать лень.

Плохо, что лень.

RNS>— каждый бросок монетки дает случайный исход 0 или 1 с одинаковой вероятностью 1/2
RNS>— Чита и Гита дают ответы независимо друг от друга и не имеют никакой дополнительной информации
RNS>Как при этих условиях может быть вероятность выше 0.5? В чём суть решения?

Это кажется невозможным, но решения "выше 0.5" существуют. Посмотри видео.

Вот, например, решение когда принцесса называет номер, в котором у нее выпала первая решка.
Обозначим O — орел, Р — решка, Х — неизвестно (равновероятно орел или решка)

1. Будут случаи, когда указанные принцессами места совпали. Тогда обе принцессы указывают на решку (чужую). Вероятность выигрыша в этому случае 1.

ООООPХХХХХХХХХ...
    ^   
    V   
OOOOPXXXXXXXXX...


2. И будут случаи, когда места не совпали. Тогда одна принцесса указывает на орла (чужого), а вторая принцесса указывает не что-то неизвестное (орел или решка). Если это неизвестное окажется орлом, то выиграли, если окажется решкой, то проиграли. Вероятность выигрыша 0.5

ООООООOOРХХХХХ...
    ^   |
    |   V
OOOOPXXXXXXXXX...


Т.к. первый случай все же будет иногда встречаться, то общая вероятность выигрыша более 0.5

P.S. Я решить задачу самостоятельно не смог. И тоже считал, что это невозможно
Best regards, Буравчик
Re[11]: Спасти принцесс
От: Erop Россия  
Дата: 11.03.20 17:51
Оценка:
Здравствуйте, Буравчик, Вы писали:

Б>Т.к. первый случай все же будет иногда встречаться, то общая вероятность выигрыша более 0.5

Есть ещё и второй способ! Можно сделать так, что разные ответы будут не равновероятны, и при этом в самом вероятном случае вероятность победы будет больше 0.5, за счёт каких-то других, менее вероятных. В результате в сумме получим >.5

Б>P.S. Я решить задачу самостоятельно не смог. И тоже считал, что это невозможно
Я смог, но не до конца. Там выше по дереву написал всё, что пока придумалось...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.