2

我正在尝试使用 cligo 生成锦标赛玩家房间分配：

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 分，而不仅仅是 1 分（这就是这段代码发生的情况）。在实践中，运行它penalty(4).并没有任何game(player, room).分配。

另外，我想有一些限制，这样我就不会遇到一些玩家还有几轮要玩但没有足够的玩家的情况（例如，如果你有 1、2 或 5 个玩家只需要打一轮）。我不确定正确的不变量是什么，它可以保证即使提前几轮也不会发生这种情况。这更像是一个实际的逻辑问题，而不是固执己见。在实践中，您有大约 3-4 个房间和大约 20-30 个玩家 - 重要的是，永远不能保证 # 个玩家是 4 的因素。

我目前的“实施”中缺少的其他东西是一个约束，即对于特定的玩​​家子集（让我们称他们为“专家”），他们中的至少一个必须留在当前回合之外（并领导它）。一般来说，对于每个使用的房间，至少有一名玩家必须留在外面（包括一名专家）。这应该是一个硬约束。

最后，我们希望最大化房间的利用率，即最大化每轮的玩家数量并最小化总体轮数。这应该是一个弱约束（就像到目前为止一起玩的排名和游戏的约束一样）。

非常感谢您的任何帮助或建议！不幸的是，文档没有提供这么多复杂的示例，所以我无法弄清楚我的用例的正确语法是什么。

4

2 回答 2

0

在答案集编程中，在开始时编写所有内容并在之后尝试调试是很困难的。在您的情况下，最好先定义您的搜索空间并逐个写入约束以删除不需要的答案。

要在每一轮之后更新输入，您必须使用“在线 ASP”。您可能需要考虑查看https://potassco.org/clingo/，因为它包含可以帮助您学习的有价值的学习材料。下面的编码对您来说可能是一个很好的起点

%%% constants %%%
#const numberOfRounds = 4.
#const numberOfPlayers = 2.
#const numberOfRooms = 4.
%%% constants %%%

%%% define players and their initial ranks %%%
player(1..numberOfPlayers,1).
%%% define players and their initial ranks %%%

%%% define rooms %%%
room(1..numberOfRooms).
%%% define rooms %%%

%%% define rounds %%%
round(1..numberOfRounds).
%%% define rounds %%%

%%% define search space (all possible values) %%%
search(P,R,S) :- player(P,_), room(R), round(S).
%%% define search space (all possible values) %%%

%%% define played %%%
{played(P,R,S)} :- search(P,R,S).
%%% define played %%%

%%% remove answers that does not satisfy the condition "Each player needs to play 4 rounds" %%%
:- player(P,_), X = #count{S : played(P,_,S)}, X != numberOfRounds.
%%% remove answers that does not satisfy the condition "Each player needs to play 4 rounds" %%%

%%% show output %%%
#show.
#show played/3.
%%% show output %%%
于 2021-05-11T06:05:09.583 回答
0

根据 NTP 的建议，我再次尝试重写，现在几乎所有约束都存在并且似乎有效，除了我仍然必须添加的基于排名的惩罚。

%%% constants %%%
#const nRounds = 3.
#const nPlayers = 4.
#const nRooms = 3.
#const nDecks = 4.

player(1..nPlayers).
room(1..nRooms).
deck(1..nDecks).
writer(1,1;2,2;3,3;4,4).

{ played(P, R, D) } :- player(P), room(R), deck(D).

% A player can only play a deck in a single room.
:- played(P, R1, D), played(P, R2, D), R1 != R2.
% A player must play nRounds decks overall.
:- player(P), X = #count { R, D: played(P, R, D) }, X != nRounds.
% Any deck in any room must be played by 3-4 players.
legal_player_count(3;4).
:- room(R), deck(D),
  X = #count { P: played(P, R, D) },
  X > 0,
  not legal_player_count(X).
% Writers cannot play their own decks.
:- writer(P, D), played(P, _, D).
% At least one non-playing player per room.
:- deck(D),
  Playing = #count { P, R: played(P, R, D) },
  Rooms = #count { R: played(_, R, D) },
  nPlayers - Playing < Rooms.

% 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) }.

% Total number of decks played throughout the night (for minimisation?)
decks(X) :- X = #count { D: played(_, _, D) }.
% 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(P1, P2, X) :- player(P1), player(P2), P1 != P2,
  X = #count { R, D: played(P1, R, D), played(P2, R, D) }, X > 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

#show decks/1.
#show played/3.
#show common_games/3.
于 2021-05-10T14:19:10.830 回答