我想找个下棋的对手

人机对战,从计划到实现

Posted by lyle on March 27, 2021

故事背景

那天是 2019 年秋天的星期日,天气真的不错,可一篇文章牢牢宅住了我

AlphaZero Explained

越看越热血,越看越痒痒,恨不得即刻动手实践一番。

可惜去年忙于换工作的事,无奈搁浅。

近期连续听了好几场游戏团队的分享,从游戏心理研究到 CG 特效,从大黄蜂变形算法到 RPG 实现,心底那股「做人机」的劲儿又上来了。

是时候「做个真正的了结」,实现一款「人机对战」的游戏。

特记下此系列,旨在立下 Flag,日后自我督(dǎ)促(liǎn)用。

关键词:人工智能、Alpha Go、深度学习…都没关系:)

人与咸鱼

一款「人机对战游戏」,嗯…像是个工程问题。人还是要有些梦想的,装模作样规划一下:

有哪些阶段

一阶段目标,对简单游戏实现人机对战,重在沉淀两个框架:棋盘类游戏框架 & 人机对战框架;

二阶段目标,选择难一些的游戏做人机,支持设置 AI 难度;

三阶段目标,支持设置 AI 倾向,让不同倾向的 AI 相互训练。

AI 倾向:如进攻型/防守型/激进型/保守型等,听起来是不是很酷,我就计划做个调参嘛…

具体选哪款游戏

一阶段选「井字棋」,规则简单,路数有限可枚举,双方回合制;

二阶段备选 1,「五子棋」,规则简单,但分支较多无法枚举,可引入胜率估算,适合体现 AI 各难度的差异;

二阶段备选 2,「飞行棋」,多方回合制,运气与决策并存,适合体现 AI 各倾向的差异。

用什么语言,怎么选 UI

