Сиюминутное и повседневное | Записки лишнего человека Голосов: 1 Адрес блога: http://4xpro.ru/lytdybr/ Добавлен: 2018-09-03 16:05:21 блограйдером 4X_Pro Принадлежит блограйдеру 4X_Pro

Legends of Code and Magic: итоги

2018-08-26 22:45:25 (читать в оригинале)

Прошлое воскресенье и понедельник я провел в очень подавленном состоянии. На конкурсе CodinGame дела шли очень плохо: несмотря на все мои попытки усовершенствовать алгоритм, я скатывался все ниже и ниже в рейтинге, и никак не мог понять, почему это происходит. Вроде ошибок нет, алгоритм играет нормально, а я все равно раз за разом проигрываю. Еще и чата узнал, что есть люди, которые вообще написали полноценный симулятор этой игры у себя на компьютере и провели на нем моделирование множества игр, на основании чего для каждой карты определили коэффициент ее полезности. Стало ясно, что с моим простеньким алгоритмом выбора карт с такими тягаться не по силам. <br />
Попробовал даже быстро написать новый вариант (уже пятый по счету), но и в нем результаты отличались не сильно. Во вторник я прекратил все эти попытки, а стал искать среди уже отправленных версий те, на которых мне еще удавалось подняться хотя бы до середины лиги. И в итоге нашел такую, которая позволила снова подпрыгнуть до 202 места. Среда и четверг ушли на испытание в этой версии некоторых идей, которые возникли в воскресенье и понедельник. Еще я пытался поиграться с функцией выбора карт на этапе начальной раздачи. Но все было безрезультатно: либо изменения были несущественны, либо наоборот, я начинал падать вниз. Кроме того, так и оставался вопрос с тем багом, про который я уже писал. Почему-то при его наличии результаты получались в разы лучше, чем при его отсутствии, хотя с точки зрения здравого смысла должно было быть все наоборот. Еще пытался изучить статистику и понять, на каких именно раскладах я проигрываю, но все что удалось — это сделать предположение, что проигрыши идут на раскладах, где guard-карт мало, а противник набирает много «тяжелых» карт.<br />
Наконец, наступил последний день конкурса — пятница. Тут мне пришло в голову (опять же, под влиянием чата) применить метод Монте-Карло, то есть выбирать ход случайно, моделировать возможный ответ противника, исходя из соображения, что он будет бить только в guard-карты и моего игрока, и оценивать результат, выбирая в итоге тот, у которого оценка оказалась лучшей. На удивление быстро я переделал под него свой старый код, но увы, такой подход тоже оказался совершенно безрезультатным: я по-прежнему оказывался на дне серебряной лиги. <br />
Вообще, если в предыдущих конкурсах было понятно, что делать, как играть, чтобы выиграть, но у меня не хватало знаний описать это математически и закодировать, то в этом — все наоборот. Я мог написать практически любую стратегию, но никак не мог понять, как вообще надо играть, чтобы выигрывать. В частности, как именно происходит захват стратегической инициативы, когда у одной из сторон на столе оказывает на три или более карт больше, после чего дальнеший ход игры, фактически, предрешен. А не понимая этого, я мог делать функцию оценки только вслепую из общих соображений типа «health points и показатели карт на столе моего игрока должны давать плюс, health points и карты противника — минус». И, судя по всему, главный недостаток моего алгоритма заключался в том, что слишком часто он решал выложить новую карту вместо того, чтобы бить в противника. И еще я не учел ассиметричности игры, того, что оказавшись вторым по очередности хода, нужно играть иначе, чем первым (хотя как именно «иначе» — не понимаю до сих пор). Из-за этого у меня было много результатов, когда я у одного и того же противника первым игроком выигрываю, вторым — проигрываю.<br />
Еще непростой выбор был в конце между двумя версиями кода, одна из которых была хорошо протестирована, а другая — меньше, но вроде бы давала лучший результат. В итоге менее чем за минуту я все же выбрал вторую. И вроде бы не прогадал: 203 место в серебряной лиге, 590-ое в общем зачете. То есть с небольшой погрешностью повторил свои результаты предыдущих конкурсов. <br />
В общем, что можно сказать в итоге: переписал код целых семь раз, получил массу опыта и интересных идей, попробовал делать то, о чем прежде имел весьма смутные представления, впервые стал целенаправленно применять функциональный подход и оценил его преимущества, да и вообще стал чувствовать себя в Python так же уверенно, как и в PHP. Но увы, в плане результатов я ожидал все же большего…