최종 결과 제공
소개
무거운 주제 ( 판타지 전쟁 , 전 세계적으로 유행하는 …)를 가진 나의 이전 KOTH 이후 , 나는 새로운 가벼운 마음으로 돌아 왔습니다. 이번에는 “보드 게임과 같은”상황에서 직면하고 있습니다. 거꾸로 동전 더미가 정말 큰 테이블의 중앙에 놓이고, 당신은 전리품에 대한 지분을 얻겠다고 결심합니다!
어휘
코인 : 뒤집거나 뒤집을 수없는 토큰.
Unflipped : 동전이 값이 아래를 향하도록 테이블 위에 놓입니다. 이것이 동전의 기본 상태입니다.
뒤집기 : 동전이 값을 가리키는 테이블 위에 놓입니다.
지역 : 동전 더미를 나타냅니다.
Global : 중앙의 동전 더미를 나타냅니다.
원리
게임 시작시 , 각 플레이어는 0 포인트 와 0 코인 (플립 또는 언 플립)으로 시작합니다. 게임은 턴제입니다. 턴 중에 플레이어는 테이블 중앙에있는 동전 더미, 자신의 동전 더미 또는 다른 플레이어와 상호 작용하는 최대 3 개의 행동을 취할 수 있습니다.
플레이 순서는 게임 시작시 무작위로 정의됩니다. 인수 목록의 플레이어 순서는 턴 순서를 나타내며 해당 목록의 왼쪽에서 오른쪽으로 진행됩니다. “다음”및 “이전”은 각각 “목록의 오른쪽에있는”및 “목록의 왼쪽에있는”을 의미합니다.
게임은 50 라운드 동안 지속 되거나 플레이어 차례가 끝날 때 중앙 에 동전 이 0 개가 될 때까지 지속됩니다 (즉, 첫 번째 행동 후에 더미가 비어 있어도 3 가지 행동을 마치고 동전을 다시 넣을 수 있음을 의미합니다. 게임은 계속됩니다). 글로벌 코인의 시작 수는 다음 공식으로 무작위로 정의됩니다.
(2 ^ nb_players) + (nb_players * 10) - random(1 + (nb_players ^ 2))`
각 행동은 당신에게 포인트를 얻거나 (또는 당신을 잃게합니다) 게임 이 끝날 때, 당신이 가진 각 동전은 당신의 포인트에 추가 될 것입니다 ( 풀리지 않은 경우 -1, 뒤집힌 경우 +2 ). 가장 높은 점수를받은 플레이어가 승리합니다.
컨트롤러는 명령 인수를 통한 입력을 제공하며 프로그램은 stdout을 통해 출력해야합니다.
통사론
입력
프로그램이 호출 될 때마다 다음 형식으로 인수를받습니다.
Round;YourPlayerId;Coins;PlayerId_Points_Flipped_Unflipped;PlayerId_Points_Flipped_Unflipped;...
라운드는 1 인덱스입니다.
입력 예
6;2;52;1_20_3_12;0_-2_0_1;2_12_1_0
여기, 당신은 그것이 6 라운드이고 당신은 2 번 선수라는 것을 알 수 있습니다. 12 포인트, 뒤집힌 동전 1 개, 뒤집지 않은 동전 0 개가 있습니다. 포인트는 음수 일 수 있습니다.
산출
공백없이 구분 기호없이 세 개의 문자를 출력해야합니다. 각 문자는 이번 차례에 한 번의 작업에 해당합니다. 문자 순서에 따라 동작 순서가 결정됩니다. 동일한 동작을 여러 번 출력 할 수 있습니다. 행동을 완료하기에 동전이 충분하지 않은 경우 사용 가능한 동전에 대해서만 사용 가능한 최대 동전 및 카운트 포인트를 사용합니다.
N
: 아무 것도하지 말 것
1
: 중앙 파일에서 동전 1 개 가져 오기 [효과 : 로컬 언 플립 +1 / 1 포인트 / -1 전역 unflipped]
2
: 중앙 더미에서 코인 2 개 가져 오기 [효과 : 로컬 unflipped +2 / -2 포인트 / -2 global unflipped]
3
: 중앙 더미에서 동전 3 개 가져 오기 [효과 : +3 로컬 unflipped / -3 포인트 / -3 global unflipped]
A
: 더미에서 동전 1 개를 옮깁니다. [효과 : -1 로컬 unflipped / +1 포인트 / +1 global unflipped]
B
: 더미에서 동전 2 개를 옮깁니다. [효과 : -2 로컬 unflipped / +2 점 / +2 global unflipped]
C
: 더미에서 3 개의 동전을 옮깁니다. [효과 : -3 로컬 unflipped / +3 점 / +3 global unflipped]
X
: 파일에서 동전 1 개 제거[효과 : -1 로컬 언 플립 / 0 포인트]
Y
: 파일에서 동전 2 개 제거 [효과 : -2 로컬 언 플립 / 0 포인트]
Z
: 파일에서 동전 3 개 제거 [효과 : -3 로컬 unflipped / 0 포인트]
R
: 동전 회전 이전 플레이어에게 [효과 : 비 플립 수 신당 -1 포인트, 뒤집힌 횟수 당 +2 포인트 / 모든 플레이어에 적용]
T
: 다음 플레이어로 동전 회전 [효과 : 비 플립 핑 된 수 신당 -1 포인트, 뒤집힌 수 신당 +2 포인트 / 적용 : 모든 플레이어]
F
: 동전 1 개 뒤집기 [효과 : 로컬 flfl 1 개 / 로컬 뒤집기 +1 / +2 점]
U
: 동전 1 개를 풉니 다 [효과 : 로컬 unflipped +1 개 / -1 로컬 뒤집기 / -2 점]
출력 예
2FF
: 동전 두 개를 가져와 동전 두 개를 뒤집어 채점 -2 + 2 + 2 = 2 points
출력이 정확하지 않으면 컨트롤러는로 가정 NNN
합니다.
제어 장치
컨트롤러는 GitHub 에서 찾을 수 있습니다 . 또한 Java로 작성된 두 개의 샘플 봇이 포함되어 있습니다. 실행하려면 프로젝트를 확인하고 Java IDE에서여십시오. main
클래스 의 메소드의 진입 점입니다 Game
. Java 8이 필요합니다.
봇을 추가하려면 먼저 컴파일 된 Java 버전 (.class 파일) 또는 해석 된 언어의 소스가 필요합니다. 프로젝트의 루트 폴더에 배치하십시오. 그런 다음 players
패키지 에 새 Java 클래스를 작성하십시오 (기존 봇에서 예를 들어 볼 수 있음). 이 클래스는 Player
메서드를 재정의하도록 구현해야합니다 String getCmd()
. 반환 된 문자열은 봇을 실행하기위한 쉘 명령입니다. 예를 들어 다음 명령으로 Ruby 봇을 작동시킬 수 있습니다 return "C:\Ruby\bin\ruby.exe MyBot.rb";
. 마지막으로 Game
클래스 상단의 플레이어 배열에 봇을 추가하십시오 .
규칙
- 봇은 다른 특정 봇을 이길 수 있도록 작성해서는 안됩니다.
- 파일 쓰기가 허용됩니다. “yoursubmissionname.txt”에 쓰면 게임이 시작되기 전에 폴더가 비워집니다. 다른 외부 리소스는 허용되지 않습니다.
- 제출 한 내용에 1 초의 응답 시간이 있습니다.
- 제출물을 컴파일하고 실행하는 명령을 제공하십시오.
지원되는 언어
모든 언어를 지원하려고하지만 온라인에서 무료로 사용할 수 있어야합니다. “주류”언어를 사용하지 않는 경우 설치 지침을 제공하십시오.
현재 Java 6-7-8, PHP, Ruby, Perl, Python 2-3, Lua, R, node.js, Haskell, Kotlin, C ++ 11을 실행할 수 있습니다.
최종 결과
다음은 100 게임의 결과입니다 (포인트가 합산 됨).
1. BirdInTheHand: 1017790
2. Balance: 851428
3. SecondBest: 802316
4. Crook: 739080
5. Jim: 723440
6. Flipper: 613290
7. Wheeler: 585516
8. Oracle: 574916
9. SimpleBot: 543665
10. TraderBot: 538160
11. EgoisticalBot: 529567
12. RememberMe: 497513
13. PassiveBot: 494441
14. TheJanitor: 474069
15. GreedyRotation: 447057
16. Devil: 79212
17. Saboteur: 62240
게임의 개별 결과는 여기에 있습니다 : http://pasted.co/63f1e924 (시작 동전과 게임 당 라운드 수).
50 명성의 현상금은 우승자에게 수여된다 : 새에 손 에 의해 마틴 있음 Büttner .
참여해 주셔서 감사합니다. 다음 KOTH에 TH겠습니다 ~
답변
손에 새, 루비
def deep_copy(o)
Marshal.load(Marshal.dump(o))
end
ID = 0
PTS = 1
FLP = 2
UFL = 3
round, id, global, *players = ARGV[0].split(';')
round = round.to_i
id = id.to_i
global = global.to_i
players.map!{ |s| s.split('_').map(&:to_i) }
nplayers = players.size
my_pos = players.find_index { |i, p, f, u| i == id }
state = {
round: round,
id: id,
global: global,
players: players,
my_pos: my_pos,
me: players[my_pos],
prev_p: players[my_pos-1],
next_p: players[(my_pos+1)%nplayers],
ends_game: round == 50 && my_pos == nplayers-1,
score: 0
}
moves = {
'N' => ->s{deep_copy(s)},
'1' => ->s{t = deep_copy(s); coins = [1, t[:global]].min; t[:global] -= coins; t[:me][UFL] += coins; t[:score] -= coins; t},
'2' => ->s{t = deep_copy(s); coins = [2, t[:global]].min; t[:global] -= coins; t[:me][UFL] += coins; t[:score] -= coins; t},
'3' => ->s{t = deep_copy(s); coins = [3, t[:global]].min; t[:global] -= coins; t[:me][UFL] += coins; t[:score] -= coins; t},
'A' => ->s{t = deep_copy(s); coins = [1, t[:me][UFL]].min; t[:global] += coins; t[:me][UFL] -= coins; t[:score] += coins; t},
'B' => ->s{t = deep_copy(s); coins = [2, t[:me][UFL]].min; t[:global] += coins; t[:me][UFL] -= coins; t[:score] += coins; t},
'C' => ->s{t = deep_copy(s); coins = [3, t[:me][UFL]].min; t[:global] += coins; t[:me][UFL] -= coins; t[:score] += coins; t},
'X' => ->s{t = deep_copy(s); coins = [1, t[:me][UFL]].min; t[:me][UFL] -= coins; t},
'Y' => ->s{t = deep_copy(s); coins = [2, t[:me][UFL]].min; t[:me][UFL] -= coins; t},
'Z' => ->s{t = deep_copy(s); coins = [3, t[:me][UFL]].min; t[:me][UFL] -= coins; t},
'F' => ->s{t = deep_copy(s); coins = [1, t[:me][UFL]].min; t[:me][UFL] -= coins; t[:me][FLP] += coins; t[:score] += 2*coins; t},
'U' => ->s{t = deep_copy(s); coins = [1, t[:me][FLP]].min; t[:me][FLP] -= coins; t[:me][UFL] += coins; t[:score] -= 2*coins; t},
'R' => ->s{
t = deep_copy(s)
(-1...t[:players].size-1).each do |i|
t[:players][i][FLP] = s[:players][i+1][FLP]
t[:players][i][UFL] = s[:players][i+1][UFL]
end
t[:score] += 2*t[:me][FLP] - t[:me][UFL];
t
},
'T' => ->s{
t = deep_copy(s)
(0...t[:players].size).each do |i|
t[:players][i][FLP] = s[:players][i-1][FLP]
t[:players][i][UFL] = s[:players][i-1][UFL]
end
t[:score] += 2*t[:me][FLP] - t[:me][UFL];
t
}
}
results = {}
'N123ABCXYZFURT'.each_char { |c1|
s1 = moves[c1][state]
'N123ABCXYZFURT'.each_char { |c2|
s2 = moves[c2][s1]
'N123ABCXYZFURT'.each_char { |c3|
s3 = moves[c3][s2]
s3[:ends_game] ||= s3[:global] == 0
results[c1+c2+c3] = s3
}
}
}
endingMoves = results.keys.select{|k| results[k][:ends_game]}
endingMoves.each{|k| results[k][:score] += 2*results[k][:me][FLP] - results[k][:me][UFL]}
$> << results.keys.shuffle.max_by {|k| results[k][:score]}
우리 중 어느 누구도 그들의 프로그램에 버그가 없다면 이것의 주요 알고리즘은 Mathias의 Oracle과 매우 유사합니다. 마지막 라운드 이전에 우리가 어떤 동전을 만들지 알 수 없다는 가정을 바탕으로, 우리는 어떤 종류의 동전을 완전히 무시하고 즉각적으로받은 포인트를 기준으로 현재 이동 세트를 평가합니다. 와. 14 3 = 2744 개의 가능한 이동 세트 만 있기 때문에 모든 점을 쉽게 시뮬레이션하여 가져올 점 수를 파악할 수 있습니다.
그러나 이동 세트가 게임을 끝내면 (전역 냄비를 0으로 줄이거 나, 50 라운드이고 우리가 마지막으로 움직일 수 있기 때문에), 마지막에 소유 한 동전을 고려 이동 세트의 값을 결정하는 이동 세트 나는 가능할 때마다 게임을 종료하는 것을 처음으로 고려했지만, 333
남은 동전이 9 개 밖에 남지 않으면 끔찍한 움직임이 발생합니다.
동일한 결과를 제공하는 이동 세트가 여러 개인 경우 임의의 이동 세트를 선택합니다. (게임 종료 이동 세트에 유리하게 편향되도록 이것을 변경할 수 있습니다.)
답변
오라클, Python 3
업데이트 : 회전보다 낮은 동전 더미를 선호하도록 다양한 시도의 순서가 변경되었습니다.
import sys
import itertools
from copy import deepcopy
MOVES_REQUIRED = 3
FLIPPED = 0
UNFLIPPED = 1
def filter_neighbors(neighbors, me, size):
limit = size - MOVES_REQUIRED
for data in neighbors:
i, _, flipped, unflipped = map(int, data.split('_'))
if MOVES_REQUIRED < (me - i) % size < limit:
continue # Skip neighbors that are too far away
yield i, [flipped, unflipped]
class Player:
def __init__(self, raw_data):
_, me, coins, *data = raw_data.split(';')
self.num_players = len(data)
self._me = int(me)
self._coins = int(coins)
self._state = dict(filter_neighbors(data, self._me, self.num_players))
def reset(self):
self.me = self._me
self.coins = self._coins
self.state = deepcopy(self._state)
self.my_state = self.state[self.me]
def invalid_move(self, move):
if move in 'NRT':
return False
if move in '123'[:self.coins]:
return False
flipped, unflipped = self.my_state
if flipped and move == 'U':
return False
if unflipped and move == 'F':
return False
if move in 'AXBYCZ'[:2 * unflipped]:
return False
return True
def N(self):
return 0
def one(self):
self.coins -= 1
self.my_state[UNFLIPPED] += 1
return -1
def two(self):
self.coins -= 2
self.my_state[UNFLIPPED] += 2
return -2
def three(self):
self.coins -= 3
self.my_state[UNFLIPPED] += 3
return -3
def A(self):
self.coins += 1
self.my_state[UNFLIPPED] -= 1
return 1
def B(self):
self.coins += 2
self.my_state[UNFLIPPED] -= 2
return 2
def C(self):
self.coins += 3
self.my_state[UNFLIPPED] -= 3
return 3
def X(self):
self.my_state[UNFLIPPED] -= 1
return 0
def Y(self):
self.my_state[UNFLIPPED] -= 2
return 0
def Z(self):
self.my_state[UNFLIPPED] -= 3
return 0
def R(self):
self.me = (self.me + 1) % self.num_players
flipped, unflipped = self.my_state = self.state[self.me]
return 2 * flipped - unflipped
def T(self):
self.me = (self.me - 1) % self.num_players
flipped, unflipped = self.my_state = self.state[self.me]
return 2 * flipped - unflipped
def F(self):
self.my_state[FLIPPED] += 1
self.my_state[UNFLIPPED] -= 1
return 2
def U(self):
self.my_state[FLIPPED] -= 1
self.my_state[UNFLIPPED] += 1
return -2
setattr(Player, '1', Player.one)
setattr(Player, '2', Player.two)
setattr(Player, '3', Player.three)
def scenarii(player):
for tries in itertools.product('FUABCXYZ123NRT', repeat=MOVES_REQUIRED):
player.reset()
points = 0
for try_ in tries:
if player.invalid_move(try_):
break
points += getattr(player, try_)()
else:
yield points, ''.join(tries)
if __name__ == '__main__':
player = Player(sys.argv[1])
print(max(scenarii(player))[1])
가능한 모든 단일 출력을 시도하고이 턴의 최대 점수를 산출하는 출력을 유지하십시오.
답변
탐욕스러운 회전, 루비
round, id, global, *players = ARGV[0].split(';')
round = round.to_i
id = id.to_i
global = global.to_i
players.map!{ |s| s.split('_').map(&:to_i) }
nplayers = players.size
my_pos = players.find_index { |i, p, f, u| i == id }
prev_p = players[my_pos-1]
next_p = players[(my_pos+1)%nplayers]
prev_score = 2*prev_p[2] - prev_p[3]
next_score = 2*next_p[2] - next_p[3]
take_from = prev_p
$><< '3'
if prev_score > next_score || prev_score == next_score && prev_p[3] > next_p[3]
$><< 'T'
else
$><< 'R'
take_from = next_p
end
if take_from[3] >= 3
$><< 'C'
elsif take_from[3] >= 1
$><< 'F'
else
$><< 'N'
end
이것은 ArtOfCode의 접근 방식과 매우 유사합니다.이 점은 어떤 이웃에서 더 많은 포인트를 얻을 수 있는지 확인 하고 회전 후 3 개 이상의 코인으로 끝나는 C
대신 선택 합니다 F
.
이 글을 작성한 후에는 가능한 한 복용하여 회전 전에 매번 모든 동작 중에서 최선을 선택하는 것이 더 나은 접근 방법이라고 확신합니다. 고정 된 “플립 핑 해제, 회전, 제거하기” 플 리핑되지 않은 “패턴).
이것은 또한 실제로 소유 한 동전으로 표현되는 암시 적 포인트를 고려하지 않습니다 (게임이 어쨌든 내 동전을 유지하지 못할 정도로 충분히 라운드를 지속 할 것이라는 가정에 근거 함).
답변
플리퍼, 파이썬 2
플리퍼는 동전을 모아 뒤집지 않은 채 뒤집기를 시도합니다. 플리퍼는 똑똑한 선수는 아니지만 게임에서 긍정적 인 힘이 되려고 노력합니다.
import sys, random
# process input data (not used here):
args = sys.argv[1].split(';')
rounds, myid, coins = map(int, args[:3])
players = [map(int, data.split('_')) for data in args[3:]]
# implement strategy using multiples of 'N123ABCXYZRTFU':
options = '12333FFFFFFFFFFF'
print ''.join(random.choice(options) for i in range(3))
플리퍼는 python flipper.py <arg>
뛰기 만하면됩니다 .
답변
SimpleBot, Python 3
SimpleBot은 간단합니다. 그는 한 가지 전략을 세웠으며 그 전략을 고수 할 것입니다.
실행하려면
python3 main.py
main.py
파일 내용 은 다음과 같습니다.
def main():
print("3RF")
if __name__ == "__main__":
main()
답변
밸런스, 루아
저울은 토큰에 잔액을 유지하려고 노력하여 누군가가 그에 대해 행동 R
하고 T
행동 할 경우의 손실을 최소화합니다 . 그는이 생활 방식이 진실한 것이라고 생각하고 뒤집어 놓거나 뒤집지 않은 동전의 균형을 잘 유지하지 못하는 사람에게는 시행해야하므로 자신과 가까운 사람은 점수를 잃을 수있는 즉시 처벌을받습니다.
실행하려면 다음 명령이 필요합니다.
lua balance.lua
파일 balance.lua에 다음 코드가 포함되어있는 경우 :
local datas={}
local arg=arg[1]..";"
-- parse the arguments
-- add some meta datas for debuging purpose/usefulness
arg:gsub("(.-);",function(c)
if not datas.round
then
datas.round=c+0
elseif not datas.myID
then
datas.myID=c+0
elseif not datas.coins
then
datas.coins=c+0
else
datas[#datas+1]={}
datas[#datas].repr=c
c=c.."_"
tmp={}
c:gsub("(.-)_",function(d) tmp[#tmp+1]=d end)
datas[#datas].id=tmp[1]+0
datas[#datas].points=tmp[2]+0
datas[#datas].flip=tmp[3]+0
datas[#datas].unflip=tmp[4]+0
if datas[#datas].id==datas.myID
then
datas.myOrder=#datas
datas.myDatas=datas[#datas]
end
end
end)
local actions=""
-- construct actions
for i=1,3
do
-- if we aren't in balance and can grab more coins
-- we do it
if #actions==0 and datas.myDatas.unflip<=datas.myDatas.flip/2 and datas.coins>=3
then
actions=actions.."3"
datas.myDatas.unflip=datas.myDatas.unflip+3
datas.coins=datas.coins-3
-- if we couldn't grab coins, but aren't in balance, we flip some coins
elseif datas.myDatas.unflip>datas.myDatas.flip/2
then
actions=actions.."F"
datas.myDatas.unflip=datas.myDatas.unflip-1
datas.myDatas.flip=datas.myDatas.flip+1
-- if we didn't have anything to do on our pile, let's punish
-- the fools who doesn't follow the great Balance principle
else
previous=datas.myOrder<2 and #datas or datas.myOrder-1
following=datas.myOrder>=#datas and 1 or datas.myOrder+1
lossPrev=-datas[previous].flip + 2*datas[previous].unflip
lossFoll=-datas[following].flip+ 2*datas[following].unflip
if lossFoll>0 and lossPrev>0
then
actions =actions.."N"
elseif lossFoll>=lossPrev
then
actions=actions.."T"
datas[following].unflip,datas[following].flip=datas[following].flip,datas[following].unflip
else
actions=actions.."R"
datas[previous].unflip,datas[previous].flip=datas[previous].flip,datas[previous].unflip
end
end
end
print(actions)
답변
관리인, 파이썬 3
그는 다른 플레이어들이이 동전으로 엉망을 청소하고 풀에 다시 넣습니다.
import sys;
def Parse(S):
T = S.split(';');
me = eval(T[1]);
N = len(T)-3;
A = list(map(lambda x: list(map(lambda y:int(y),T[3+((2*N+x+me)%N)].split('_'))),range(-3,4)));
Dic = {}
for a in A:
Dic[a[0]] = a[1:];
Dic[-1] = [me];
return Dic;
def Recursive(Dic,me,D):
if D==3: return '';
V = Dic[me];
N = max(Dic.keys());
Next = (me+1)%N;
Prev = (N+1+me)%N;
for i in range(3,0,-1):
if V[2]>=i:
Dic[me][2] = Dic[me][2]-i;
return chr((i-1)+ord('A'))+Recursive(Dic,me,D+1);
if V[1]>0:
Dic[me][1] = Dic[me][1]-1;
Dic[me][2] = Dic[me][2]+1;
return 'U'+Recursive(Dic,me,D+1);
if Dic[Next][2]>Dic[Prev][2]:
return 'T'+Recursive(Dic,Next,D+1);
return 'R'+Recursive(Dic,Prev,D+1);
Dic = Parse(sys.argv[1]);
me = Dic[-1][0];
print(Recursive(Dic,me,0));
그는 뒤집어 놓지 않은 동전을 모두 돌려 주려고 노력하고, 뒤집힌 동전이 붙어 있으면 뒤집을 것이고, 모든 동전을 제거하면 다른 사람을 얻게됩니다.