Game theory
Game theory is a branch of modern mathematics and a mathematical tool used to study the phenomenon of competition. Game strategy is a set of actions that take into account all possible situations. Game theory has great value in artificial intelligence.
zero-sum game
In the zero sum game, the total interests of both parties are 0, and one party must lose the interests of the other party in order to maximize its own interests. Just as in a chess game, if one party wins, the other party must lose, and the sum of interests is 1 + (- 1) = 0
This requires that either party should maximize its own interests and minimize the interests of the other party. Therefore, when making decisions, we should not only consider our own best interests, but also consider the most unfavorable choices made by the other party
Minimax strategy
Minimax method is a strategy to analyze the zero sum game. In the game, each participant will make the most favorable choice for himself and the most unfavorable choice for the other party.
When playing chess, each chessboard layout can be represented as a node, and the adjacent nodes form a multi fork tree. Each layout will be beneficial to one party and unfavorable to the other. The degree of advantage of the node is called value.
Assuming that human beings compete with computers and assume that human beings are absolutely smart, in human rounds, he will choose the chess game that is the most unfavorable to computers, that is, the node with the lowest value. The computer will choose the node with the highest value to itself.
It is assumed that the value of each node is as follows
The decision-making process is as follows:
- The computer selects the node favorable to itself: 10 → 17
- Human selection of nodes unfavorable to computers: 17 → 8
- The computer selects the node beneficial to itself: 8 → 11
- Humans This decision-making process of constantly switching between maximum and minimum is called minimax strategy
This is a conservative strategy, because the computer will not try to take risks. It will assume that human beings make the most unfavorable choice every time, so as to ensure that the node value they finally get will not be too low
Tic tac toe algorithm
Chess game
The TicTac class is used to represent the chess game, and the chess pieces are saved in an array
/// <summary>
///Chess pieces
/// </summary>
public static class Player
{
public const int Non = 0;
public const int Computer = 1;
public const int Human = -1;
}
public class TicTac
{
public int num { get; set; }= 0;
/// <summary>
///Chessboard layout
/// </summary>
public int[,] chess { get; } = new int[,]
{
{0, 0, 0},
{0, 0, 0},
{0, 0, 0}
};
public TicTac(){}
public TicTac(TicTac copyFrom)
{
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
chess[i, j] = copyFrom.chess[i, j];
}
}
num = copyFrom.num;
}
/// <summary>
///Put down the pieces
/// </summary>
///< param name = "I" > location < / param >
///< param name = "J" > location < / param >
///< param name = "player" > chess player < / param >
///< returns > results < / returns >
public bool DropDown(int i, int j, int player)
{
if (chess[i, j] == Player.Non)
{
chess[i, j] = player;
num++;
return true;
}
return false;
}
/// <summary>
///Pick up the pieces
/// </summary>
///< param name = "I" > location < / param >
///< param name = "J" > location < / param >
///< returns > results < / returns >
public bool PickUp(int i, int j)
{
if (chess[i, j] != Player.Non)
{
chess[i, j] = Player.Non;
num--;
return true;
}
return false;
}
/// <summary>
///Return to the winner
/// </summary>
///< returns > winner < / returns >
public int GetWinner()
{
//The winner only needs to judge whether the sum of the three figures is ± 3
//Check line
if (Math.Abs(chess[0, 0] + chess[1, 0] + chess[2, 0]) == 3) return chess[0, 0];
if (Math.Abs(chess[0, 1] + chess[1, 1] + chess[2, 1]) == 3) return chess[0, 1];
if (Math.Abs(chess[0, 2] + chess[1, 2] + chess[2, 2]) == 3) return chess[0, 2];
//Check column
if (Math.Abs(chess[0, 0] + chess[0, 1] + chess[0, 2]) == 3) return chess[0, 0];
if (Math.Abs(chess[1, 0] + chess[1, 1] + chess[1, 2]) == 3) return chess[1, 0];
if (Math.Abs(chess[2, 0] + chess[2, 1] + chess[2, 2]) == 3) return chess[2, 0];
//Check diagonal
if (Math.Abs(chess[0, 0] + chess[1, 1] + chess[2, 2]) == 3) return chess[0, 0];
if (Math.Abs(chess[0, 2] + chess[1, 1] + chess[2, 0]) == 3) return chess[0, 2];
//There is no winner
return Player.Non;
}
public bool isEnd()
{
if (GetWinner() != Player.Non || num == 9)
{
return true;
}
else
{
return false;
}
}
}round
A round is represented by a node, which includes chess game, value, child nodes, players and placement
The child node contains all possible situations after the current round. The player is the player's turn in the current round, and the placement position is the last move position of the player in the previous round
/// <summary>
///Node class
/// </summary>
public class Node
{
/// <summary>
///Chess game
/// </summary>
public TicTac ticTac;
/// <summary>
///Value
/// </summary>
private int? value = null;
/// <summary>
///Child node
/// </summary>
public List<Node> childNodes = null;
/// <summary>
///Chess player
/// </summary>
public int player = Player.Non;
public Point lastDrop = null;
private Node(){}
public Node(TicTac ticTac, int player)
{
Debug.Assert(player == Player.Computer || player == Player.Human);
this.ticTac = new TicTac(ticTac);
this.player = player;
GetValue();
}
public Node(Node lastNode, Point drop)
{
this.ticTac = new TicTac(lastNode.ticTac);
this.player = -lastNode.player;
this.lastDrop = drop;
ticTac.DropDown(drop.i, drop.j, lastNode.player);
GetValue();
}
/// <summary>
///Calculate the value of the current node
///If the player is a computer, the maximum value of the child node is returned
///If the player is human, the minimum value of the child node is returned
/// </summary>
public int GetValue()
{
//The value has been calculated
if (value != null) return (int) value;
//The outcome is divided
int winner = ticTac.GetWinner();
if (winner != Player.Non)
{
value = winner == Player.Computer ? 10 : -10;
return (int) value;
}
//The chessboard is full
if (ticTac.num == 9)
{
value = 0;
return (int) value;
}
//The child node is not initialized. Construct the child node
if (childNodes == null)
{
childNodes = new List<Node>();
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
if (ticTac.chess[i, j] == Player.Non)
{
Node child = new Node(this, new Point(i, j));
childNodes.Add(child);
}
}
}
}
if (player == Player.Computer)
{
//The current player is a computer and returns the maximum value
int maxValue = Int32.MinValue;
//Find the maximum value from the minimum value of the child node
foreach (Node item in childNodes)
{
if (item.GetValue() > maxValue)
{
maxValue = item.GetValue();
}
}
value = maxValue;
}
else
{
int minValue = Int32.MaxValue;
foreach (Node item in childNodes)
{
if (item.GetValue() < minValue)
{
minValue = item.GetValue();
}
}
value = minValue;
}
return (int) value;
}
public Node SearchChildByPoint(int i, int j)
{
foreach (Node item in childNodes)
{
if (item.lastDrop.i == i && item.lastDrop.j == j) return item;
}
return null;
}
}Chess game value
For a chess game, if the game is over, the value is calculated according to the winner. If the winner is a computer, the value is 10; If the winner is human, the value is - 10; If there is a draw, the value is 0
If the game is not over yet, drop children in all empty positions on the chess game and get all possible child nodes. If the current player is human, the value of the node is the minimum value of the value of the child node, because human will make the most unfavorable choice to the computer. If the current player is a computer, the value of the node is the maximum value of the child node, because the computer will make the most favorable choice for itself.
Chess code
public class Point
{
public int i { get; set; }
public int j { get; set; }
public Point(int i, int j)
{
this.i = i;
this.j = j;
}
}
class Program
{
private const string space = " ";
private static Node node;
static void Main(string[] args)
{
Play();
}
static void Play()
{
Console.Write("First hand(1:computer, 0:human beings):");
int start = int.Parse(Console.ReadLine());
//Initialize header node
Console.WriteLine("Initializing...");
node = new Node(new TicTac(), start == 1 ? Player.Computer : Player.Human);
Console.WriteLine("End of initialization...");
Point drop = null;
while (!node.ticTac.isEnd())
{
if (node.player == Player.Computer)
{
drop = WaitComputerDrop();
}
else
{
drop = WaitHumanDrop();
}
Drop(drop.i, drop.j);
}
Console.WriteLine("Game over, game results");
switch (node.ticTac.GetWinner())
{
case Player.Computer:
Console.WriteLine("Computer wins!");
break;
case Player.Human:
Console.WriteLine("Human victory!");
break;
case Player.Non:
Console.WriteLine("it ends in a draw!");
break;
}
}
static void PrintTicTac()
{
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
string s;
switch (node.ticTac.chess[i, j])
{
case Player.Computer:
s = "0";
break;
case Player.Human:
s = "1";
break;
default:
s = "x";
break;
}
Console.Write(s + space);
}
Console.WriteLine();
}
}
static Point WaitHumanDrop()
{
Console.WriteLine("Please enter the drop position[1~3,1~3],for example: 2,3");
string line = Console.ReadLine();
string[] s = line.Split(",");
Point p = new Point(int.Parse(s[0]) - 1, int.Parse(s[1]) - 1);
return p;
}
static Point WaitComputerDrop()
{
Node maxNode = null;
int MaxValue = Int32.MinValue;
foreach (Node item in node.childNodes)
{
if (item.GetValue() > MaxValue)
{
maxNode = item;
MaxValue = item.GetValue();
}
}
return new Point(maxNode.lastDrop.i, maxNode.lastDrop.j);
}
static void Drop(int i, int j)
{
Console.WriteLine("------------");
Console.Write("chess player:" + (node.player == Player.Computer ? "computer" : "human beings") + ",");
node = node.SearchChildByPoint(i, j);
Console.WriteLine("Drop point:(" + (i+1) + "," + (j+1) + ")");
PrintTicTac();
Console.WriteLine("------------");
}
}