게임 이론 알고리즘 : 진행 방법

Question

예 : Permutation Game (interviewstreet.com). 나는 그러한 질문을 어떻게 진행해야하는지 알고 싶다.

P .: 소수의 포인터만으로 전체 알고리즘을 게시하면 안됩니다.

Answer 1

내가 설정 한 후 작은 N과 작은 게임과 임의의 순열과 완전한 알파 - 베타 트리을 그릴 것입니다 ... 가능한 모든 움직임의

http://en.wikipedia.org/wiki/Alpha-beta_pruning

하고 하단 작업 각 포인트에서 각 플레이어에 대해 최적의 선택을합니다.

그런 다음 패턴을 보게되면 거기에서 일반화하십시오. 게임 이론 용어에서

당신은 Subgame 완벽한 균형을 찾을 수 뒤로 유도를 사용해야합니다.

Answer 2

펜과 종이

사용 펜과 종이, 정확하게, 다음 게임에 대한 모든 가능한 전략을 생각하는 게임의 규칙을 알고 있어야합니다.

이와 같은 비교적 간단한 문제에 대해서는 게임이 승리 할 때 한 번에 한 걸음 씩 올린 다음 그 단계를 만든 플레이어가 더 나은 단계를 밟을 수는 없다는 것을 확인하십시오. 이것이 최적 조건입니다.

더 복잡한 문제의 경우 게임 이론에서 위키 백과를 읽으십시오.

Answer 3

N은 다소 적습니다. 각 턴에는 각 숫자에 대해 두 가지 가능성이 있습니다 : 그 숫자를 제거하거나 그 숫자를 제거하지 마십시오. 두 가지 방법을 시도해보고 각 테스트 사례에 대해 O(N*2^N) 알고리즘을 생성하십시오. 실제로 모든 숫자가 제거되기 전에 게임이 끝나기 때문에 게임의 순위가 낮아질 수 있습니다.

그래서 숫자 제거의 모든 가능성을 시도하는 백 트랙 기능을 원하고 앨리스가 이기면 1, 밥이 이기면 2을 반환합니다. k (첫 번째 깊이는 k = 0)이고 k % 2 = 0이면 앨리스의 차례입니다. 모든 즉각적인 재귀 호출 (깊이가 k + 1 인 경우)이 1이면 그녀가 이깁니다. 적어도 하나가 2을 반환하면 Bob이 이기기위한 최소한 하나의 방법이 있기 때문에 그녀는 잃습니다.

예제 1 3 2 실행 :

k = 0 - Alice removes 1: 
    k = 1 - Bob removes 3 => Bob wins because only 2 remains 
      - Bob removes 2 => Bob wins because only 3 remains (note: this step 
      is not needed, as Bob already proved he can win at this k = 1) 
     - Alice removes 3 => Alice wins because 1 2 is increasing 
     - Alice removes 2 => Alice wins because 1 3 is increasing 

그래서 앨리스 (모두가 최적의 상태로 재생할 때) 그녀가 3 또는 첫 번째 이동에 2 제거하면이 두의 재귀 가지 결코 포기하지 않기 때문에 확실히이기는 전략을 가지고 밥 우승자.5 3 2 1 4 (부분 실행)에서 실행

예 :

k = 0 - Alice removes 5 
    k = 1 - Bob removes 3 
     k = 2 - Alice removes 2 => 1 4 => Alice wins 
    k = 1 - Bob removes 2 
     k = 2 - Alice removes 3 => 1 4 => Alice wins 
    k = 1 - Bob removes 1 
     k = 2 - Alice removes 3 => 2 4 => Alice wins 
    k = 1 - Bob removes 4 
     k = 2 - Alice removes 3 
      k = 3 - Whatever Bob removes, he wins 
     k = 2 - Alice removes 2 
      k = 3 - Whatever Bob removes, he wins 
     k = 2 - Alice removes 1 
      k = 3 - Whatever Bob removes, he wins 
    ... 

당신이 볼 수 있듯이,이 적어도 하나의 Bob가 5을 제거하여 Alice 시작하면 경력이 끝날위한 방법. 그녀의 다른 가능성에 대해서도 똑같이한다면, 아마 같은 결과를 얻게 될 것입니다. 따라서, 그가 최적으로 뛰면 분명히이기는 사람은 Bob입니다.