JS:界面效果好,但需要补的基础较多(JQ 时代的老人家…惭愧
C# + WinForm:丑了点,你拖过控件吗
Java + Console:有点极客的味儿了,但略重
Go + Console:UI 框架太少
Python:动态语言,不利于调试

经过「充分 && 理性」地分析,就选最近比较感兴趣的 Go 吧。

无知限制选择,贫穷限制想象。

至于框架问题,越轻越好,快速 github 一把「go console」,按星倒序,锁定 jroimartin/gocui - Go Console User Interface。

直奔小样

初探文档

你通常可以在 github/官网上找到像这样的文档,gocui document

官方文档一定要看、还要看多次。但这第一次,是限速的。

新学一套框架,第一步就是确定「这套框架真的合适吗」。

它的定位是什么,解决了什么问题,解决的手段是厚重还是轻薄

能快速搭建终端交互应用的框架,解决终端显示与交互问题,十分轻薄,依赖 github.com/nsf/termbox-go

官方文档有多详尽,是否有设计理念的介绍

有上手 demo,介绍了关键的常量与方法,展示了使用效果、成功案例

没有关于设计理念的介绍,只在使用 g.MainLoopg.Update 方法的简介中猜测
框架基于一个无限循环的主流程与事件队列,来实现整体的交互

MainLoop runs the main loop until an error is returned.
It is important to note that the passed function won’t be executed immediately, instead it will be added to the user events queue.

上手体验

先放张官图填充一下想象。

layout

无脑先拿官方 demo 跑一跑,保留关键信息,加点「人文注释」感受一下。

func main() {
    // 1. 创建「画布」
	g, err := gocui.NewGui(gocui.OutputNormal)
	if err != nil {
		log.Panicln(err)
	}
	
	// -1. 打完收工
	defer g.Close()

    // 2. 设计「画布」
	g.SetManagerFunc(layout)

    // 5. 将事件绑定到「图层」上
	if err := g.SetKeybinding("", gocui.KeyCtrlC, gocui.ModNone, quit); err != nil {
		log.Panicln(err)
	}

    // 6. 运行「画布」效果
	if err := g.MainLoop(); err != nil && err != gocui.ErrQuit {
		log.Panicln(err)
	}
}

// 3. 在「画布」上创建「图层」
func layout(g *gocui.Gui) error {
	maxX, maxY := g.Size()
	if v, err := g.SetView("hello", maxX/2-7, maxY/2, maxX/2+7, maxY/2+2); err != nil {
		if err != gocui.ErrUnknownView {
			return err
		}
		fmt.Fprintln(v, "Hello world!")
	}
	return nil
}

// 4. 定义即将发生在「图层」上的事件处理
func quit(g *gocui.Gui, v *gocui.View) error {
	return gocui.ErrQuit
}

至此,有几个概念在 GUI 的世界里一直都在,只是选择语言上有所不同:

  • 画布
    • 类似 canvas,panel,这里叫 gocui.Gui
  • 图层
    • 类似 panel,layout,这里叫 gocui.View
    • 图层 != 框,图层可覆盖,相互不影响,视觉上能区分
    • 在画布上画一个图层,1画布:n图层
  • 事件 & 处理
    • gocui.KeyCtrlC 是一个点击按钮的事件
    • func quit 是对某个事件的处理
    • 1图层:n事件,事件要定义在图层上,默认 "" 是为所有图层绑定事件
    • 1处理:n事件,一个事件只能有一个处理,一种处理可以对应多种事件

demo 阶段,暂不细究,时刻要保持清醒头脑,不要被花里胡哨的效果/工程师健壮性的提问体系偏离了航道。

案例小样

除了官方 demo,我们还可以找一些使用过该框架的小案例,快速学习看看别人踩了什么坑,用的效果怎样。

goo 到一个聊天程序 使用go语言的Console UI

与官方 demo 相比,增加了几点:

  • 设置画布属性,如 g.Mouse = false
  • 设置图层属性,如 v.Editable = true
  • 图层读写,如 g.View("out")cv.ReadEditor()v.Write([]byte("你:"))

好了,外部知识的吸收告一段落,完后再有就是针对特定问题的搜索了。

确定目标

TDD 的思路,限定目标测试用例,通过为主,重构为辅,「不要被花里胡哨的效果/工程师健壮性的提问体系偏离了航道」。

于是写下

- [ ] 画出井字棋盘
- [ ] 鼠标落子
- [ ] 落子标记:x, o
- [ ] 终局标记:x/o win
- [ ] 重新开局

完成一项勾一项

浅尝辄止

搭建模板

还是 demo 那一套,拿来即用

func main() {
	g, err := gocui.NewGui(gocui.OutputNormal)
	if err != nil {
		log.Panicln(err)
	}
	defer g.Close()

	g.SetManagerFunc(layout)

	if err := g.SetKeybinding("", gocui.KeyCtrlC, gocui.ModNone, quit); err != nil {
		log.Panicln(err)
	}

	if err := g.MainLoop(); err != nil && err != gocui.ErrQuit {
		log.Panicln(err)
	}
}

func layout(g *gocui.Gui) error {
	// todo g.SetView()
	return nil
}

func quit(g *gocui.Gui, v *gocui.View) error {
	return gocui.ErrQuit
}

画出井字棋盘

目标的第一步就是画棋盘,思路:

  1. 不只是画个「井」字,而是画完整的「九宫格」—— 因为默认效果就是一个四方格子,减少调整的工作量
  2. 九宫格使用九个图层 View —— 事件是绑定在图层上的,且文字也是放在图层内的,适合独立处理
func layout(g *gocui.Gui) error {
	side := 2 // 定义边长
	_, err := g.SetView("cell", 0, 0, side, side) // 画一个从 (0,0) 到 (side, side) 的矩形
	if err != nil && err != gocui.ErrUnknownView {
		return err
	}
	return nil
}

此时的效果是这样的

cell00

不应该都是变长为 side 的正方形吗?目测像是 1:3 的长方形

demo 要快速实验,无需深究

就当作结论是 1:3,继续调整参数

学习 demo 里利用 g.Size() 获取画布大小,以此定位居中的位置,结合 1:3 的结论,得

func layout(g *gocui.Gui) error {
	maxX, maxY := g.Size()
	side := 2
	x0, y0 := maxX/2-6*side, maxY/2-2*side
	_, err := g.SetView("cell", x0+3*side, y0+side, x0+3*side+3*side, y0+side+side)
	if err != nil && err != gocui.ErrUnknownView {
		return err
	}
	return nil
}

运行…不错,居中了,正方了。

cell11

趁热打铁两层遍历,图层名定义 cell-{i}-{j}

func layout(g *gocui.Gui) error {
	maxX, maxY := g.Size()
	side := 2
	x0, y0 := maxX/2-6*side, maxY/2-2*side
	for i := 0; i < 3; i++ {
		for j := 0; j < 3; j++ {
			_, err := g.SetView(fmt.Sprintf("cell-%d-%d", i, j), x0+i*3*side, y0+j*side, x0+i*3*side+3*side, y0+j*side+side)
			if err != nil && err != gocui.ErrUnknownView {
				return err
			}
		}
	}
	return nil
}

运行…奈斯,万里长征第一步,星辰大海我来了!

board

感觉连接处不是很好?

这时候「目标」的作用来了:目标提醒我们要时刻关注它,浅尝辄止,实现就交卷,不求甚解

这还是工匠精神吗?

工匠精神要用在更值得关注的地方,别忘了咱的星辰大海是「人机」算法,UI 只是提供人机交互罢了

60 分万岁,可谓「低空飞行的哲学」

鼠标落子

有个画布,就可以走棋了,如何支持鼠标点击?

「案例小样」中「画布属性」相关设置了 g.Mouse = false 是突破口

// 注释只是为了突出非注释部分
func main() {
	// gocui.NewGui(gocui.OutputNormal)
	// defer g.Close()

	// g.SetManagerFunc(layout)
	
	// 1. 设置画布支持响应鼠标
	g.Mouse = true

	// g.SetKeybinding("", gocui.KeyCtrlC, gocui.ModNone, quit)
	
	// 2. 为所有图层绑定 MouseLeft 事件,对应 click 处理
	if err := g.SetKeybinding("", gocui.MouseLeft, gocui.ModNone, click); err != nil {
		log.Panicln(err)
	}

	// g.MainLoop();
}


// 3. 定义 click 处理
func click(g *gocui.Gui, v *gocui.View) error {
	return nil
}

落子标记 & 胜负判断

click 内要处理的内容:

  1. 是否已落子
  2. 当前落子
  3. 判断胜负
var (
	step   = 0      // 步数
	finish = false  // 胜利标识
)

func click(g *gocui.Gui, v *gocui.View) error {
    if finish {
		return nil
	}
	
    // 1. 若已落子,则不可重复再落
	if len(v.Buffer()) > 0 {
		return nil
	}

    // 2. 根据步数,双方交替落子
	signal := "o"
	if (step & 1) == 0 {
		signal = "x"
	}
	fmt.Fprintf(v, "  %s", signal)
	step++

    // 3. 判断胜负
	if judge(g) {
		return win(g, signal)
	}
	return nil
}

func win(g *gocui.Gui, winner string) error {
    finish = true
	return nil
}

func judge(g *gocui.Gui) bool {
    // 无脑第 8 步胜
	return step > 7
}

至此,已经可以「假装」玩一把游戏了!

play-first-time

胜利弹窗输出

是不是感觉缺少点胜利的喜悦?加个弹窗式的图层吧!

func win(g *gocui.Gui, winner string) error {
	finish = true
	
	// 取中心格子的位置
	x0, y0, x1, y1, err := g.ViewPosition("cell-1-1")
	if err != nil {
		return err
	}

    // 计算偏移量
	dx, dy := (x1-x0)/2, (y1-y0)/2
	
	// 创建胜利弹窗
	v, err := g.SetView("win", x0-dx, y0-dy, x1+dx, y1+dy)
	if err != nil && err != gocui.ErrUnknownView {
		return err
	}
	fmt.Fprintf(v, "%s win!", winner)
	return nil
}

效果像这样

add-win

感觉好欠缺什么?

是胜利来的太突然,还是重开显得不自然

胜利延时 & 重新开局

考虑在 win() 内延时 1s,增加重新开局的事件

// 注释只是为了突出非注释部分
func win(g *gocui.Gui, winner string) error {
	// finish = true
	
	// 增加延时效果
	time.Sleep(1 * time.Second)
	
	// g.ViewPosition("cell-1-1")

	// g.SetView("win", x0-dx, y0-dy, x1+dx, y1+dy)
	// fmt.Fprintf(v, "%s win!", winner)
	
	// 增加重新开局的「回车」事件,绑定到 restart 处理
	g.SetKeybinding("", gocui.KeyEnter, gocui.ModNone, restart)
	g.SetCurrentView(v.Name())
	
	// return nil
}

func restart(g *gocui.Gui, v *gocui.View) error {
    // 移除胜利弹窗
	g.DeleteView(v.Name())
	// 清空所有格子
	for _, v := range g.Views() {
		v.Clear()
	}
	// 重新计步
	step = 0
	finish = false
	// 移除重新开局的「回车」事件
	g.DeleteKeybinding("", gocui.KeyEnter, gocui.ModNone)
	return nil
}

好了,现在可以无限开局了

restart

还是有些奇怪,为什么延时的 1s,明明写在 win 内,却连 win 之前的「落子」动作也被阻塞了呢?

从效果上说,我们如何实现最后的落子在完成绘制以后,间隔一秒,才出现弹窗?

最后一次落子

写程序时的思考,就像侦探小说一样有趣

还记得官网那句神奇的 loop 循环吗?

MainLoop runs the main loop

  1. 交互框架,解决的是人机的「交互」环节
  2. 每一次「交互」都是一次循环,无论是操作鼠标落子,还是敲击键盘按压

让我们再回到代码上来

func click(...) {
    ...
    if judge(...) {
		return win(...)
	}
	...
}

func win(...) {
    ...
    time.Sleep(1 * time.Second)
    ...
}

没错,真相了:上述代码里我们只做了一次交互 click,而 win 从属于这一次交互

我们有理由相信,框架底层是在每论的代码执行完毕后,才开始绘制的界面:

click -> win -> 绘制界面

故:在 win 内的 1s,会影响 click 中希望被绘制的最后一次落子。

而我们希望的是:

click - 绘制 - win - 绘制

如何解?回到官网找到这句

It is important to note that the passed function won’t be executed immediately, instead it will be added to the user events queue.

原来哥们儿实现循环的做法,就是将 function 放入队列 queue

为何这么实现?官网也说的很清楚:并发安全性

盲猜:

  1. 默认应该是 FIFO 的队列
  2. 队列元素出队后被处理,而后绘制界面,再出队下一个元素进行处理、绘制,如此反复。

click - 绘制 - win - 绘制

被细化为

{click-绘制},{win-绘制}

两个事件,分开处理,分开绘制。g.Update 可理解为将「处理」入队。

func click(g *gocui.Gui, v *gocui.View) error {
	// ...

	g.Update(func(gui *gocui.Gui) error {
		if judge(g) {
			return win(g, signal)
		}
		return nil
	})
	return nil
}

成果展示

queue

至此,本篇代码完,开战吧孩子!

本篇小结

为何说兴趣是最好的老师?

你想想老师一天天最担心是学生们的学习成绩吗,是学习的态度/动力呀!

找到你心中的感兴趣的事吧,那件当时没做,日后还会想起,每每想起还依然热血的事。

语言也好,框架也罢,只是实现想法的手段罢了。

出发前别忘了先定下目标,不要被半路花里胡哨的、灯红酒绿的繁华所迷惑,始终不要偏离航线太远。

扩展思考

如果落子在横纵线交点呢?如五子棋、象棋

思路:去掉图层 View 边框,在格内画「十」字试试。

下期更新 Flag

  1. 完整做一个「井字棋」游戏
  2. 沉淀出「棋盘类游戏框架」