1、功能需求
接上篇博文,本文描述简单人机对战实现过程,只是简单实现考虑走一步策略,如果要想实现走多步策略,可以在本文估值算法的基础上用极大极小值配合剪枝算法,实现考虑多步策略,这样ai会显得更加聪明,后期如果有时间完善,会更新代码。
2、界面设计
参考上一篇博文的界面。
3、算法描述
其实算法非常简单,毕竟ai部分只有200行代码,所以应该只能算是实现估值函数,即当前局面走一步时最好的位置,不考虑走多步。我的思路如下:
(1)枚举当前局面棋子可能的落点,并给不同的局面赋值,越重要的局面分数会越高
(2)遍历每个可落子点
(3)在可落子点落子时,分四个方向去获得落子前后五个位置并转换成序列,然后检测该序列满足(1)中的情况,并获得一定分数累加存到字典中
(4)对字典进行排序
(5)取得分数最高的点即为最优落子点
当然,这只是考虑一步,但也有不错的棋力,如果要考虑多步,请参考前面提到的极大极小值配合剪枝算法,其实本博文的算法可以当作极大极小值配合剪枝算法的估值函数,然后只做迭代就好了。
4、代码实现
对上一博文的代码有一点小的更新,因此全部贴出代码,可能枚举时有考虑不到的情况,可能有些小问题,不过思想是没有问题的,项目代码如下:
using System;using System.Collections.Generic;using System.ComponentModel;using System.Data;using System.Drawing;using System.Linq;using System.Text;using System.Threading.Tasks;using System.Windows.Forms;namespace WindowsFormsAppAnimalRegonize{ public partial class FormChess : Form { class Pos { public int X { get; set; } public int Y { get; set; } public bool Have_chess { get; set; } public int Type { get; set; } public Pos(int X, int Y, bool Have_chess, int Type) { this.X = X; this.Y = Y; this.Have_chess = Have_chess; this.Type = Type; } } private List null_chess_pos_list; private Stack cur_chess_btn_list; private List buttons; private int down_chess; private string[] game_types = {"双人对战","人机对战","联网对战" }; private int cur_game_type; private bool game_over; public FormChess() { InitializeComponent(); comboBox1.Items.AddRange(game_types); comboBox1.SelectedIndex = 0; init_score_dict(); } private void init_game() { switch(comboBox1.SelectedItem.ToString()) { case "双人对战": cur_game_type = 0; break; case "人机对战": cur_game_type = 1; break; case "联网对战": cur_game_type = 2; break; } game_over = false; //白棋先走,1为白棋2为黑棋 down_chess = 1; if (buttons == null) buttons = new List(); if (null_chess_pos_list == null) { null_chess_pos_list = new List(); for (int x = 0; x < 13; x++) { for (int y = 0; y < 13; y++) { new_chess_pos(30 + 50 * x, 30 + 50 * y); var pos = new Pos(x, y, false, 0); null_chess_pos_list.Add(pos); } } } else { for (int i = 0; i < null_chess_pos_list.Count; i++) { null_chess_pos_list[i].Have_chess = false; null_chess_pos_list[i].Type = 0; } } if (cur_chess_btn_list == null) cur_chess_btn_list = new Stack(); else { while (cur_chess_btn_list.Count > 0) { var btn = cur_chess_btn_list.Peek(); btn.BackgroundImage = Properties.Resources.chess_bg1; cur_chess_btn_list.Pop(); } } set_down_chess_label(); } //绘制棋盘 private void draw_chess_grid() { var graphics = this.CreateGraphics(); this.Show();//一定要加这句,不然无法显示 var pen = new Pen(Brushes.Black, 2.0f); for (int x = 0; x < 13; x++) { var p1 = new Point(50 + x * 50, 50); var p2 = new Point(50 + x * 50, 50 + 50 * 12); graphics.DrawLine(pen, p1, p2); } for (int y = 0; y < 13; y++) { var p1 = new Point(50, 50 + y * 50); var p2 = new Point(50 + 50 * 12, 50 + y * 50); graphics.DrawLine(pen, p1, p2); } } //右上方向判断 private int right_up_check(Pos pos,int count) { if (count == 5) { if (pos.Type == 2)MessageBox.Show("黑方赢棋", "系统提示"); else MessageBox.Show("白方赢棋", "系统提示"); game_over = true; } if (pos.X + 1 <13 && pos.Y - 1 >0 && pos.Type != 0) { var index = get_pos_index_from_null_chess_list(pos.X + 1, pos.Y - 1); if (null_chess_pos_list[index].Type == pos.Type) right_up_check(null_chess_pos_list[index],count + 1); } return count; } //左上方向判断 private int left_up_check(Pos pos, int count) { if (count == 5) { if (pos.Type == 2) MessageBox.Show("黑方赢棋", "系统提示"); else MessageBox.Show("白方赢棋", "系统提示"); game_over = true; } if (pos.X - 1 > 0 && pos.Y - 1 > 0 && pos.Type != 0) { var index = get_pos_index_from_null_chess_list(pos.X - 1, pos.Y - 1); if (null_chess_pos_list[index].Type == pos.Type ) left_up_check(null_chess_pos_list[index], count + 1); } return count; } //横向方向判断 private int horizontal_check(Pos pos, int count) { if (count == 5) { if (pos.Type == 2) MessageBox.Show("黑方赢棋", "系统提示"); else MessageBox.Show("白方赢棋", "系统提示"); game_over = true; } if (pos.X + 1 < 13 && pos.Type != 0) { var index = get_pos_index_from_null_chess_list(pos.X + 1, pos.Y ); if (null_chess_pos_list[index].Type == pos.Type) horizontal_check(null_chess_pos_list[index], count + 1); } return count; } //竖向方向判断 private int vertical_check(Pos pos, int count) { if (count == 5) { if (pos.Type == 2) MessageBox.Show("黑方赢棋", "系统提示"); else MessageBox.Show("白方赢棋", "系统提示"); game_over = true; } if (pos.Y + 1 < 13 && pos.Type != 0) { var index = get_pos_index_from_null_chess_list(pos.X , pos.Y + 1); if (null_chess_pos_list[index].Type == pos.Type) vertical_check(null_chess_pos_list[index], count + 1); } return count; } //判断赢局 private void check_win() { for (int i = 0; i < null_chess_pos_list.Count; i++) { left_up_check(null_chess_pos_list[i], 1); right_up_check(null_chess_pos_list[i], 1); horizontal_check(null_chess_pos_list[i], 1); vertical_check(null_chess_pos_list[i], 1); } } //初始生成下棋位置 private void new_chess_pos(int x,int y) { var button = new Button(); button.Location = new Point(x, y); button.Size = new Size(40, 40); set_btn_style(button); this.Controls.Add(button); button.Click += new EventHandler(button1_Click); buttons.Add(button); } //窗口坐标转点坐标 private Point location_to_point(Button button) { return new Point((button.Location.X - 30)/50, (button.Location.Y - 30)/50); } //点坐标转窗口坐标 private Point point_to_location(Pos pos) { return new Point(pos.X * 50 +30, pos.Y * 50 +30); } //根据点坐标得到棋子位置索引 private int get_pos_index_from_null_chess_list(int x,int y) { for (int i = 0; i < null_chess_pos_list.Count; i++) if (null_chess_pos_list[i].X == x && null_chess_pos_list[i].Y == y)return i; return -1; } //根据窗口坐标得到索引 private int get_btn_index_from_button_list(int x, int y) { for (int i = 0; i < buttons.Count; i++) if (buttons[i].Location.X == x && buttons[i].Location.Y == y) return i; return -1; } //ai走棋 private void ai_move_chess() { Pos pos = get_best_pos(); var point = point_to_location(pos); var index = get_btn_index_from_button_list(point.X, point.Y); move_chess(buttons[index]); } //走棋 private void move_chess(Button button) { var point = location_to_point(button); var index = get_pos_index_from_null_chess_list(point.X, point.Y); if (null_chess_pos_list[index].Have_chess) return; null_chess_pos_list[index].Have_chess = true; if (down_chess == 2) { button.BackgroundImage = Properties.Resources.black; null_chess_pos_list[index].Type = 2; down_chess = 1; } else { button.BackgroundImage = Properties.Resources.white; null_chess_pos_list[index].Type = 1; down_chess = 2; } set_down_chess_label(); //添加到下棋栈列 cur_chess_btn_list.Push(button); check_win(); } // 设置透明按钮样式 private void set_btn_style(Button btn) { btn.FlatStyle = FlatStyle.Flat;//样式 btn.ForeColor = Color.Transparent;//前景 btn.BackColor = Color.Transparent;//去背景 btn.FlatAppearance.BorderSize = 0;//去边线 btn.FlatAppearance.MouseOverBackColor = Color.Transparent;//鼠标经过 btn.FlatAppearance.MouseDownBackColor = Color.Transparent;//鼠标按下 } //提示当前由哪方下棋 private void set_down_chess_label() { if (down_chess == 2) label_game_type.Text = "黑方下棋"; else label_game_type.Text = "白方下棋"; } //悔棋 private void back_chess() { if (cur_chess_btn_list==null) return; if (cur_chess_btn_list.Count == 0) return; var btn = cur_chess_btn_list.Peek(); var p = location_to_point(btn); var index = get_pos_index_from_null_chess_list(p.X,p.Y); null_chess_pos_list[index].Type = 0; null_chess_pos_list[index].Have_chess = false; btn.BackgroundImage = Properties.Resources.chess_bg1; cur_chess_btn_list.Pop(); if (down_chess == 2) down_chess = 1; else down_chess = 2; set_down_chess_label(); } //下棋点击事件 private void button1_Click(object sender, EventArgs e) { if (game_over) return; switch (cur_game_type) { case 0: move_chess((Button)sender); break; case 1: move_chess((Button)sender); ai_move_chess(); break; case 2: break; } } //开始游戏 private void button_start_Click(object sender, EventArgs e) { init_game(); } //悔棋 private void button_back_Click(object sender, EventArgs e) { if (game_over) return; switch (cur_game_type) { case 0: back_chess(); break; case 1: back_chess(); back_chess(); break; case 2: break; } } //重置游戏 private void button_reset_Click(object sender, EventArgs e) { init_game(); } //ai部分代码 private Dictionary dict = new Dictionary();//存储枚举分数的字典 private void init_score_dict() { //5个连子 dict.Add("",); //4个连子 dict.Add("", ); dict.Add("", 5222); dict.Add("", 5222); dict.Add("", 5222); //3个连子 dict.Add("", 2522); dict.Add("", 1222); dict.Add("", 1222); dict.Add("", 1222); dict.Add("", 1222); dict.Add("", 1222); //2个连子 dict.Add("", 522); dict.Add("", 522); dict.Add("", 322); //1个子 dict.Add("", ); dict.Add("", ); dict.Add("", ); dict.Add("", 4222); dict.Add("", 4222); dict.Add("", 4222); dict.Add("",822); dict.Add("", 822); dict.Add("", 822); dict.Add("", 222); dict.Add("", 222); } //水平方向,传入的pos均为当前要估值的pos private string get_horizontal_pos_str(Pos head_temp_pos) { int head_x = head_temp_pos.X,trail_x = head_temp_pos.X,head_count =0,trail_count =0; while (head_count < 5 && head_x - 1 > 0) { head_count++; head_x--; } while (trail_count < 5 && trail_x + 1 < 13) { trail_count++; trail_x++; } StringBuilder sb = new StringBuilder(); for (int i = head_temp_pos.X - head_count; i <= head_temp_pos.X+trail_count; i++) { if (i == head_temp_pos.X) sb.Append(head_temp_pos.Type.ToString()); else { var index = get_pos_index_from_null_chess_list(i, head_temp_pos.Y); sb.Append(null_chess_pos_list[index].Type.ToString()); } } return sb.ToString(); } //竖直方向 private string get_vertical_pos_str(Pos head_temp_pos) { int head_y = head_temp_pos.Y, trail_y = head_temp_pos.Y, head_count = 0, trail_count = 0; while (head_count < 5 && head_y - 1 > 0) { head_count++; head_y--; } while (trail_count < 5 && trail_y + 1 < 13) { trail_count++; trail_y++; } StringBuilder sb = new StringBuilder(); for (int i = head_temp_pos.Y - head_count; i <= head_temp_pos.Y + trail_count; i++) { if (i == head_temp_pos.Y) sb.Append(head_temp_pos.Type.ToString()); else { var index = get_pos_index_from_null_chess_list(head_temp_pos.X,i); sb.Append(null_chess_pos_list[index].Type.ToString()); } } return sb.ToString(); } //左上方向 private string get_left_up_pos_str(Pos head_temp_pos) { int head_x=head_temp_pos.X,head_y = head_temp_pos.Y, trail_x = head_temp_pos.X, trail_y = head_temp_pos.Y, head_count = 0, trail_count = 0; while (head_count < 5 && head_y - 1 > 0 && head_x - 1>0) { head_count++; head_y--; head_x--; } while (trail_count < 5 && trail_y + 1 < 13 && trail_x + 1 <13) { trail_count++; trail_y++; trail_x++; } var step = head_temp_pos.X - head_count; StringBuilder sb = new StringBuilder(); for (int i = head_temp_pos.Y - head_count; i <= head_temp_pos.Y + trail_count; i++) { if (i == head_temp_pos.Y) sb.Append(head_temp_pos.Type.ToString()); else { var index = get_pos_index_from_null_chess_list(step, i); sb.Append(null_chess_pos_list[index].Type.ToString()); } step++; } return sb.ToString(); } //右上方向 private string get_right_up_pos_str(Pos head_temp_pos) { int head_x = head_temp_pos.X, head_y = head_temp_pos.Y, trail_x = head_temp_pos.X, trail_y = head_temp_pos.Y, head_count = 0, trail_count = 0; while (head_count < 5 && head_y + 1 < 13 && head_x - 1 > 0) { head_count++; head_y++; head_x--; } while (trail_count < 5 && trail_y - 1 > 0 && trail_x + 1 < 13) { trail_count++; trail_y--; trail_x++; } var step = head_temp_pos.Y + head_count; StringBuilder sb = new StringBuilder(); for (int i = head_temp_pos.X - head_count; i <= head_temp_pos.X + trail_count; i++) { if (i == head_temp_pos.X) sb.Append(head_temp_pos.Type.ToString()); else { var index = get_pos_index_from_null_chess_list(i, step); sb.Append(null_chess_pos_list[index].Type.ToString()); } step--; } return sb.ToString(); } //得到在位置落子时的分数 private int get_pos_score(Pos pos) { int value = 0; string left_up = get_left_up_pos_str(pos); string right_up = get_right_up_pos_str(pos); string horizontal = get_horizontal_pos_str(pos); string vertical = get_vertical_pos_str(pos); foreach (KeyValuePair pair in dict) { if (left_up.Contains(pair.Key) || left_up.Contains(new string(pair.Key.ToCharArray().Reverse().ToArray()))) value += pair.Value; if (right_up.Contains(pair.Key) || right_up.Contains(new string(pair.Key.ToCharArray().Reverse().ToArray()))) value += pair.Value; if (horizontal.Contains(pair.Key) || horizontal.Contains(new string(pair.Key.ToCharArray().Reverse().ToArray()))) value += pair.Value; if (vertical.Contains(pair.Key) || vertical.Contains(new string(pair.Key.ToCharArray().Reverse().ToArray()))) value += pair.Value; } return value; } //得到最好的落子位置 private Pos get_best_pos() { var dict_score = new Dictionary(); for (int i = 0; i < null_chess_pos_list.Count; i++) { if (null_chess_pos_list[i].Have_chess == false) { Pos pos = new Pos(null_chess_pos_list[i].X, null_chess_pos_list[i].Y, null_chess_pos_list[i].Have_chess,2); dict_score.Add(null_chess_pos_list[i], get_pos_score(pos)); } } var temp_dict_score = dict_score.OrderByDescending(o => o.Value).ToDictionary(p =>p.Key,o => o.Value); return temp_dict_score.Keys.First(); } }}5、测试
由于只考虑一步,想要很强的棋力是不可能的,但是也不算特别白痴,给它赢它还是很“乐意”的,好奇的童鞋可以拷贝代码运行试试看看,本文的思想仅供参考。