flaass: задачка о консенсусе

(Добавить комментарий)

	(Анонимно) 2005-04-20 12:14 (ссылка)
	a roboty ravnopravny? Veselo budet, esli dlja raznyh robotov dopustimy raznye algoritmy :) (Ответить) (Ветвь дискуссии)

	flaass@lj 2005-04-20 12:25 (ссылка)
	Полностью равноправны. Алгоритм должен быть абсолютно одинаков у всех троих (в т.ч. они не имеют никаких номеров, от которых могло бы зависеть поведение). (Ответить) (Уровень выше)

garvej@lj
2005-04-20 13:27 (ссылка)

Робот знает свои карты и помнит, какие карты передавались ему справа в предыдущие ходы. Что делать, он вычисляет из этого по некоторому детерминированному алгоритму

А те, что сам передавал налево - тоже, конечно, помнит? В алгоритме эту информацию можно использовать?

И ещё вопрос. Робот знает, что все его коллеги действуют по тому же алгоритму, что и он? Может ли эта метаинформация использоваться в алгоритме? Кажется, это может быть существенно вот в какой ситуации. Допустим робот первым ходом передал некоторую карту налево. И через один ход она вернулась к нему справа. Значит оба его коллеги вторым и третьим ходом передавали эту карту. В принипе, это может дать ему некую информацию о распределении карт у двух других. Может, конечно, всё это фигня, и на это не стоит обращать внимания - надо подумать. Но вот из вредности спрашиваю :)

(Ответить) (Ветвь дискуссии)

flaass@lj
2005-04-21 09:49 (ссылка)

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

(Ответить) (Уровень выше)

	flaass@lj 2005-04-21 09:51 (ссылка)
	Насчет возвращения карты: ну все же короли пиковые! Одинаковые. Может, вернулся совсем не он. (Ответить) (Уровень выше) (Ветвь дискуссии)

	garvej@lj 2005-04-21 10:07 (ссылка)
	Да, согласен :) Про пиковые это я невнимательно прочитал. (Ответить) (Уровень выше)

dimrub@lj
2005-04-21 05:46 (ссылка)

Ну, про четырех - очевидно: допустим, что в начале у каждого все карты разные. Тогда, поскольку алгоритм у всех одинаковый, после первого хода каждый передаст вправо одну и ту же карту - и состояние останется, как и до этого хода.

По поводу 3-х есть идея, буду думать :)

(Ответить) (Ветвь дискуссии)

	garvej@lj 2005-04-21 10:10 (ссылка)
	С четырьмя хорошо получилось! Интересно, а что будет для пяти? (Ответить) (Уровень выше)

	rgu@lj 2005-04-21 10:11 (ссылка)
	черт, верно! а я сижу и думаю, какого рожна про 4-х легче? спасибо. (Ответить) (Уровень выше)

	rgu@lj 2005-04-21 10:14 (ссылка)
	Дмитрий, а алгоритм подразумевает "пас", в смысле ничего не передавать? Тогда, переданная ему карта автоматически передаётся ещё левее. (Ответить) (Ветвь дискуссии)

	flaass@lj 2005-04-21 12:08 (ссылка)
	Нет, "паса" нету. Что-то обязательно надо отдать. (Ответить) (Уровень выше)

opegs@lj
2005-04-21 13:44 (ссылка)

Если игроки заранее знают, кто что собирает, то надо
привести к ситуации, когда у каждого 2 своих и 2 разных чужих.
Т.е. тот, кто собирает А (сосед кому он передает - В) играет так:
ААВС - отдает С, ААВВ - отдает В, АААВ - отдает В, АААА - скидывает,
если это получено не при раздаче, если при раздаче - отдает А.
Иначе: АВВС(АВВВ) - В, АВСС(АССС) - С, АААС - А. Примерно так?

(Ответить) (Ветвь дискуссии)

opegs@lj
2005-04-22 13:26 (ссылка)

P.S.
Договор (кто что собирает) - 2 хода, на третьем, еще получаем свою, с учетом выше сказанного - 7 ходов включая сброс. То что выше написано, не обязательно проходит через комбинацию ААВС, она упомянута из педагогических соображений.

(Ответить) (Уровень выше)

dimrub@lj
2005-04-21 17:18 (ссылка)

Есть некий алгоритм, но не уверен, что он оптимальный. За 4 шага каждый может узнать, что у всех остальных на руках: каждый просто передает последовательно все карты, какие у него есть. Таким образом, через 4 хода карты, которые были у 1-го, будут у 2-го, те, что были у 2-го будут у 3-го, а те, что были у 3-го - у 1-го. 1-й знает, что у него было в начале, значит он знает, что теперь у 2-го, плюс он знает, что есть у него, и путем вычитания может понять, что у 3-го. Далее, в принципе, зная, где они находятся на схеме переходов, они могут, кажется, за 5 ходов дойти до правильного состояния. Итого 9 ходов. Буду думать дальше.

