Я изо всех сил пытаюсь масштабировать проблему ограничения (она не работает для больших значений и / или если я пытаюсь оптимизировать, а не просто искать какое-либо решение). Я предпринял некоторые шаги, чтобы сократить пространство поиска, основываясь на советах из некоторых предыдущих вопросов, но это все еще задерживается. Есть ли еще какие-нибудь методы, которые помогут мне оптимизировать эти вычисления?
%%% constants %%%
#const nRounds = 4.
#const nPlayers = 20.
#const nRooms = 4.
#const nDecks = 7.
player(1..nPlayers).
room(1..nRooms).
deck(1..nDecks).
writer(1,1;2,2;3,3;4,4).
% For reference - that's what I started with:
%nRounds { seat(Player, 1..nRooms, 1..nDecks) } nRounds :- player(Player).
% Now instead I'm using a few building blocks
% Each player shall only play nRounds decks
nRounds { what(Player, 1..nDecks) } nRounds :- player(Player).
% Each player shall only play in up to nRounds rooms.
1 { where(Player, 1..nRooms) } nRounds :- player(Player).
% For each deck, 3 or 4 players can play in each room.
3 { who(1..nPlayers, Room, Deck) } 4 :- room(Room), deck(Deck).
% Putting it all together, hopefully, this leads to fewer combinations than the original monolithic choice rule.
{ seat(Player, Room, Deck) } :- what(Player, Deck), where(Player, Room), who(Player, Room, Deck).
% A player can only play a deck in a single room.
:- seat(Player, Room1, Deck), seat(Player, Room2, Deck), Room1 != Room2.
% A player must play nRounds decks overall.
:- player(Player), #count { Room, Deck: seat(Player, Room, Deck) } != nRounds.
% Any deck in any room must be played by 3-4 players.
legal_player_count(3..4).
:- room(Room), deck(Deck),
Players = #count { Player: seat(Player, Room, Deck) },
Players > 0,
not legal_player_count(Players).
% Writers cannot play their own decks.
:- writer(Player, Deck), seat(Player, _, Deck).
% At least one non-playing player per room.
:- deck(Deck),
Playing = #count { Player, Room: seat(Player, Room, Deck) },
Rooms = #count { Room: seat(_, Room, Deck) },
nPlayers - Playing < Rooms.
%:- room(R1), deck(D), room(R2), X = #sum { P: seat(P, R1, D) }, Y = #sum { P: seat(P, R2, D) }, R1 > R2, X > Y.
#minimize { D: decks(D) }.
#show decks/1.
#show seat/3.
% #show common_games/3.
Когда или если это станет управляемым, я надеюсь добавить больше целей оптимизации, чтобы выбрать лучшие конфигурации по следующим направлениям:
% Input points(P, R, D, X) to report points.
% winner(P, R, D) :- points(P, R, D, X), X = #max { Y : points(_, R, D, Y) }.
% Compute each player's rank based on each round:
% rank(P, D, R) :- points(P, Room, D, X), winner(Winner, Room, D), D_ = D - 1,
% rank(P, D_, R_),
% R = some_combination_of(X, P=Winner, R_).
% latest_rank(P, R) :- D = #max { DD: rank(P, DD, _) }, rank(P, D, R).
% Total number of decks played throughout the night (for minimisation?)
decks(Decks) :- Decks = #count { Deck: seat(_, _, Deck) }.
% Total number of games played together by the same players (for minimisation)
% The total sum of this predicate is invariant
% Minimisation should took place by a superlinear value (e.g. square)
common_games(Player1, Player2, Games) :-
player(Player1), player(Player2), Player1 != Player2,
Games = #count { Room, Deck:
seat(Player1, Room, Deck),
seat(Player2, Room, Deck)
}, Games > 0.
% For example:
% common_game_penalty(X) :- X = #sum { Y*Y, P1, P2 : common_games(P1, P2, Y) }.
% Another rank-based penalty needs to be added once the rank mechanics are there
% Then the 2 types of penalties need to be combined and / or passed to the optimiser
Обновление - описание проблемы
- Игроки P собираются на ночь викторин. Для игры доступны колоды D и R.
- В каждой комнате могут разместиться только 3 или 4 игрока (из-за правил игры, а не из-за места).
- Каждая Колода разыгрывается не более одного раза и одновременно в нескольких комнатах, так что в некотором смысле Колода является синонимом Раунда.
- Каждый игрок может играть одной и той же колодой не более одного раза.
- Каждый игрок может сыграть только N раз за ночь (N практически фиксировано, а это 4).
- Таким образом, если в течение ночи сыграно 9 колод (т.е.если присутствует много игроков), каждая сыграет 4 из этих 9.
- Следовательно, нет необходимости, чтобы каждый игрок играл в каждой колоде / раунде. Фактически, для каждой колоды есть писатель, и это обычно один из присутствующих игроков.
- Естественно, писатель не может разыграть свою колоду, поэтому в этом раунде он не участвует. Кроме того, для каждой колоды / раунда кто-то должен прочитать вопросы в каждой комнате, поэтому, если присутствует 16 игроков и есть 4 комнаты, все 16 игроков не смогут играть. Можно иметь 4 комнаты по 3 игрока в каждой (а оставшиеся 4 игрока зачитывают вопросы) или 3 комнаты по 4 игрока в каждой (3 игрока читают вопросы, а 1 наблюдает).
Надеюсь, это проясняет путаницу, если нет, я могу попытаться привести более подробные примеры, но в основном, скажем, если у вас 4 комнаты и 30 игроков:
- Вы выбираете 16, кто будет играть, и еще 4, кто зачитает вопросы
- Затем у вас есть 16 человек, которые сыграли своей 1/4 колодой / раундом, и 14 человек, которые все еще на 0/4.
- Таким образом, вы можете либо позволить другим 14 людям играть (4,4,3,3 игрока на комнату), либо продолжить максимизировать полезность комнаты, чтобы после второго раунда все играли хотя бы один раз, а 2/30 игроков уже сыграли 2 / 4 игры.
- Итак, вы продолжаете выбирать некоторое количество людей, пока все не сыграют ровно 4 колоды / раунда.
P.S. У вас есть 2 понятия раунда - одно на личном уровне, где у каждого есть 4 игры, а другое на уровне лиги, где имеется некоторое количество колод ›4, и каждая колода считается раундом в глазах всех присутствующих. Насколько я понял, это был самый запутанный момент в настройке, который я не очень хорошо прояснил вначале.
