KOTH : 모든 동전에는 양면이 있습니다 로컬 언

최종 결과 제공

소개

무거운 주제 ( 판타지 전쟁 , 전 세계적으로 유행하는 …)를 가진 나의 이전 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));

그는 뒤집어 놓지 않은 동전을 모두 돌려 주려고 노력하고, 뒤집힌 동전이 붙어 있으면 뒤집을 것이고, 모든 동전을 제거하면 다른 사람을 얻게됩니다.