(Ответить) (Ветвь дискуссии)

dimrub@lj
2005-04-21 17:36 (ссылка)

Понял, как установить, в каком мы положении, за 3 хода (вместо четырех): далее таблица того, что мы передаем в зависимости от того, что у нас есть:

AAAA - A, A, A
AAAB - A, A, B
AABB - A, B, B
AABC - A, B, C

В третьем случае выбор между A и B производится либо случайным образом, либо лексиграфической сортировкой. Очевидно, что тот, кому мы передаем, в состоянии добавить первое A и понять, с чем мы начали игру.

(Ответить) (Уровень выше) (Ветвь дискуссии)

garvej@lj
2005-04-22 11:54 (ссылка)

Если знать полный расклад карт, то до правильного состояния можно дойти за 3 хода. То есть всего получается 6 ходов.

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

Всего есть 120 вариантов расклада карт. (Если учесть симметрию относительно обхода по часовой стрелке, то 40).
3 хода достаточно, чтобы дойти до одного из правильных состояний.
Для всех 120 раскладов получается такая картина. Минимальное количество ходов и кол-во раскладов:
0 - 6
1 - 6
2 - 48
3 - 60
Посчитал на компе. Вариантов немного, в общем-то можно и руками перебрать, а если исхитриться, то и кратко записать.

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

(Ответить) (Уровень выше) (Ветвь дискуссии)

dimrub@lj
2005-04-22 16:16 (ссылка)

Если знать полный расклад карт, то до правильного состояния можно дойти за 3 хода. То есть всего получается 6 ходов.

На самом деле - 7, так как последний ход - это положить карты на стол. Итого - коллективными усилиями мы задачу решили :)

Всего есть 120 вариантов расклада карт. (Если учесть симметрию относительно обхода по часовой стрелке, то 40).

Если учесть еще и симметрию относительно видов карт, которых три, то раскладов остается еще меньше (хотя первоначальное число - 120 - мне кажется неверным, потому как 40 на 3 не делится). Я насчитал 12, хотя не уверен, что это верно (но особо и не старался :)).

Посчитал на компе.

Круто! Я тоже хотел было, но поленился, намалевал что-то на бумажке.

(Ответить) (Уровень выше) (Ветвь дискуссии)

garvej@lj
2005-04-24 22:47 (ссылка)

120 - мне кажется неверным, потому как 40 на 3 не делится

Здесь противоречия нет.
Дальше нельзя просто так делить 40 на 3, дело обстоит сложнее.
На подсчеты лучше всего посмотреть с точки зрения действия групп на множестве. Множество - 120 различных вариантов расклада. "Варианты с учётом симметрии" - называются орбитами группы преобразований, действующей на этом множестве. У меня использовалась циклическая группа порядка 3. Для неё орбита может состоять из одного или трёх элементов. Слова "у всех не может быть одинаковый расклад" указывают на то, что орбита не может иметь длину 1. Следовательно получается, что все орбиты имеют длину 3, поэтому для подсчёта их количества мы можем просто 120 разделить на 3.

Но если взять большую группу (учесть симметрию видов карт), то свойство, что орбиты имеют равную длину, уже не будет выполняться. Например, для расклада {{4,0,0},{0,4,0},{0,0,4}} орбита имеет длину 6 (это все "правильные состояния"). А расклад {{4,0,0},{0,2,2},{0,2,2}} имеет орбиту длины 12.
Поэтому подсчитывать орбиты сложнее. Я тоже хотел сначала использовать большую степень симметрии, но надо чтобы решение было инвариантно относительно этой симметрии. Относительно сдвига по часовой стрелке - очевидно, инвариантно. Относительно большей группы, с учетом симметрии видов карт, вроде бы уже нет, но детально не проверял.

Решили, но вопрос об оптимальности остался. И скорее всего так и останется ;) - фиг докажешь.
Оказывается, задача неразрешима для любого чётного числа роботов. А для нечётного вроде бы нет препятствий, и скорее всего подойдёт обобщение алгоритма: сначала узнаём расклад, а потом собираем.

(Ответить) (Уровень выше)

	поправка garvej@lj 2005-04-24 22:59 (ссылка)
	Расклад {{4,0,0},{0,2,2},{0,2,2}} имеет орбиту длины 9. (Ответить) (Уровень выше)

	Дима, как с тобой связаться? attentus@lj 2005-05-03 14:04 (ссылка)
	Твой сосед по номеру в последней командировке в Нижний, ака attentus. (Ответить) (Ветвь дискуссии)

	Re: Дима, как с тобой связаться? flaass@lj 2005-05-03 23:51 (ссылка)
	Можно мылом, но можно и именно так :) О написанных комментариях меня извещают. А сейчас как раз собрался написать немного о Нижнем. (Ответить) (Уровень выше)