Антикомпьютерный контроль (АКК)

← →
xayam © (2010-05-26 12:25) [0]

Вот такая тема. Есть запись партии в шахматы, нужно определить использовалась ли помощь программ или нет? Интересуют естественно алгоритмы, идеи, исходники, если есть. Компьютерных движков навалом, АКК не нашел.

← →
Думкин © (2010-05-26 12:31) [1]

1.e2-e4

Дисквалификация! Вы используете программу!

← →
xayam © (2010-05-26 12:33) [2]

если бы еще все партии выигрывались бы одним этим ходом ;)

← →
xayam © (2010-05-26 12:42) [3]

кстати вот и код :)
<?php
function ACC($moves) {

if ( $moves[0]["from"] == "e2" && $moves[0]["to"] == "e4" )
return true; //используется прога
else
return false; //не используется прога

}
?>

← →
oldman © (2010-05-26 12:47) [4]

> Есть запись партии в шахматы, нужно определить использовалась
> ли помощь программ или нет?

Если существует запись, программа использовалась!
:)

← →
brother © (2010-05-26 13:02) [5]

> Если существует запись, программа использовалась!

VHS кассета? Пленка 12мм, там какая программа? ;)

← →
xayam © (2010-05-26 13:10) [6]

> oldman © (26.05.10 12:47) [4]
> Если существует запись, программа использовалась!

тогда так :)
<?php function ACC($notation = false) { return $notation; } ?>
PS А по делу есть что сказать?

← →
brother © (2010-05-26 13:12) [7]

имхо, на докторскую тянет...

← →
xayam © (2010-05-26 13:21) [8]

судя по ответам - тянет как минимум на 5 страниц флейма :)

← →
Медвежонок Пятачок © (2010-05-26 13:21) [9]

идеи, исходники, если есть.

Есть идея, что даже если кто-то получит исходник и вычислит, что я пользовался программой, то доказать это он не сможет, а я всегда смогу отвертеться от того, что использовалась программа. (даже если у меня найдут запущенный процесс этой программы и даже если это будет документально зафиксировано).

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

← →
Медвежонок Пятачок © (2010-05-26 13:26) [10]

Иными словами получение знания о том, что программа работала во время матча ничего не дает.

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

← →
xayam © (2010-05-26 13:27) [11]

> Медвежонок Пятачок © (26.05.10 13:21) [9]
> Я скажу, что все ходы мои, а в программу я даже не смотрел,
> либо смотрел, но после того, как сделаю самостоятельный ход.

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

← →
Медвежонок Пятачок © (2010-05-26 13:32) [12]

Что хотят и чего не хотят - это другой вопрос.
А пометить игрока как комп легче легкого:

"я его пометил как бота потому что он у меня слишком часто выигрывает"

и не волнует ни разу что там на самом деле человек был, а не бот.

← →
RWolf © (2010-05-26 13:33) [13]

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

← →
xayam © (2010-05-26 13:33) [14]

> Медвежонок Пятачок © (26.05.10 13:32) [12]
> "я его пометил как бота потому что он у меня слишком часто
> выигрывает"
> и не волнует ни разу что там на самом деле человек был,
> а не бот.

почему это не волнует? Как раз волнует, раз алгоритмы спрашиваю. Если бы не волновало, то как бы и проблемы не было бы. Не?

← →
Медвежонок Пятачок © (2010-05-26 13:34) [15]

ну как бы... иногда люди хотят играть только с людьми, а что ты скажешь не имеет особого значения

Ну вот тебе ситуация.
Играешь ты, и играю я.
Рядом со мной пролиант 580 с четырьмя зионами и шахматной программой.
Я всегда делаю тебя.

Твои действия? (при условии что у тебя есть волшебный детектор упомянутый выше)

← →
brother © (2010-05-26 13:34) [16]

> на которых запущены все возможные шахматные программы

такая же мысль была... иначе никак...)

← →
12 © (2010-05-26 13:36) [17]

на 100%, даже на 80, невозможно, имхо, такое сделать

идея - подсовывать компьютерным движкам, позиции смотреть как сыграют они и как сыграли на самом деле.

Особенно:
цейтнотные
жертвы, когда ничего не видать от них на первый взгляд

в любом случае нужен совет квалифицированного игрока-человека, не ниже 1го разряда/кмс, имхо

← →
Думкин © (2010-05-26 13:37) [18]

> вероятно, ей оппонент и пользуется.

← →
Медвежонок Пятачок © (2010-05-26 13:37) [19]

