Я пытаюсь использовать clingo для создания распределения турнирных игровых комнат:
player(1..20).
room(1..4).
played(1..20, 0).
rank(1..20, 1).
played(1..20, 1..20, 0).
0 { used_room(R) } 1 :- room(R).
3 { game(P, R) } 4 :- used_room(R), player(P).
:- game(P, R1), game(P, R2), R1 != R2.
penalty(Y) :- Y = #sum {
X: game(P1, R), game(P2, R), played(P1, P2, X);
X: game(P1, R), game(P2, R), rank(P1, R1), rank(P2, R2), abs(R1-R2) = X;
4 - X: played(P, X), not game(P, _)
}.
#minimize { X: penalty(X) }.
Первые 5 строк должны быть вводом:
- Количество присутствующих игроков варьируется
- Количество свободных номеров
- Каждому игроку нужно сыграть 4 раунда за ночь, поэтому мы записываем количество раундов, сыгранных каждым игроком на данный момент.
- У каждого игрока есть ранг (в таблице лиг), который обновляется после каждого раунда — в идеале игроки в каждой комнате должны иметь одинаковые уровни (например, ELO).
- Чтобы препятствовать тому, чтобы алгоритм постоянно объединял одних и тех же игроков, мы также отслеживаем количество раундов, которое любая пара игроков провела вместе в одной комнате.
Идея состоит в том, чтобы обновлять эти входные данные после каждого раунда (после получения точек) и возвращать их обратно в решатель для создания распределения следующего раунда.
Затем я попытался добавить некоторые ограничения:
- Доступно определенное количество комнат, но не обязательно использовать их все. Каждую комнату можно использовать или не использовать в каждом раунде.
- В любой используемой комнате должны быть назначены 3 или 4 игрока (из-за механики игры - 4 всегда предпочтительнее, 3 для работы с крайними случаями)
- Ни один игрок не может быть назначен более чем в одну комнату в течение одного раунда.
Наконец, я попытался определить некоторые штрафы, чтобы помочь решателю выбрать наилучшее распределение:
- Для каждой пары игроков P1, P2, которые были размещены в одной комнате, добавьте X к штрафу, где X — количество раз, когда они уже играли вместе.
- Для каждой пары игроков P1, P2, которые были размещены в одной комнате, к штрафу добавляется (абсолютная) разница в их рангах.
- Для каждого игрока, который должен сыграть еще X раундов, но не был выбран для этого раунда, добавьте X к штрафу.
Я хотел сделать так, чтобы этот штраф накапливался, чтобы каждый игрок, у которого осталось 4 раунда (то есть каждый игрок в начале), добавлял к штрафу 4 очка, а не только одно (что и произошло с этим кодом). На практике выполнение этого получает penalty(4).
и вообще не выделяет game(player, room).
.
Кроме того, я хотел бы иметь некоторое ограничение, чтобы я не мог оказаться в ситуации, когда у некоторых игроков еще остались раунды для игры, но осталось недостаточно игроков (например, если у вас остался 1, 2 или 5 игроков, которым просто нужно играть один раунд). Я не уверен, каков правильный инвариант, который мог бы гарантировать, что этого не произойдет даже на несколько раундов вперед. Это скорее реальный логический вопрос, чем цепляние. На практике у вас есть около 3-4 доступных комнат и около 20-30 игроков — важно, никогда нет гарантии, что количество игроков будет в 4 раза больше.
Что-то еще, чего не хватает в моей текущей реализации, — это ограничение, согласно которому для определенного подмножества игроков (назовем их экспертами) по крайней мере один из них должен оставаться вне текущего раунда (и вести его). И вообще для каждой используемой комнаты должен остаться хотя бы один игрок (включая одного эксперта). Это должно быть жестким ограничением.
Наконец, мы хотели бы максимизировать использование комнат, то есть максимизировать количество игроков за раунд и минимизировать количество раундов в целом. Это должно быть слабым ограничением (точно так же, как ограничения, связанные с рангами и играми, сыгранными до сих пор вместе).
Заранее большое спасибо за любую помощь или совет! К сожалению, в документации не так много сложных примеров, поэтому я не смог понять, какой правильный синтаксис подходит для моих вариантов использования.
3 { P: game(P, R) } 4
- person rudolfovic   schedule 10.05.2021