🎪 퍼레이드 AI

퍼레이드 AI는 퍼레이드 게임에 사람 플레이어 외에 AI 봇을 추가하는 기능을 개발하기 위한 프로젝트이며, 이 페이지는 간단한 설명과 튜토리얼을 포함합니다. 퍼레이드 게임을 플레이하는 여러가지 가능한 알고리즘을 작성해보고, 경쟁에 참여해 가장 높은 점수를 획득하세요!

📌 시작하기에 앞서

AI 봇 개발에 사용되는 프로그래밍 언어는 JavaScript입니다. Python을 사용하면 안되는걸까? 하는 생각이 든다면, 다음 인용구를 떠올려 봅시다.

"Any application that can be written in JavaScript, will eventually be written in JavaScript."

제프 앳우드, Stack Overflow 공동 창립자

당신은 할 수 있습니다.

⛳️ 시작하기

퍼레이드를 플레이하는 봇은 단 두 개의 함수로 구현할 수 있습니다. 나의 차례에 핸드에서 무슨 카드를 낼지 결정하는 함수 play_card()와, 마지막 라운드가 끝나고 핸드에서 무슨 카드 두 장을 내려놓을지 결정하는 함수 play_hidden()입니다.

• play_card()의 결과값은 { 0, 1, 2, 3, 4 } 중의 하나입니다.
• play_hidden()의 결과값은 { [0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3] } 중의 하나입니다 (배열내 순서는 무관합니다).

예를 들어, 언제나 무작위로 플레이하는 모자장수의 알고리즘은 다음과 같습니다.

function play_card() {
  // Math.random()은 [0, 1) 구간의 실수를 반환함
  return Math.floor(Math.random() * 5);
}

function play_hidden() {
  // [0, 1, 2, 3]을 셔플하여 앞의 두 원소만 취함
  return [0, 1, 2, 3].sort(() => Math.random() - .5).slice(0, 2);
}

🔭 관측 가능한 정보 이용하기

무작위로 플레이하는 것보다 잘하고 싶다면, 주어진 정보를 활용해야 합니다. play_card()와 play_hidden() 함수에는 사실 첫번째이자 유일한 인자(state)로 플레이어 입장에서 현재 게임에서 관측 가능한 정보가 주어집니다.

이 인자(state)에는 다음과 같은 정보가 들어 있습니다.

위의 예시는 게임을 시작하고 앞서 다른 사람들(player: 1, player: 2)이 한번씩, 총 두턴 플레이 후 내가 플레이할 차례인 상황입니다. 플레이어의 구분은 나로부터 0으로 시작해 시계 방향으로(= 이어서 플레이하는 차례대로) 1, 2, ..., (num_players - 1)이 됩니다. 게임의 첫 턴 플레이어에 관계 없이 내가 player: 0이며, 전체 플레이어가 지금까지 획득한 점수를 나타내는 scores에서도 0번째 원소인 배열(scores[0])이 나의 점수를 나타냅니다.

parade, scores, hand, history.card, history.scores 등에 등장하는 숫자는 0에서 65 사이로, 각 숫자는 카드 한 장의 색깔과 크기를 의미합니다. 숫자를 11로 나눈 몫이 색깔을 나타내고 11로 나눈 나머지가 크기를 나타냅니다. 색깔은 숫자를 11로 나눈 몫에 따라 각각 0:파랑, 1:초록, 2:노랑, 3:빨강, 4:보라, 5:검정입니다. 예를 들어, scores[1] = [45, 55]는 player: 1의 점수 보라색 1과 검정색 0 카드를 의미합니다.

parade와 hand의 정보를 조합하면 손패의 { 0, 1, 2, 3, 4 } 중 어떤 카드를 내는 것이 유리할지 계산할 수 있습니다. 또한, scores를 통해 게임의 판세와 향방을 가늠할 수 있습니다.

🏹 상황에 따라 다른 전략 사용하기

상술한 것과 같이, 인자의 정보를 이용해 세부적인 전략을 구상할 수 있습니다. 아래는 이해를 돕기 위한 JavaScript 구문의 예시입니다.

1. 내 점수에서 특정 색깔(노랑)의 카드 개수

// 긴 버전
var color = 2,
    counts = 0;

for (var i = 0; i < state.scores[0].length; i += 1) {
  // parseInt는 실수의 정수부만을 취함
  if (parseInt(state.scores[0][i] / 11) === color) {
    counts += 1;
  }
}

// 짧은 버전
var counts = state.scores[0].filter(e => parseInt(e / 11) === 2).length;

2. 내 손패에 있는 카드의 크기의 최소값

// 긴 버전
var minimum = Infinity;     // Infinity 대신 충분히 큰 임의의 수를 사용해도 됨

for (var i = 0; i < state.hand.length; i += 1) {
  var size = state.hand[i] % 11;
  if (size < minimum) {
    minimum = state.hand[i] % 11;
  }
}

// 짧은 버전
var minimum = Math.min.apply(null, state.hand.map(e => e % 11));