Другая ситуация:

Играешь ты и играет каспаров (ну допустим, что ему скучно и он вышел в инет)
И он тоже постоянно тебя делает.

"Какие ваши доказательства?" - /* как однажды спросили у губернатора калифорнии в красной жаре */

← →
xayam © (2010-05-26 13:37) [20]

> RWolf © (26.05.10 13:33) [13]
> с началом матча запускаем кластер из компьютеров

это как бы не алгоритм. Интересует программная реализация, а не техническая. Тем более где взять кластер? Все ли программы учтутся?

← →
xayam © (2010-05-26 13:41) [21]

> Медвежонок Пятачок © (26.05.10 13:34) [15]
> Ну вот тебе ситуация.
> Играешь ты, и играю я.
> Рядом со мной пролиант 580 с четырьмя зионами и шахматной
> программой.
> Я всегда делаю тебя.
> Твои действия? (при условии что у тебя есть волшебный детектор
> упомянутый выше)

некорректные условия, скорей так:
играют двое через сайт
я админю сервер
у меня есть волшебный детектор
Мои действия? Забанить тебя или перенести в отдельную песочницу для прог :)

← →
RWolf © (2010-05-26 13:42) [22]

> xayam © (26.05.10 13:37) [20]

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

> Тем более где взять кластер? Все ли программы учтутся?

Не так уж и много хороших компьютерных программ.
И по железу верхняя граница есть — сомневаюсь, что у оппонента Deep Blue под боком.

← →
Медвежонок Пятачок © (2010-05-26 13:43) [23]

некорректные условия, скорей так:
играют двое через сайт
я админю сервер
у меня есть волшебный детектор
Мои действия? Забанить тебя или перенести в отдельную песочницу для прог :)

Именно так. Двое и через сайт.
Но у меня рядом сервер. Причем отдельно стоящий, с моим компом никак не связанный (кроме визуальной доступности)

← →
xayam © (2010-05-26 13:43) [24]

> 12 © (26.05.10 13:36) [17]
> на 100%, даже на 80, невозможно, имхо, такое сделать

на Шахматной Планете есть АКК, и работает я проверял несколько раз.

← →
RWolf © (2010-05-26 13:44) [25]

[22]
> компьютерных

шахматных, конечно

← →
xayam © (2010-05-26 13:46) [26]

> Медвежонок Пятачок © (26.05.10 13:43) [23]
> Но у меня рядом сервер. Причем отдельно стоящий, с моим
> компом никак не связанный

а причем здесь это. Вход для АКК - запись партии, выход - true или false. А как ты там играешь - через другой комп или нет, не имеет значения.

← →
12 © (2010-05-26 13:46) [27]

интересно бы взглянуть на график минимаксной функции ИИ при игре - может из него чего видно?

← →
Медвежонок Пятачок © (2010-05-26 13:47) [28]

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

а на самом деле здесь все не так.
задача не в том, чтобы выявить читера.
задача в том, чтобы не играть с тем, с кем не интересно играть.

а с кем не интересно играть?

с тем кто всегда проигрывает (в том числе если это человек).
с тем кто всегда выигрывает (в том числе если это человек).
возможно еще есть варианты.

вот и все.

← →
xayam © (2010-05-26 13:49) [29]

> 12 © (26.05.10 13:46) [27]
> интересно бы взглянуть на график минимаксной функции ИИ
> при игре - может из него чего видно?

т.е. по-любому нужен свой движок для оценки? И как график строить?

← →
Медвежонок Пятачок © (2010-05-26 13:49) [30]

а причем здесь это. Вход для АКК - запись партии, выход - true или false.

Ну положим я каспаров или просто помню много партий наизусть.
Меня твой детектор пометит? (По сильной корреляции моих ходов с известными комбинациями)

← →
RWolf © (2010-05-26 13:50) [31]

> Медвежонок Пятачок © (26.05.10 13:47) [28]

а если субъект использует программу, но слабую?

← →
xayam © (2010-05-26 13:51) [32]

> т.е. по-любому нужен свой движок для оценки

и с чего ты взял, что оценка моего движка совпадет с оценкой проверяемой играющего прогой?

← →
Медвежонок Пятачок © (2010-05-26 13:51) [33]

а если субъект использует программу, но слабую?

Дык в том то и дело!

см. [28]

← →
Медвежонок Пятачок © (2010-05-26 13:56) [34]

Смысл любой игры - в недетерминированности ее результата.

Интересно - это когда можно и проиграть и когда можно выиграть.

