Работа устройства без противодействия человека

Модель, имитирующая работу устройства. Работа устройства без противодействия имитировалась на ЦВМ. На модели имитировалась игра устройства с противником, в которой оно работает по вышеприведенному алгоритму, а выбор указания противником равновероятен для каждого соседнего узла на каждом шаге.

Эту модель можно интерпретировать как блуждание без противодействия, когда действия путника таковы: в каждом узле он бросает жребий и, в зависимости от номера хода, либо следует выпавшему указанию, либо выбирает противоположный узел. Поскольку отношение противоположности не является взаимно однозначным, то употребление подобной стратегии в принципе должно изменить среднюю длину блуждания по сравнению с «обычным» блужданием, когда путник не пользуется отношением противоположности. В нашем случае отношение противоположности не в пользу путника. Руководствуясь подобным алгоритмом обработки жребия, путник увеличивает среднюю длительность своего пребывания в лабиринте по сравнению со случайным блужданием. Среднее число ходов оказалось равным 27, а при случайном блуждании — 25.

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

случайном блуждании. Это вызвано тем, что для случайного блуждания легко построить интересующую нас функцию распределения. Построение функции распределения при случайном блуждании.

Пусть Ро(т) — вероятность того, что партия окончится за число ходов, не превышающее т' В нашем случае Ро(т) можно определить исходя из того, что.процесс 'блуждания представим в виде цепи Маркова (рис. 41).

Первому элементу этой цепи соответствует центральный узел— 13 (см. рис. 40); второму элементу — уровень, состоящий из узлов 7, 12, 14, 16, 17; третьему элементу соответствует уровень, состоящий из узлов 6, 8, 22, 15, 18; четвертому — уровень из узлов 3, 10, 11, 21, 23; пятому — уровень из узлов 2, 4, 19, 20, 25 и шестому — точки поглощения /, 5, 9, 24, 26. Данной цепи Маркова соответствует матрица А.

В силу соотношений, известных из теории цепей Маркова, вероятность того, что точка будет поглощена за число ходов, не превышающее 30, равна элементу а₁₆ матрицы A^m (т — показатель степени, в которую следует возводить матрицу).