java - 保证赢(或平)的硬币排问题的算法

Question

在一排 n 个硬币(>=0，n=偶数)中，每个玩家(Amir 和 Tamar)必须从该排的边缘之一挑选一枚硬币。金额最大的玩家获胜。需要保证至少给阿米尔打平。阿米尔先走。我的算法是让阿米尔拿走最大的硬币，除非紧随其后的硬币保证损失(即，如果阿米尔拿走所有可能的最大剩余硬币 - 他仍然会输)。你认为这是对的吗？如果是这样，如果您看一下我的代码(Java)，我将不胜感激 - 随机获胜 Amir/Tamar。

//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

您可以尝试为您的游戏实现极小极大算法，以保证您的玩家获得最佳游戏体验(获胜或平局)。