|
正好赶上c#实验和android实验结课大作业，同时需要提交，就都写了一个井字棋的AI
一.因为只有3*3的小数据量，电脑AI可以直接枚举出所有可能情况
二.算是一种简单的博弈问题吧，所以先来简单说一下枚举的核心函数dfs()
1.两个人，A,B,一人走一步；
2.分别有三种状态，必胜态，平局态，和必败态；
3.转移方程：
如果A无论如何走，B都可以找到必胜态，那么A便是必败态；
如果A有一种走法，使得B达到必败态，那么A便是必胜态；
如果A有几种走法，分别可以使得B达到必胜态和必败态，那么如果我是A，我肯定要让B必败，所以A依旧是必胜态
如果A有几种走法，分别使得B达到必平，和必败，那么我至少不能让B获胜，所以，我走让B必平态的走法，我也是
必平态
4.终止条件
如果没有棋可走了，并且没有分出胜负，那么是一个必平态，递归终止
如果A发现B出现必败态，那么这是一个A的必胜态，递归终止
如果A尝试了所有的走法，B都是必胜态，那么A必败，递归终止
贴出C#的搜索代码
int dfs(bool computer)
{
int state = -1,n = 0;
for (int x = 0; x < 3; x++)
for (int y = 0; y < 3; y++) if (cal[y, x] != 0)
n++;
if (n == 9) return 0;
for (int x = 0; x < 3; x++)
for (int y = 0; y < 3; y++) if(cal[y, x] == 0)
{
if (computer) cal[y, x] = 2;
else cal[y, x] = 1;
if (win(cal))
{
cal[y, x] = 0;
return 1;
}
int cur = dfs(!computer);
if (cur == -1)
{
cal[y, x] = 0;
return 1;
}
else if (cur == 0) state = 0;
cal[y, x] = 0;
}
return state;
}
命令行实现的c#井字棋程序
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace 井字棋ai
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("if you want to go first type 1,or type 0");
Console.WriteLine("first people named Alice");
Console.WriteLine("second people named Bob");
int flag = Convert.ToInt32(Console.ReadLine());
while(true)
{
XO game = new XO(flag);
game.play();
}
}
}
class XO
{
int[,] num = new int[5, 5];
int[,] cal = new int[5, 5];
int first;
public XO(int cur)
{
for (int i = 0; i < 5; i++)
for (int j = 0; j < 5; j++)
cal[i, j] = num[i, j] = 0;
first = cur;
}
bool win(int [,] cur)
{
for (int i = 0; i < 3; i++)
if (cur[i, 0] == cur[i, 1] && cur[i, 1] == cur[i, 2] && cur[i, 2] != 0)
return true;
for (int i = 0; i < 3; i++)
if (cur[0, i] == cur[1, i] && cur[1, i] == cur[2, i] && cur[2, i] != 0)
return true;
if (cur[0, 0] == cur[1, 1] && cur[1, 1] == cur[2, 2] && cur[2, 2] != 0) return true;
else if (cur[0, 2] == cur[1, 1] && cur[1, 1] == cur[2, 0] && cur[2, 0] != 0) return true;
return false;
}
int dfs(bool computer)
{
int state = -1,n = 0;
for (int x = 0; x < 3; x++)
for (int y = 0; y < 3; y++) if (cal[y, x] != 0)
n++;
if (n == 9) return 0;
for (int x = 0; x < 3; x++)
for (int y = 0; y < 3; y++) if(cal[y, x] == 0)
{
if (computer) cal[y, x] = 2;
else cal[y, x] = 1;
if (win(cal))
{
cal[y, x] = 0;
return 1;
}
int cur = dfs(!computer);
if (cur == -1)
{
cal[y, x] = 0;
return 1;
}
else if (cur == 0) state = 0;
cal[y, x] = 0;
}
return state;
}
void people()
{
int x, y;
do
{
Console.WriteLine("please type x ----- [0,2]");
x = Convert.ToInt32(Console.ReadLine());
Console.WriteLine("please type y ------[0,2]");
y = Convert.ToInt32(Console.ReadLine());
} while (num[y, x] != 0);
Console.WriteLine("what you typed is (" + x + "," + y + ")");
num[y, x] = 1;
}
void computer()
{
int ansx = -1, ansy = -1,state;
for (int x = 0; x < 3; x++)for (int y = 0; y < 3; y++)
{
if (num[y, x] == 0)
{
ansx = x;
ansy = y;
num[y, x] = 2;
if (win(num))
{
Console.WriteLine("what computer typed is (" + x + "," + y + ")");
return;
}
num[y, x] = 0;
}
cal[y, x] = num[y, x];
}
for (int x = 0; x < 3; x++)for (int y = 0; y < 3; y++)
{
if (num[y, x] == 0)
{
num[y, x] = 1;
if(win(num))
{
num[y, x] = 2;
Console.WriteLine("what computer typed is (" + x + "," + y + ")");
return;
}
num[y, x] = 0;
}
}
for (int x = 0; x < 3; x++)
for (int y = 0; y < 3; y++) if (cal[y, x] == 0)
{
cal[y, x] = 2;
// 2 is computer
// 1 is people
if(win(cal))
{
num[y, x] = 1;
Console.WriteLine("what computer typed is (" + x + "," + y + ")");
return;
}
state = dfs(false);
Console.WriteLine(x + " x y " + y + " state " + state);
//false is people;
//true is computer
if(state == 0)
{
ansx = x;
ansy = y;
}
else if (state == -1)
{
num[y, x] = 2;
Console.WriteLine("what computer typed is (" + x + "," + y + ")");
return;
}
cal[y, x] = 0;
}
num[ansy, ansx] = 2;
Console.WriteLine("what computer typed is (" + ansx + "," + ansy + ")");
}
int solve()
{
int ans = 0;
if (first == 0)
{
num[1, 1] = 2;
ans++;
Console.WriteLine("1 x y 1");
}
while(!win(num) && ans != 9)
{
ans++;
if ((ans & 1) == first)people();
else computer();
}
if(win(num))return (ans & 1);
else return -1;
}
public void play()
{
int state = solve();
if (state == 1) Console.WriteLine("Alice");
else if (state == 0) Console.WriteLine("Bob");
else Console.WriteLine("Draw");
}
}
}
以及java的实现
import java.util.Scanner;
class Main
{
public static void main(String [] args)
{
System.out.println("if you want to go first type 1,or type 0");
System.out.println("first people named Alice");
System.out.println("second people named Bob");
Scanner sc = new Scanner(System.in);
int flag = sc.nextInt();
while(true)
{
XO game = new XO(flag);
game.play();
}
}
}
class XO
{
int[][] num = new int[5][5];
int[][] cal = new int[5][5];
public int first;
public XO(int cur)
{
for (int i = 0; i < 5; i++)
for (int j = 0; j < 5; j++)
cal[i][j] = num[i][j] = 0;
first = cur;
}
boolean win(int [][] cur)
{
for (int i = 0; i < 3; i++)
if (cur[i][0] == cur[i][1] && cur[i][1] == cur[i][2] && cur[i][2] != 0)
return true;
for (int i = 0; i < 3; i++)
if (cur[0][i] == cur[1][i] && cur[1][i] == cur[2][i] && cur[2][i] != 0)
return true;
if (cur[0][0] == cur[1][1] && cur[1][1] == cur[2][2] && cur[2][2] != 0) return true;
else if (cur[0][2] == cur[1][1] && cur[1][1] == cur[2][0] && cur[2][0] != 0) return true;
return false;
}
int dfs(boolean computer)
{
int state = -1,n = 0;
for (int x = 0; x < 3; x++)
for (int y = 0; y < 3; y++) if (cal[y][x] != 0)
n++;
if (n == 9) return 0;
for (int x = 0; x < 3; x++)
for (int y = 0; y < 3; y++) if(cal[y][x] == 0)
{
if (computer) cal[y][x] = 2;
else cal[y][x] = 1;
if (win(cal))
{
cal[y][x] = 0;
return 1;
}
int cur = dfs(!computer);
if (cur == -1)
{
cal[y][x] = 0;
return 1;
}
else if (cur == 0) state = 0;
cal[y][x] = 0;
}
return state;
}
void people()
{
int x,y;
do
{
Scanner sc = new Scanner(System.in);
System.out.println("please type x ----- [0,2]");
x = sc.nextInt();
System.out.println("please type y ------[0,2]");
y = sc.nextInt();
} while (num[y][x] != 0);
System.out.println("what you typed is (" + x + "][" + y + ")");
num[y][x] = 1;
}
void computer()
{
int ansx = -1,ansy = -1,state;
for (int x = 0; x < 3; x++)for (int y = 0; y < 3; y++)
{
if (num[y][x] == 0)
{
ansx = x;
ansy = y;
num[y][x] = 2;
if (win(num))
{
System.out.println("what computer typed is (" + x + "][" + y + ")");
return;
}
num[y][x] = 0;
}
cal[y][x] = num[y][x];
}
for (int x = 0; x < 3; x++)for (int y = 0; y < 3; y++)
{
if (num[y][x] == 0)
{
num[y][x] = 1;
if(win(num))
{
num[y][x] = 2;
System.out.println("what computer typed is (" + x + "][" + y + ")");
return;
}
num[y][x] = 0;
}
}
for (int x = 0; x < 3; x++)
for (int y = 0; y < 3; y++) if (cal[y][x] == 0)
{
cal[y][x] = 2;
// 2 is computer
// 1 is people
if(win(cal))
{
num[y][x] = 1;
System.out.println("what computer typed is (" + x + "][" + y + ")");
return;
}
state = dfs(false);
//System.out.println(x + " x y " + y + " state " + state);
//false is people;
//true is computer
if(state == 0)
{
ansx = x;
ansy = y;
}
else if (state == -1)
{
num[y][x] = 2;
System.out.println("what computer typed is (" + x + "," + y + ")");
return;
}
cal[y][x] = 0;
}
num[ansy][ansx] = 2;
System.out.println("what computer typed is (" + ansx + "," + ansy + ")");
}
int solve()
{
int ans = 0;
if (first == 0)
{
num[1][1] = 2;
ans++;
System.out.println("1 x y 1");
}
while(!win(num) && ans != 9)
{
ans++;
if ((ans & 1) == first)people();
else computer();
}
if(win(num))return (ans & 1);
else return -1;
}
public void play()
{
int state = solve();
System.out.println("----------------------------------------------------------------------");
System.out.println("----------------------------------------------------------------------");
if (state == 1) System.out.println("Alice");
else if (state == 0) System.out.println("Bob");
else System.out.println("Draw");
System.out.println("----------------------------------------------------------------------");
System.out.println("----------------------------------------------------------------------");
}
}
|
转播