При этом неважно - использует противник чит или нет. Или там вообще нет противника, а работает бот.

И не надо говорить, что с ботом играть всегда неинтересно.
Иначе бы не было партий с тем самым дипблю.

Один играл, а куча народа наблюдала за процессом.
Если бы это было неинтересно, ничего бы подобного не было бы.

← →
12 © (2010-05-26 14:02) [35]

да, движок полюбому нужен, имхо
и не один или один но глубину перебора разную ставить

Имеем Н графиков минимакса на разных глубинах для каждого хода
Оцениваем график ходов, смотрим отклонения от каждого.
При наличии большого количества отклонений на глубине более 4-5-6 полуходов и выше, особенно в миттельшпиле - я бы поставил оценку "не используется программа"

← →
xayam © (2010-05-26 14:06) [36]

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

← →
Медвежонок Пятачок © (2010-05-26 14:12) [37]

я бы поставил оценку "не используется программа"

Имеется 500 аккаунтов на которых играют чайники.
У них нет программы, и они всегда проигрывают "матом в два хода"

им ставится оценка "нет программы"

Иным читерам, кто попал под раздачу, оценка выставлена "используется программа"

Что в итоге:
знаем с кем играть не стоит.
но, тем не менее, все еще не знаем, с кем играть стоит.

/* Не думаю, что играть с чайником более интересно, чем с читером */

← →
Омлет © (2010-05-26 14:18) [38]

Все, кто выигрывает, жулики.

← →
12 © (2010-05-26 14:18) [39]

> но оценочная функция разная,

нет

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

Компьютер оценивает ходы Подопытного - строится график
Компьютер на разных уровнях глубины перебора строит "идеальный" график.

Человек может заглянуть вперед намного дальше ИИ, и сыграть сильнее, на перспективу, но ИИ оценит это как слабость. Точка будет ниже чем его точки.

И надо посчитать такие точки, с учетом смещения к концу игры(больше весят такие)

← →
Медвежонок Пятачок © (2010-05-26 14:24) [40]

И надо посчитать такие точки, с учетом смещения к концу игры(больше весят такие)

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

← →
12 © (2010-05-26 14:26) [41]

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

да,
а иначе не предположить никак вообще - он может и монеткой сходить как ГлубокийГолубой после 24ч раздумий

← →
xayam © (2010-05-26 14:48) [42]

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

если бы это действительно было так, но еще оценкой отличается, иначе проблемы не было бы.

← →
Медвежонок Пятачок © (2010-05-26 14:59) [43]

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

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

> еще оценкой отличается

конечно.
методикой оценивания, точнее, приоритетами в оценках

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

> мастер спорта обыграет новичка без того, что вы назвали
> "с виду слабый ход, но заточенный на перспективу" - ему
> для выигрыша достаточно будет стандартных комбинаций

если новичок не будет пользоваться компом - они и не попадут в стандартные ситуации. Там после 4-5 ходов будет позиция, отсутствующая в справочнике.

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

Мастер..
Думаю мастер или играть не станет,
или будет баловаться - в любом случае не попадет под определение

Там после 4-5 ходов будет позиция, отсутствующая в справочнике.

Там возможно вообще ничего не будет.
В том смысле, что ответы новичка на стандарты мастера не будут вообще никак связаны с атаками мастера.

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

в итоге у мастера черная метка.

> очевидно, оценки будут по одной системе

а какая разница, ни ее оценки, ни этой одной системы я не знаю.

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

пример?
А я думаю, что на каждый бессмысленный ход, или ход, не разрушающие стандартную атаку, но странный, со стороны мастера будет уже другой ход, не вписывающийся в стандарты.

> а какая разница, ни ее оценки, ни этой одной системы я не
> знаю.

надо взять программу с исходником, или ту, которая пишет в чью пользу сейчас, при текущих расчетах(есть такие - где то в углу пишется число, + или -, и значение. 0 - вероятно, что ничья)
Вот это число и будет значением по Y
по х, естественно, полуход

Далее в ту же программу загоняется позиция и делается ход, как у подопытного - ловим число-оценку.

итого
число когда сама ходит и число когда мы сходим.
и так для каждого уровня перебора.

А я думаю, что на каждый бессмысленный ход, или ход, не разрушающие стандартную атаку, но странный, со стороны мастера будет уже другой ход, не вписывающийся в стандарты.

А я думаю иначе.
Если новичек не в силах помешать стандартной атаке, то мастер закончит партию стандартно.

> мастер закончит партию стандартно.

