Предложение алгоритма для варианта игры Nim
Поэтому я пытаюсь создать игру Nim, но с небольшим поворотом:
Есть 3 башни в 3 разных высотах (kmn), где каждый игрок позволяет убрать 1 куб из одной башни или 1 куб из двух разных башен. Игра заканчивается, когда игрок не может играть.
Вы играете против ИИ, который просто останавливает свой ход, но игра предлагает вам оптимальный ход для победы. (Так что, если я буду играть только то, что мне подсказывает игра, я обязательно выиграю в 100% игр).
Я немного покопался и нашел разные способы написания режима "предложения" для игры, например с помощью XOR.
Но кажется, что это не работает 100% времени, а иногда я все равно проигрываю (потому что XOR относится только к игре, в которой вы можете удалить столько частей, сколько хотите из одной башни).
Что касается кода, я пишу это на C# и просто на практике язык, который я использую Linked List за каждую башню (head это самый "нижний" куб башни)
у меня есть
LinkedList towerA, towerB, towerC
Я ищу алгоритм, который мог бы помочь мне предложить ход для игрока, с точки зрения помощи игроку в оптимальной игре, метод XOR и алгоритмы метода 0-строк не помогли мне в этом варианте игры Nim, возможно, кто-то еще может предложить хороший алгоритм, который может решить эту проблему?
(Я не обязательно ищу кого-то, чтобы написать это для меня, просто чтобы помочь мне понять алгоритм, в котором я мог бы написать сам c#)
Заранее спасибо!
Мой код:
// Game start
while (!isWinnerFound)
{
// Player computer's turn
if (!isPlayerTurn)
{
PlayComputerTurn(towerA, towerB, towerC);
}
// Check if game ended
if (DidLose(towerA, towerB, towerC))
{
// Declare winner
isWinnerFound = true;
if (isPlayerTurn)
{
Console.WriteLine("Player #" + playerNum + " won!");
}
else
{
Console.WriteLine("Player #" + (3-playerNum) + " won!");
}
}
}
// Check if there is more than 1 tower to remove from
private static bool CanRemoveFromTwoTowers(LinkedList towerA, LinkedList
towerB, LinkedList towerC)
{
int sizeA, sizeB, sizeC;
int standingTowers = 0;
sizeA = towerA.Size();
sizeB = towerB.Size();
sizeC = towerC.Size();
if (sizeA > 0)
standingTowers++;
if (sizeB > 0)
standingTowers++;
if (sizeC > 0)
standingTowers++;
return (standingTowers > 1);
}
public static void PlayComputerTurn(LinkedList towerA, LinkedList towerB, LinkedList towerC)
{
Random random = new Random();
int numOfTowersToRemoveFrom = random.Next(1, 3); // Can only remove from 1 or 2 towers
bool cubesRemoved = false;
while (!cubesRemoved)
{
if (!CanRemoveFromTwoTowers(towerA, towerB, towerC))
{
numOfTowersToRemoveFrom = 1;
}
// Remove from only 1 tower
if (numOfTowersToRemoveFrom == 1)
{
int towerNum = random.Next(1, 4);
bool oneCubeRemoved = false;
// Make sure a cube is removed (for example if randomed an empty tower)
while (!oneCubeRemoved)
{
// Check which tower was removed
if (towerNum == 1)
{
if (towerA.GetLastNode() != null)
{
Console.WriteLine("Removed cube #" + towerA.DeleteLastNode().data + " from tower A");
oneCubeRemoved = true;
}
}
else if (towerNum == 2)
{
if (towerB.GetLastNode() != null)
{
Console.WriteLine("Removed cube #" + towerB.DeleteLastNode().data + " from tower B");
oneCubeRemoved = true;
}
}
else
{
if (towerC.GetLastNode() != null)
{
Console.WriteLine("Removed cube #" + towerC.DeleteLastNode().data + " from tower C");
oneCubeRemoved = true;
}
}
// Random a new tower to remove from
towerNum = random.Next(1, 4);
}
cubesRemoved = true;
}
else // Remove from 2 towers
{
int firstTowerNum = random.Next(1, 4);
int secondTowerNum = random.Next(1, 4);
while (secondTowerNum == firstTowerNum)
secondTowerNum = random.Next(1, 4);
int cubesRemovedNum = 0;
// Make sure a cube is removed (for example if randomed an empty tower)
while (cubesRemovedNum != 2)
{
// Check which tower was removed
if ((firstTowerNum == 1) || (secondTowerNum == 1))
{
if (towerA.GetLastNode() != null)
{
Console.WriteLine("Removed cube #" + towerA.DeleteLastNode().data + " from tower A");
cubesRemovedNum++;
}
}
if ((firstTowerNum == 2) || (secondTowerNum == 2))
{
if (towerB.GetLastNode() != null)
{
Console.WriteLine("Removed cube #" + towerB.DeleteLastNode().data + " from tower B");
cubesRemovedNum++;
}
}
if ((firstTowerNum == 3) || (secondTowerNum == 3))
{
if (towerC.GetLastNode() != null)
{
Console.WriteLine("Removed cube #" + towerC.DeleteLastNode().data + " from tower C");
cubesRemovedNum++;
}
}
// Random a new tower to remove from
firstTowerNum = random.Next(1, 4);
}
cubesRemoved = true;
}
// Random a new approach (either remove from 1 tower or from 2 towers)
numOfTowersToRemoveFrom = random.Next(1, 3);
}
}
ИСПРАВЛЕНО:
Алгоритм, который это решил, всегда гарантирует, что башни имеют одинаковую высоту, так что игрок всегда может выиграть рандомизирующий компьютер, вот код, который это сделал:
public static string SuggestPlayerTurn(LinkedList towerA, LinkedList towerB, LinkedList towerC, bool isGameStart)
{
string suggestion = "";
bool isTowerAGood, isTowerBGood, isTowerCGood;
isTowerAGood = (towerA.Size() % 2) == 0;
isTowerBGood = (towerB.Size() % 2) == 0;
isTowerCGood = (towerC.Size() % 2) == 0;
if ((isGameStart) && (isTowerAGood == isTowerBGood) && (isTowerBGood == isTowerCGood))
suggestion += "Be player #2\n";
else if (isGameStart)
suggestion += "Be player #1\n";
else
{
// If there is a tower with an odd height, remove from it.
// At ANY given time, the maximum number odd heights is 2.
if (!isTowerAGood)
suggestion += "Remove from tower A\t";
if (!isTowerBGood)
suggestion += "Remove from tower B\t";
if (!isTowerCGood)
suggestion += "Remove from tower C\t";
}
return suggestion + "\n";
}