五子棋 – 人机对战

简介

高一时第一次接触了C++,心血来潮编了几个诸如推箱子、贪吃蛇、俄罗斯方块的小游戏。

觉得不过瘾,碰巧那会儿班里流行五子棋,便着手于编一个人机对战程序。

碍于编程知识不足,算法只用了判断、循环。借助easyx的图形库,它有了图形界面。

最终版本经调查测试,实力优于初学者,并能与中等水平者相抗衡。

(反正我被他阴了好多次,不知是该笑还是该哭(▼皿▼#) )

基本思路

敌方每下一子,就在一个计数的矩阵里自己那格的四周(横竖撇捺四个方向,正负各延伸四格)加上个数值。这个加上的数值随与敌方所下子的距离而变。

不妨命名一个点的累积值为,下子使周围改变的效果为

己方下的子同理,但所给的是反向的(即所增加的值为负值)。

用四个矩阵分别记录来自四个方向的和相应积累的,互不干扰。

最终己方落子的判断依据来源于所有方向的绝对值的总和,取绝对值的总和最大的点落子。

算法原理很简单,说白了就是赋值再取极值的贪心算法,但至于怎么赋值还是有点讲究的。

初始版本里采用了1-1-1-1赋值法(就是那个加上的值不随与上一落子的距离而变),并且没有加入四方向绝对值相加的机制,导致算法的最终行为很玄学

它居然自动解锁了八卦阵技能,在连活三都不会防的情况下。(⊙_⊙)

升级版本采用了4-3-2-1赋值法,并延续到了最终版本。至此,它学会了如何防双三、三四等局面。

最终版本里又加入了遇四就堵的功能,但已经丧失了初始版本“两仪生四象,四象生八卦”的睿智。

废话讲完了,下面是代码

代码

#pragma comment(lib, "kernel32")
#pragma comment(lib, "user32")
#pragma comment(lib, "gdi32")
#pragma comment(lib, "winspool")
#pragma comment(lib, "comdlg32")
#pragma comment(lib, "advapi32")
#pragma comment(lib, "shell32")
#pragma comment(lib, "ole32")
#pragma comment(lib, "oleaut32")
#pragma comment(lib, "uuid")
#pragma comment(lib, "odbc32")
#pragma comment(lib, "odbccp32")
#include <graphics.h>
#include <conio.h>
#include <math.h>
#include <stdlib.h>

int plotform(int x)
{
	return 25 * (x - 1) + 15;
}

int storgeform(int x)
{
	return (x - 15) / 25 + 1;
}

class whom
{
public:
	int value;//1 or -1
	COLORREF color;//BLACK or WHITE
};

void changeplayer(whom& whom)
{
	whom.value = whom.value*(-1);
	if (whom.value == 1)
		whom.color = BLACK;
	else
		whom.color = WHITE;
}

void drawmap(int map[][20])
{
	int xwidth = 480, ywidth = 480;
	initgraph(xwidth, ywidth);
	setbkcolor(YELLOW);
	cleardevice();
	setlinecolor(LIGHTGRAY);
	for (int i = 15; i <= ywidth - 15; i = i + 25)
		line(15, i, xwidth - 15, i);
	for (int j = 15; j <= xwidth - 15; j = j + 25)
		line(j, 15, j, xwidth - 15);
	setfillcolor(LIGHTGRAY);
	for (int i = 4; i <= 16; i = i + 6)//both i & j are storgeform
	{
		for (int j = 4; j <= 16; j = j + 6)
		{
			solidcircle(plotform(i), plotform(j), 5);
		}
	}
}

void human(int& x, int& y, int&xq, int& yq, whom& whom, int map[][20])//both x & y are storgeform 
{
	MOUSEMSG a;
	do
	{
		do
		{
			a = GetMouseMsg();
		} while (a.mkLButton == 1);
		do
		{
			a = GetMouseMsg();
		} while (a.mkLButton == 0);
		xq = x;
		yq = y;
		x = round(((double)a.x - 15) / 25) + 1;
		y = round(((double)a.y - 15) / 25) + 1;
		/*if (getpixel(plotform(x),plotform(y)) == LIGHTGRAY)
			break;*/
		if (map[x][y] == 0)
			break;
	} while (1);
}

void record(int x, int y, whom whom, int map[][20], int maprecord[][20][20])//for robot
{
	for (int i = 1; i <= 4; i++)
	{
		int dx, dy;
		switch (i)
		{
		case 1:dx = 1, dy = 0; break;
		case 2:dx = 0, dy = 1; break;
		case 3:dx = 1, dy = -1; break;
		case 4:dx = 1, dy = 1; break;
		}
		for (int j = -4; j <= 4; j++)
		{
			if (1 <= x + dx * j&&x + dx * j <= 19 && 1 <= y + dy * j&&y + dy * j <= 19 && map[x + dx * j][y + dy * j] == 0)
			{
				maprecord[i][x + dx * j][y + dy * j] = maprecord[i][x + dx * j][y + dy * j] + whom.value*abs(5 - abs(j));
			}
		}
	}
}

void chong4(int x, int y,whom whom, int map[][20],int coordinate[3])//map[x][y]==whom.value
{
	for (int i = 1; i <= 4; i++)
	{
		int dx, dy;
		switch (i)
		{
		case 1:dx = 1, dy = 0; break;
		case 2:dx = 0, dy = 1; break;
		case 3:dx = 1, dy = -1; break;
		case 4:dx = 1, dy = 1; break;
		}
		int m = 0, n = 0, skip = 0;
		coordinate[0] = 0;
		coordinate[1] = -1;
		coordinate[2] = -1;
		for (int j = 1;; j++)
		{
			if (x + j * dx < 1 || x + j * dx>19 || y + j * dy < 1 || y + j * dy>19)
				break;
			if (map[x + j * dx][y + j * dy] == whom.value)
			{
				m = m + 1;
				if (skip > 0)
					skip++;
			}
			else if (skip == 0 && map[x + j * dx][y + j * dy] == 0)
			{
				skip = 1;
				coordinate[1] = x + j * dx;
				coordinate[2] = y + j * dy;
			}
			else if (skip > 1)
			{
				coordinate[0] = 1;
				break;
			}
			else
				break;
		}
		if (coordinate[0] == 1)
			skip = 1;
		else
			skip = 0;
		for (int j = -1;; j--)
		{
			if (x + j * dx < 1 || x + j * dx>19 || y + j * dy < 1 || y + j * dy>19)
				break;
			if (map[x + j * dx][y + j * dy] == whom.value)
			{
				n = n + 1;
				if (skip > 0)
					skip++;
			}
			else if (skip == 0 && map[x + j * dx][y + j * dy] == 0)
			{
				skip = 1;
				coordinate[1] = x + j * dx;
				coordinate[2] = y + j * dy;
			}
			else if (skip > 1)
			{
				coordinate[0] = 1;
				break;
			}
			else
				break;
		}
		if (m + n >= 3&&coordinate[1]!=-1)
		{
			coordinate[0] = 2;
			settextcolor(whom.value == 1 ? RED : BLUE);//used for debug
			outtextxy(plotform(coordinate[1]), plotform(coordinate[2]), 'x');
			return;
		}
	}
}

void robot(int& x, int& y, int& xq, int& yq, whom& whom, int map[][20], int maprecord[][20][20])//both x & y are storgeform 
{
	int max = -1;
	changeplayer(whom);
	record(x, y, whom, map, maprecord);
	changeplayer(whom);

	int coordinate[3];
	chong4(xq, yq, whom, map, coordinate);
	if (coordinate[0] == 2)
	{
		xq = x;
		yq = y;
		x = coordinate[1];
		y = coordinate[2];
		record(x, y, whom, map, maprecord);
		return;
	}
	changeplayer(whom);
	chong4(x, y, whom, map, coordinate);
	if (coordinate[0] == 2)
	{
		xq = x;
		yq = y;
		x = coordinate[1];
		y = coordinate[2];
		changeplayer(whom);
		record(x, y, whom, map, maprecord);
		return;
	}
	changeplayer(whom);

	for (int i = 1; i <= 19; i++)
	{
		for (int j = 1; j <= 19; j++)
		{
			if (map[i][j] == 0)
			{
				int potential[5];
				for (int p = 1; p <= 4; p++)
				{
					potential[p] = maprecord[p][i][j];
					if (abs(potential[p]) >= 5)
						potential[p] = potential[p] * 2;
					if (abs(potential[p]) >= 18)
						potential[p] = potential[p] * 2;
				}
				int all = abs(potential[1]) + abs(potential[2]) + abs(potential[3]) + abs(potential[4]);
				if (all > max)
				{
					max = all;
					xq = x;
					yq = y;
					x = i;
					y = j;
				}
				if (all == max && rand()%100 <= 60)
				{
					max = all;
					xq = x;
					yq = y;
					x = i;
					y = j;
				}
			}
		}
	}
	record(x, y, whom, map, maprecord);
}

void drawpiece(int x, int y, whom& whom, int map[][20])//both x & y are storgeform 
{
	setfillcolor(whom.color);
	solidcircle(plotform(x), plotform(y), 10);
	map[x][y] = whom.value;
	changeplayer(whom);
}

int main()
{
	int map[20][20] = { 0 };
	int maprecord[5][20][20] = { 0 };
	whom whom;
	whom.color = BLACK;
	whom.value = 1;
	int x, y, xq, yq;
	drawmap(map);
	do
	{
		if (whom.value == 1)
			human(x, y,xq,yq, whom, map);
		else
			robot(x, y, xq, yq, whom, map, maprecord);
		drawpiece(x, y, whom, map);
	} while (1);
	_getch();
	closegraph();
}

图片

发表评论