Как разработать стратегию и алгоритм для игры в золотой ящик

Проблема с золотым ящиком (подход)

В ряд поставлено n золотых коробок, в каждой из которых разное количество золотых монет. 2 игрока играют в игру, цель которой - собрать максимальное количество золотых монет. Каждый игрок может видеть, сколько монет находится в каждой коробке, но может получить коробку только с любого конца в свой ход. Разработайте стратегию так, чтобы победил Player1 (при условии, что оба игрока играют умно)

Эту проблему задали в интервью Amazon. Я пробовал такой подход:

#include<stdio.h>
int max(int a, int b) {
    return a>b?a:b;
}
int maxCoins(int arr[], int i, int j, int turn) {
    if(i==j) {
        if(turn == 1) return arr[i];
        else return 0;
    }
    if(turn) {
        return max(arr[i] + maxCoins(arr,i+1,j,0),arr[j] + maxCoins(arr,i,j-1,0));
    } else {
        if(arr[i]>arr[j])
        return maxCoins(arr,i+1,j,1);
        else
        return maxCoins(arr,i,j-1,1);
    }
}    
int main() {
    int arr[10] = {6,7,4,1,10,5,4,9,20,8}; //{2,3,4,5,6,7,8,9,10,11};
    printf("%d\n",maxCoins(arr,0,9,1));
}

Но я считаю, что это неправильно, так как player2 тоже шустро играет. Пожалуйста, помогите с тем, что мне не хватает.


c algorithm dynamic-programming game-theory
person Sanjay Verma    schedule 22.03.2014    source источник
comment
Та же проблема - Понимание решения для поиска оптимальной стратегии игры, включающей сбор горшков с золотом   -  person Bernhard Barker    schedule 22.03.2014

Ответы (1)


arrow_upward
0
arrow_downward

Я добрался до решения, просто был близок. Вот что я упустил:

«Противник намеревается выбрать монету, которая оставляет пользователю минимальную ценность».

Вот обновленное решение:

#include<stdio.h>
int max(int a, int b) {
    return a>b?a:b;
}
int min(int a, int b) {
    return a<b?a:b;
}
int maxCoins(int arr[], int i, int j, int turn) {
    int a,b;
    if(i==j) {
        if(turn == 1) return arr[i];
        else return 0;
    }
    if(turn) {
        a = arr[i] +maxCoins(arr,i+1,j,0);
        b = arr[j] + maxCoins(arr,i,j-1,0);
        return max(a,b);
    } else {
        return min(maxCoins(arr,i+1,j,1), maxCoins(arr,i,j-1,1));
    }
}
int main() {
    int arr[4] = {8, 15, 3, 7 };//{6,7,4,1,10,5,4,9,20,8}; //{2,3,4,5,6,7,8,9,10,11};
    printf("%d\n",maxCoins(arr,0,3,1));
}

По этой ссылке обсуждается стратегия: http://www.geeksforgeeks.org/dynamic-programming-set-31-optimal-strategy-for-a-game/

person Sanjay Verma    schedule 22.03.2014