это как он ее закончит стандартно, если я пешку не ту двину, допустим
и проиграю всю позицию, отдам центр, инициативу, слонов позапираю

какие тут стандарты, если так играть нигде не советуют и не рассматривают далее продолжение, после таких ходов?

Мастер начнет давить, безусловно, но это будет не стандартно, а "просто давить" .

Если длина моей партии с противником была более 30-40 ходов,
и у моей шахматной программы найдутся такие настройки,
при которых, начиная с 10 хода, 95% процентов ее ходов совпадут
с ходами противника, то противник бот на 95% :)

А если нет 40 ходов, то что? Вот полноценная партия 25 ходов:
1. e4 e5 2. Nf3 Nc6 3. Bc4 Nd4 4. c3 Nxf3 5. Qxf3 Nf6 6. d4 d6 7. 0-0 h6 8. h3 Be7 9. Rd1 Bd7 10. dxe5 dxe5 11. Qg3 g5 12. Qxe5 a6 13. Qd4 b5 14. Bb3 c5 15. Qe3 c4 16. Bc2 0-0 17. e5 Nh5 18. Qe4 f5 19. exf6 Nxf6 20. Qg6 Kh8 21. Qxh6 Kg8 22. Qxg5 Kf7 23. Qg6 Ke6 24. Bf5 Ke5 25. f4# 1-0

если я пешку не ту двину, допустим

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

> xayam © (26.05.10 13:27) [11]
я б рассмотрел совсем с другой стороны, анализировал не алгоритм игры, а алгоритм поведения игроков, т.е. время между ходами, соотношение времени между ходами и их сложности, машина конечно покажет более линейные зависимости..

> соотношение времени между ходами и их сложности

ну с временем понятно, а вот со сложностью заковыка имхо. По какому принципу определяется сложность? Я сам иногда нахожу сложный, но понятный мне выйгрыш, а иногда ошибаюсь в 1-2 хода.

← →
Юри й Зотов (2010-05-26 20:12) [55]

Что тут обсуждать? Очевидно же, что точно определить нельзя, а с какой-то долей вероятности - можно.

раньше еще говорили, что программа никогда не сможет играть в силу гроссмейстера, но с вероятностью 0.0000...1 это случилось :)

> xayam © (26.05.10 20:18) [56]

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

> компьютер намного превосходит объем памяти любого человека

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

> Заведомо ясно, что по скорости счета вариантов компьютер
> намного превосходит любого человека.

Любого средне статистического да. Но не гроссмейстера. Гроссмейстер отобранный обученный выведенный тип человека способный считать кучу комбинаций причем не всегда осознанно. Но в пределе да компьютер справиться с задачью перебора лучше.

> У компьютера - статическая,

Не статическая, у него ОЗУ.

> У компьютера соответственно "проблема" в том, что нет идеального
> алгоритма оценки позиции (перебор не помогает),

Это не у компьютера проблема, а проблема человека который не может её написать. xayam, камень в ваш огород.

> xayam © (26.05.10 20:18) [56]
> раньше еще говорили, что программа никогда не сможет играть
> в силу гроссмейстера, но с вероятностью 0.0000...1 это случилось
> :)

А еще раньше говорили что земля плоская. ;-)

О сколько нам открытий чудных Готовят просвещенья дух И опыт, сын ошибок трудных, И гений, парадоксов друг, И случай, бог изобретатель...

> xayam © (26.05.10 22:44) [58]
> У компьютера соответственно "проблема" в том, что нет идеального
> алгоритма оценки позиции
именно так оно и есть, насколько я знаю, в шахматах каждой фигуре присваивается своё количество баллов, потом чисто математически просчитывается, выгодно ли терять ту или иную фигуру. и именно глубина мат модели и определяет уровень программы..

> в шахматах каждой фигуре присваивается своё количество баллов

вообще там два балла каждой фигуре присваивается. Один - статический вес (пешка = 100, конь и слон = 300, ладья = 500, ферзь = 800, король = сумма всех фигур) и второй - динамический. Например, второй параметр для коня может выглядеть так в зависимости от его расположения на доске:
0 4 8 10 10 8 4 0 4 8 16 20 20 16 8 4 8 16 24 28 28 24 16 8 10 20 28 32 32 28 20 10 10 20 28 32 32 28 20 10 8 16 24 28 28 24 16 8 4 8 16 20 20 16 8 4 0 4 8 10 10 8 4 0
т.е. у коня приоритет центра и т.д.

Антикомпьютерный контроль (АКК) Найти похожие ветки