Алгоритм гарантирования выигрыша (или розыгрыша) в ряду монет

Question

В ряду из n монет (> = 0, n = четный) каждый игрок (Амир и Тамар) должен выбрать монету из одного из краев ряда. Игрок с наибольшим количеством выигрывает. Нужно гарантировать хотя бы ничью Амиру. Амир идет первым. Мой алгоритм для этого заключался в том, чтобы заставить Амира взять самую большую монету, если только НЕМЕДЛЕННО СЛЕДУЮЩАЯ монета не гарантирует потери (т.е. если Амир заберет все максимально возможные оставшиеся монеты - он ПОСТОЯННО проиграет). Как вы думаете, это правильно? Если это так, я был бы признателен, если бы вы взглянули на мой код (Java) - случайные выигрыши Амир / Тамар.

//This method takes the largest of the two coins providing the coin adjacent to the larger coin leaves a chance of winning assuming
//worse case scenario - all highest (remaining numbers) are picked by - Tamar.
public static void win(int[] arr){
    int beginning = 0, end=arr.length-1, sumAmir = 0, sumTamar = 0;
    int[] arrClone = arr.clone();
    java.util.Arrays.sort (arrClone, beginning, end+1);
    while (beginning<end){
        if ((arr[end]>=arr[beginning] && !loses(arr,arrClone, end-1,sumAmir,sumTamar,beginning,end))
                || (arr[end]<arr[beginning] && loses(arr, arrClone,beginning+1,sumAmir,sumTamar,beginning,end))) {
            System.out.println ("Amir took " + arr[end]);
            sumAmir+=arr[end];
            end--;
        }
        else{
            System.out.println ("Amir took "+ arr[beginning]);
            sumAmir+=arr[beginning];
            beginning++;
        }
        if (arr[beginning]> arr[end]){
            System.out.println ("Tamar took " + arr[beginning]) ;
            sumTamar+=arr[beginning];
            beginning++;
        }
        else{
            System.out.println ("Tamar took " + arr[end]) ;
            sumTamar+=arr[end];
            end--;
        }
    }
    System.out.println ("Amir total " + sumAmir + "\nTamar total " + sumTamar);
}
private static boolean loses(int[] arr,int[] arrClone, int place, int sumAmir, int sumTamar, int beginning, int end) {
    int currPlace =arr[place];
    if (end - beginning == 1) {
        return false;
    }
    if (place == beginning + 1) {
        sumAmir += arr[beginning];
        beginning += 2;
    } else {
        sumAmir += arr[end];
        end -= 2;
    }

    //Sums lowest & highest halves of (sorted) array. (excluding checked duo)
    int lowestValsSum = 0;
    int k=0;
    int highestValsSum = 0;
    for (int i = beginning; i < (beginning+end)/2 + 1; i++) {
        k++;
        lowestValsSum+=arrClone[i];
        highestValsSum+=arrClone[end-k];
    }
    return sumAmir + highestValsSum < sumTamar + currPlace + lowestValsSum;
}

TX

Answer 1

Вы можете попытаться реализовать минимаксный алгоритм для своей игры, чтобы гарантировать оптимальную игру для своего игрока (победа или ничья).