// 또다른 짧은 버전
var minimum = state.hand.map(e => e % 11).reduce((a, b) => Math.min(a, b), Infinity);

3. 특정 카드(빨강색 9)를 낼 때 퍼레이드에서 가져오는 카드

// 긴 버전
var card = 42,
    expected_scores = [];

var color = parseInt(card / 11),
    size = card % 11;

for (var i = 0; i < state.parade.length - size; i += 1) {
  if (parseInt(state.parade[i] / 11) === color || state.parade[i] % 11 <= size) {
    expected_scores.push(state.parade[i]);
  }
}

// 짧은 버전
var card = 42;
var expected_scores = state.parade
  .filter(e => state.parade.indexOf(e) < state.parade.length - (card % 11))         // 마스킹
  .filter(e => parseInt(e / 11) === parseInt(card / 11) || e % 11 <= card % 11);    // 뛰쳐나간 카드

4. 색깔별로 현재 독점하기 위해 필요한 카드 개수

var threshold = [];

for (var i = 0; i < 6; i += 1) {
  var counts = state.scores.map(e => e.filter(e => parseInt(e / 11) === i)).map(e => e.length),
      minimum = counts.reduce((a, b) => Math.min(a, b), 11),
      maximum = counts.reduce((a, b) => Math.max(a, b), 0);

  threshold.push(state.num_players === 2 ? minimum + 2 : maximum);     // 2인일 경우 최소값+2로, 그외 최대값으로
}

5. 색깔별로 지금까지 위치가 확인된 카드 개수

// 긴 버전
var disclosed = Array(6).fill(0);

for (var i = 0; i < state.parade.length; i += 1) {
  // 퍼레이드
  var color = parseInt(state.parade[i] / 11);
  disclosed[color] += 1;
}

for (var i = 0; i < state.num_players; i += 1) {
  // 각 플레이어의 점수 카드
  for (var j = 0; j < state.scores[i].length; j += 1) {
    var color = parseInt(state.scores[i][j] / 11);
    disclosed[color] += 1;
  }
}

for (var i = 0; i < state.hand.length; i += 1) {
  // 내 손패
  var color = parseInt(state.scores[i] / 11);
  disclosed[color] += 1;
}

// 짧은 버전
var disclosed = Array(6).fill(0).map((e, i) => state.parade
  .concat(state.scores.reduce((a, b) => a.concat(b), []))
  .concat(state.hand)
  .filter(e => parseInt(e / 11) === i)
  .length)

Array 메소드의 인자로 쓰인 화살표 함수의 표기법에 대해서는 다음 링크 의 설명을 참고해주세요.

이제 실제 state 인자를 사용하도록 작성된 AI 봇을 살펴봅시다. 다음은 항상 이번 턴에 획득하는 점수 카드의 합을 최소화하도록 플레이하는 여왕의 알고리즘입니다. 주어진 턴에 퍼레이드에 깔린 카드와 손패를 비교해 최소의 점수만을 가져오려 하고, 마지막에 두 장 내려놓을 카드를 고를 때도 크기가 작은 카드를 골라 내려놓습니다. 대체로 점수를 적게 얻겠지만, 색깔 독점 규칙을 포함해도 플레이를 잘 할지는 두고 봐야 합니다. 그리고 매턴 눈앞의 이익만을 추구하는 것 또한 여왕의 약점입니다.

function play_card(state) {
  var adds_numbers_sum = state.hand.map(card =>
    state.parade
      .filter(e => state.parade.indexOf(e) < state.parade.length - (card % 11))         // 마스킹
      .filter(e => parseInt(e / 11) === parseInt(card / 11) || e % 11 <= card % 11)     // 뛰쳐나간 카드
      .map(e => e % 11)                                                                 // 의 크기
      .reduce((a, b) => a + b, 0));                                                     // 의 합

  var min = Math.min.apply(null, adds_numbers_sum),
      argmin = adds_numbers_sum.indexOf(min);

  return argmin;
}

function play_hidden(state) {
  var numbers = state.hand.map(e => e % 11 + Math.random());        // 노이즈 안 더해주면 [0, 0] 이따위로 선택

  var sorted = Array.from(numbers).sort((a, b) => a - b),           // sort는 inplace 메소드라 deep copy
      argmins = sorted.slice(0, 2).map(e => numbers.indexOf(e));

  return argmins;
}

이제 당신은 퍼레이드의 게임 플레이 알고리즘을 작성할 준비가 모두 끝났습니다. 행운을 빕니다!

💣 주의사항

함수의 결과값이 유효하지 않은 경우(예시: play_card()의 결과값이 59) 또는 계산시간이 1초를 초과하거나 지나치게 많은 메모리를 사용하는 경우 경쟁에서 제외됩니다. 작성한 알고리즘은 본인만 조회 또는 삭제 가능합니다. 보안상 이유로 eval, Function, setTimeout, setInterval, promise, prototype, document 등의 키워드 사용을 금지합니다.