看着 Ta 们在棋盘上疯狂地思考、对战厮杀，那么专注、那么乐此不疲；
而我，终于放空思绪，呆若木鸡。
有那么一刻，仿佛 Ta 们才是有生命的人。
快速预览
- 笔者做了两款框架：一款定义游戏规则，一款定义人机算法
- 前者实现了两个案例，井字棋 & 五子棋
- 后者实现了井字棋 AI，按计划下期才到五子棋 AI
- 本文介绍框架的基本使用 & 案例实现：100行一款游戏，10行一款AI
人-人
人-机
随机落子算法
智能落子算法
AI 互掐
正文开始
全文 7000 字(不计代码)，阅读时间 24-38 分钟
继上篇「我想找个下棋的对手」之后，笔者便「立刻且零散地」投入到下一阶段的开发中。
原计划本篇要完成：
- 完整做一个「井字棋」游戏
- 沉淀出「棋盘类游戏框架」
当前进度：计划超额完成啦！repo 戳这里 github.com/lzhlyle/board-game
本篇将向大家介绍：
- 游戏框架，包括井字棋、五子棋游戏规则的代码实现。
- 人机框架，包括默认的随机选址策略、井字棋智能选址策略。
有趣的算法知识点包括：
- 棋盘压缩的位运算 —— 哈希井字棋当前棋局
- 四组八联通方向的 DFS —— 计算五子棋获胜条件
- 经典「Alice & Bob」的动态规划 —— 计算各步胜/平/负概率的棋谱生成器
游戏框架
笔者认为区分「游戏框架」与「人机框架」还是很有必要的。
游戏框架只限于游戏的设计，专注在可玩性与规则的创造，旨在回答「这游戏怎么玩」的问题。考虑的因素有：棋盘长什么样、几个人玩/谁先开/轮到谁、每轮/局的结束规则。
而人机框架关注的是计算机如何思考、如何行动。考虑的因素有：如何快速识别一个棋局、模拟更多步棋的落子、准确计算胜率。
开胃菜差不多了，这就开冲，先来揭晓游戏框架的面纱吧！
一起来到项目的 /core/ 目录。
核心接口，一览纵山小
// IBoard 棋盘
type IBoard interface {
// 棋盘长什么样
Board() *Board
}
// IPlayerCollection 玩家集
type IPlayerCollection interface {
// 几个人玩
Players() []*Player
// 谁先开
StartPlayerSequence(lastStarter *Player, winner *Player, players []*Player) []*Player
// 轮到谁
NextPlayer(last *Player) *Player
}
// IGameRule 游戏规则
type IGameRule interface {
// 怎么算一轮结束
RoundEnd(snapshot *MoveSnapshot) bool
// 怎么算一局结束
GameEnd(snapshot *MoveSnapshot) (end bool, winner *Player)
}
type BoardGame interface {
IBoard
IPlayerCollection
IGameRule
}
StartPlayerSequence 起初是没有这个方法的，表现则是每次都同一个玩家开局；考虑到游戏的有趣性，轮流开局还是更符合常理吧。
RoundEnd 表示某方玩家一轮的结束，在井字棋、五子棋里无差异 —— 落子即结束，但在飞行棋里就显得有用了 —— 骰子掷到「六」可以继续。
BoardGame 只是一个接口集，方便框架使用罢了。
核心结构体
// 棋盘
type Board struct {
Width, Height int
MoveLocStyle MoveLocStyle
}
// 落子样式
type MoveLocStyle int8
const (
// 格内落子，如井字棋、飞行棋
MoveLocStyle_InCell MoveLocStyle = 1 + iota
// 交界落子，如五子棋、围棋
MoveLocStyle_InCross
)
type MoveLocStylePainting struct {
defStr, locStrFmt string
side int
frame bool
}
Board 除了棋盘长、宽，还定义了落子样式 MoveLocStylePainting ，主要在框架内绘制棋盘时使用，游戏的实现无需关心。
// Player 单个玩家
type Player struct {
Signal *PlaySignal
AI bool
}
// PlaySignal 玩家标识
type PlaySignal struct {
Tag string
}
PlaySignal 目前只有一个 Tag string 属性，表示 x 或 o 这样的棋子标识，后续可以引入更丰富的棋子样式，如增加 Color int8 属性。
// 原始棋局快照
type MoveSnapshot struct {
Step int // 最后步数，从 0 起计
I, J int // 最后落子处
Player *Player // 最后落子玩家
Board [][]*PlaySignal // 最后棋盘
Pre, Next *MoveSnapshot // 上一步、下一步
}
func NewEmptyMoveSnapshot(width, height int) *MoveSnapshot {
board := make([][]*PlaySignal, height)
for i := range board {
board[i] = make([]*PlaySignal, width)
}
return &MoveSnapshot{Step: 0, Board: board}
}
func GenSnapshot(step, i, j int, player *Player, pre *MoveSnapshot) *MoveSnapshot {
curr := &MoveSnapshot{
Step: step,
I: i,
J: j,
Board: CloneMatrix(pre.Board),
Player: player,
Pre: pre,
}
pre.Next = curr
curr.Board[i][j] = player.Signal
return curr
}
属性「最后落子处」及「玩家」，可用于快速判断胜负，并确定胜者。
Pre, Next *MoveSnapshot 存储上一步、下一步的快照指针，形成双向链表，可用于像录像一样复盘学习。
游戏主流程
源码 200+ 行，完全可自行阅读。这里可大体预览一下「删减版」：
先来看看游戏 Play 的状态，以及游戏开始前的初始化阶段。
type Play struct {
// 游戏状态
step int
gameState GameState
currPlayer *Player
snapshot *MoveSnapshot
init bool // 是否已初始化
starter *Player
winner *Player
rule IGameRule
board *Board
playerCollection IPlayerCollection
players []*Player
// ...
}
func NewPlay(bg BoardGame) *Play {
res := &Play{
// ...
}
// ...
return res.reset()
}
// 初始游戏状态
func (p *Play) reset() *Play {
p.step = 0
p.players = p.playerCollection.StartPlayerSequence(p.starter, p.winner, p.players)
p.currPlayer = p.players[0]
p.starter = p.currPlayer
p.winner = nil
p.snapshot = NewEmptyMoveSnapshot(p.board.Width, p.board.Height)
p.init = false
return p
}
func (p *Play) Play() {
// ...
// 注册 Ctrl+C 事件
g.SetKeybinding("", gocui.KeyCtrlC, gocui.ModNone, p.quit)
// 注册鼠标左键点击事件
g.SetKeybinding("", gocui.MouseLeft, gocui.ModNone, p.move)
// ...
// 开始游戏
g.MainLoop()
}
// 绘制棋盘
func (p *Play) layout(g *gocui.Gui) error {
// ...
}
来吧，开战吧！走一步试试。
// 走一步，落子
func (p *Play) move(g *gocui.Gui, v *gocui.View) error {
// ...
// 绘制落子点位
painting := moveLocStyleMap[p.board.MoveLocStyle]
if v.Buffer() != painting.defStr+"\n" {
return nil
}
signal := p.currPlayer.Signal.Tag
// ...
// 生成棋局快照
i, j := NameToCell(v.Name())
p.snapshot = GenSnapshot(p.step, i, j, p.currPlayer, p.snapshot)
// 计算是否游戏结束
g.Update(func(g *gocui.Gui) error {
end, winner := p.rule.GameEnd(p.snapshot)
if end {
return p.win(g, winner)
}
return nil
})
// 计算当前玩家此轮是否结束
p.step++
if p.rule.RoundEnd(p.snapshot) {
p.currPlayer = p.playerCollection.NextPlayer(p.currPlayer)
}
// ...
return nil
}
赢家会是你吗？不服再战！
// 游戏结束
func (p *Play) win(g *gocui.Gui, winner *Player) error {
p.winner = winner
p.gameState = GameState_End
// ...
// 计算游戏结果弹窗的坐标
x0, y0, x1, y1, err := calcWinViewLocation(p.board.Width, p.board.Height, g)
if err != nil {
return err
}
// 显示胜利弹窗
v, err := g.SetView("win", x0, y0, x1, y1)
if err != nil && err != gocui.ErrUnknownView {
return err
}
// ...
// 注册回车事件：重新开始
_ = g.SetKeybinding("", gocui.KeyEnter, gocui.ModNone, p.restart)
// 注册 ESC 事件：移除遮罩层，看看终局什么样
_ = g.SetKeybinding("", gocui.KeyEsc, gocui.ModNone, func(g *gocui.Gui, v *gocui.View) error {
_ = g.DeleteView(v.Name())
_ = g.DeleteKeybinding("", gocui.KeyEsc, gocui.ModNone)
return nil
})
// ...
return nil
}
// 重新开局
func (p *Play) restart(g *gocui.Gui, v *gocui.View) error {
// 移除遮罩层
_ = g.DeleteView(v.Name())
// 清空棋盘
for _, v := range g.Views() {
v.Clear()
}
// 注销回车事件
_ = g.DeleteKeybinding("", gocui.KeyEnter, gocui.ModNone)
// 重置游戏状态
p.reset()
// ...
return nil
}
看到核心接口、结构体在其中的使用了吗？熟悉吧，也没有多么神秘啦～
框架空无一物，灵魂也需肉身
实现井字棋
详见仓库 /concrete/ 目录
定制一款游戏，只需实现 Board 接口
状态只有 board 和 players
type TicTacToe struct {
board *core.Board
players []*core.Player
}
func NewTicTacToe() *TicTacToe {
return &TicTacToe{
board: &core.Board{
Width: 3,
Height: 3,
MoveLocStyle: core.MoveLocStyle_InCell,
},
players: []*core.Player{
core.NewPlayer("X"),
core.NewPlayer("O"),
},
}
}
以及一些平平无奇的实现
func (t *TicTacToe) Board() *core.Board {
return t.board
}
func (t *TicTacToe) Players() []*core.Player {
return t.players
}
func (t *TicTacToe) StartPlayerSequence(lastStarter *core.Player, winner *core.Player, players []*core.Player) []*core.Player {
if lastStarter == nil {
return players
}
// 轮流开局
players[0], players[1] = players[1], players[0]
return players
}
func (t *TicTacToe) NextPlayer(last *core.Player) *core.Player {
if last == t.players[0] {
return t.players[1]
}
return t.players[0]
}
func (t *TicTacToe) RoundEnd(_ *core.MoveSnapshot) bool {
return true
}
每次落子都会判断 RoundEnd ，井字棋、五子棋直接 return true 即可。
最后是唯一关键的游戏结束判断 GameEnd
func (t *TicTacToe) GameEnd(snapshot *core.MoveSnapshot) (end bool, winner *core.Player) {
if snapshot.Player == nil {
return false, nil
}
validRow := func(mat [][]*core.PlaySignal, i int) bool {
// ...
}
validCol := func(mat [][]*core.PlaySignal, j int) bool {
// ...
}
validRToL := func(mat [][]*core.PlaySignal, i, j int) bool {
// ...
}
validLToR := func(mat [][]*core.PlaySignal, i, j int) bool {
// ...
}
// 校验当前(i, j)的横竖撇捺是否三连
if validRow(snapshot.Board, snapshot.I) ||
validCol(snapshot.Board, snapshot.J) ||
validRToL(snapshot.Board, snapshot.I, snapshot.J) ||
validLToR(snapshot.Board, snapshot.I, snapshot.J) {
return true, snapshot.Player
}
// 未结束
for _, row := range snapshot.Board {
for _, sgn := range row {
if sgn == nil {
return false, nil
}
}
}
// 平局
return true, nil
}
值得一提的是，框架取了个巧 —— MoveSnapshot 保存有当前落子的坐标 (snapshot.I, snapshot.J) ，目的就在实现者能够快速判断游戏是否结束 —— 只需判断最后落子处的「横竖撇捺」即可。
对于棋盘较大的游戏（如五子棋），作用会更明显。
最后再细看所谓「横竖撇捺」的连线判断：
// 判断横行是否三连
validRow := func(mat [][]*core.PlaySignal, i int) bool {
for j := 0; j < 3; j++ {
if mat[i][j] != mat[i][0] {
return false
}
}
return true
}
// 判断竖列是否三连
validCol := func(mat [][]*core.PlaySignal, j int) bool {
for i := 0; i < 3; i++ {
if mat[i][j] != mat[0][j] {
return false
}
}
return true
}
// 判断撇斜是否三连
validRToL := func(mat [][]*core.PlaySignal, i, j int) bool {
if i+j != 2 {
// 不在「撇」对角线上
return false
}
return mat[0][2] == mat[1][1] && mat[1][1] == mat[2][0]
}
// 判断捺斜是否三连
validLToR := func(mat [][]*core.PlaySignal, i, j int) bool {
if i != j {
// 不在「捺」对角线上
return false
}
return mat[0][0] == mat[1][1] && mat[1][1] == mat[2][2]
}
实则也是平平无奇啦～ 3x3 的棋盘实在太小，巧一巧也就完成了。
实现五子棋
五子棋的 GameEnd 则相对更普适，有前文提到的「四组八联通方向的 DFS」，那就直奔主题吧！
这神特么「四组八联通方向的 DFS」，其实就是要对「横竖撇捺」四组分别判断有没有连成五颗子，同时每组要向相反的两个方向 DFS。就这样《平平无奇》哈哈哈～
var (
dirGroup = [][][]int{
{
{0, 1}, // up
{0, -1}, // down
},
{
{-1, 0}, // left
{1, 0}, // right
},
{
{-1, -1}, // left-down
{1, 1}, // right-up
},
{
{-1, 1}, // left-up
{1, -1}, // right-down
},
}
)
两层遍历消费 dirGroup ，判断是否有五子连线。同样的，也只需要以最后一处落子为中心展开即可。
func (g *Gobang) GameEnd(snapshot *core.MoveSnapshot) (end bool, winner *core.Player) {
target := snapshot.Board[snapshot.I][snapshot.J]
// 遍历「横竖撇捺」四组
for _, group := range dirGroup {
// 累计已连线的个数
tot := 0
// 每组两个相反方向 DFS
for _, dir := range group {
tot += g.dfs(snapshot.Board, target, snapshot.I, snapshot.J, dir[0], dir[1], 0)
if tot > 5 {
// 有胜者
return true, snapshot.Player
}
}
}
// 未结束
for _, row := range snapshot.Board {
for _, sgn := range row {
// 还有空的格子
if sgn == nil {
return false, nil
}
}
}
// 平局（所有格子都满了）
return true, nil
}
DFS 依然轻薄可见，边走边累计
func (g *Gobang) dfs(mat [][]*core.PlaySignal, target *core.PlaySignal, i, j, dx, dy, cnt int) int {
if i < 0 || j < 0 || i >= len(mat) || j >= len(mat[0]) {
return cnt
}
if mat[i][j] != target {
return cnt
}
return g.dfs(mat, target, i+dx, j+dy, dx, dy, cnt+1)
}
就这样，一个五子棋游戏又完成了。
基于游戏框架，我们只需要关注游戏的规则制定，剩下的界面交互、主流程运行，都交给与游戏设计无关的框架来完成即可。
若现在需求要做「四子棋」、加入禁手规则、三人轮流玩等自定义玩法，也能很快基于框架实现。赶快制作自己的游戏吧！
ROI 较低的优化
别问，问就是 ROI 不高。
- 五子棋界面太花了，看不清，可考虑将棋盘颜色调淡一些
- 井字棋/五子棋在胜利时，可增加特殊着色，将连成线的棋子突出显示
- 落子前可考虑跟踪鼠标显示虚拟棋子，使落子更准确
欢迎提出优化 github.com/lzhlyle/board-game/issues ，同样期待你的 PR！
接下来就进入到「人 工(ji) 智(dui) 能(zhan)」框架吧！
人机框架
前文提到
人机框架关注的是计算机如何思考、如何行动。考虑的因素有：如何快速识别一个棋局、模拟更多步棋的落子、准确计算胜率。
先谈谈思考人机框架需要考虑的因素：
我们常说「这种棋局应该…」，这里的「快速识别」，就是在庞大的棋谱库中「快速定位」到当前棋局，并找到应对之策。
我们常会思考对方的走棋，尽量做到多想几步、预判未来，从而对当前落子提供更多信息。计算机相较于人脑，大量的存储和快速的计算则是优势所在。别说人类较强的「多想七步」，那简直是轻而易举，就是多想七十步，也不过几行代码。唯一限制的也只是存储容量与计算速度。
聪明的你一定发现了，「多想几步」，也只是提前做好准备、发现是否藏有杀机、或预设陷阱、或守株待兔，可对方也未必会无脑入坑呀！
没错，这就需要上篇提到的「引入胜率估算」，即每多想一步，都要能精确计算这一步的胜率如何。
灵魂一问：A、B 两个候选落子点，走 A 点的胜率为 40%、B 点的胜率为 30%，A 点就一定比 B 点更优吗？
不是的，还要看「负率」，A 点负率 50%、B 的负率 10%，则说明 A 是一步险棋，适合风险喜好型选手的孤注一掷；B 则更中规中矩，稳中求胜。
接入游戏框架
先在游戏框架里开个口子 Hook ，这是框架之间的桥梁，允许接入像人机一样的更多框架/工具。
// Hook 钩子
type Hook interface {
AIMove(snapshot *MoveSnapshot, moveFn MoveFn) UpdateFn
}
type (
UpdateFn func(gui *gocui.Gui) error
MoveFn func(g *gocui.Gui, v *gocui.View) error
)
消费之处
func NewPlay(bg BoardGame) *Play {
// 初始化 res *Play
if v, ok := bg.(Hook); ok { // use Hook
res.hook = v
}
return res.reset()
}
func (p *Play) beforeRound(g *gocui.Gui) {
if p.currPlayer.AI && p.hook != nil { // use hook
// AI 行动
if fn := p.hook.AIMove(p.snapshot, p.move); fn != nil {
g.Update(fn)
}
}
}
func (p *Play) Play() {
// 游戏初始化...
p.beforeRound(g) // 新一轮开始
// 开始游戏...
}
func (p *Play) move(g *gocui.Gui, v *gocui.View) error {
// 玩家行动..
// 这一轮结束
p.beforeRound(g) // 下一轮开始
return nil
}
func (p *Play) restart(g *gocui.Gui, v *gocui.View) error {
// 重新开局...
p.beforeRound(g) // 新一轮开始
return nil
}
上述代码可知，框架将在适当的时候调用 beforeRound ，进而调用 AIMove 的实现。可以从 bg.(Hook) 得知，框架期望 BoardGame 的实现类也实现 Hook 接口的 AIMove 方法。
为了方便使用，笔者在框架内提供了「默认的人机实现」—— DefaultAIImpl 。
默认的随机策略
type DefaultAIImpl struct {
players []*core.Player
allAI bool
strategies map[ai.Strategy]ai.CalcFunc // 行动策略集
currStrategy ai.Strategy // 当前策略
}
func (t *DefaultAIImpl) AIMove(snapshot *core.MoveSnapshot, moveFn core.MoveFn) core.UpdateFn {
return func(g *gocui.Gui) error {
// 计算应对当前棋局 snapshot 的落子坐标
i, j, err := t.Calculate(snapshot.Board)
// ...
// 落子
return moveFn(g, v) // 框架内暴露出来
}
}
// 计算落子坐标
func (t *DefaultAIImpl) Calculate(curr [][]*core.PlaySignal) (i, j int, err error) {
return t.strategies[t.currStrategy](curr)
}
可以看出，落子坐标的计算导向了 t.strategies 策略集。
策略集只是一个 ai.Strategy 为 key，ai.CalcFunc 为 value 的哈希键值对。
在 /ai/alg.go 可以找到这两个类型的定义：
// ICalculate 走棋计算
type ICalculate interface {
Calculate(curr [][]*core.PlaySignal) (i, j int, err error)
}
type CalcFunc func(curr [][]*core.PlaySignal) (i, j int, err error)
type Strategy int
接下来看看策略集的构建与维护过程：
// 默认策略的 key
const AIStrategyRandom ai.Strategy = 1 + iota
func NewDefaultAIImpl(players []*core.Player) *DefaultAIImpl {
res := &DefaultAIImpl{
players: players,
allAI: true,
currStrategy: AIStrategyRandom,
}
for _, p := range res.players {
res.allAI = res.allAI && p.AI
}
res.strategies = map[ai.Strategy]ai.CalcFunc{
AIStrategyRandom: res.randomStrategy, // 默认加上随机策略
}
return res
}
// 注册策略
func (t *DefaultAIImpl) RegisterStrategy(key ai.Strategy, strategy ai.CalcFunc) bool {
if _, ok := t.strategies[key]; ok {
return false
}
t.strategies[key] = strategy
return true
}
// 设置当前策略
func (t *DefaultAIImpl) SetCurrentStrategy(key ai.Strategy) bool {
if _, ok := t.strategies[key]; !ok {
return false
}
t.currStrategy = key
return true
}
SetCurrentStrategy 设置当前策略，可支持在游戏进行过程中切换思考方式，就好像换了一个对手一样，而不至于游戏重新开始。
最后，让我们来领略一下如何根据一个棋局现状来决定落子坐标，哪怕这只是一个无脑的随机落子的家伙。
func (t *DefaultAIImpl) randomStrategy(curr [][]*core.PlaySignal) (i, j int, err error) {
// 统计可选的点位
optionals := make([][2]int, 0)
for i := range curr {
for j := range curr[i] {
if curr[i][j] == nil {
optionals = append(optionals, [2]int{i, j})
}
}
}
if len(optionals) == 0 {
return -1, -1, ai.ErrCannotMove
}
// 返回随机点位
res := optionals[rand.Intn(len(optionals))]
return res[0], res[1], nil
}
是的，依然平平无奇～
但纵览全局，目前的代码已经完成了最简单的「人机」实现。
10 行井字棋人机，五子棋同理
基于 DefaultAIImpl 默认的随机策略，搭建一个井字棋人机只需区区几行代码
// 井字棋人机
type TicTacToeAI struct {
*TicTacToe // 关联一个井字棋游戏实现
*ai_impl2.DefaultAIImpl // 关联一个默认的人机实现
}
func NewTicTacToeAI() *TicTacToeAI {
res := &TicTacToeAI{
TicTacToe: NewTicTacToe(),
}
res.DefaultAIImpl = ai_impl2.NewDefaultAIImpl(res.TicTacToe.players)
return res
}
// 五子棋人机
type GobangAI struct {
*Gobang // 关联一个五子棋游戏实现
*ai_impl2.DefaultAIImpl // 关联一个默认的人机实现
}
func NewGobangAI() *GobangAI {
res := &GobangAI{
Gobang: NewGobang(),
}
res.DefaultAIImpl = ai_impl2.NewDefaultAIImpl(res.Gobang.players)
return res
}
消费代码
game := concrete.NewTicTacToeAI() // 井字棋
// game := concrete.NewGobangAI() // 五子棋
core.NewPlay(game).Play()
别忘了修改一下初始井字棋时的玩家类型
func NewTicTacToe() *TicTacToe {
return &TicTacToe{
board: &core.Board{
Width: 3,
Height: 3,
MoveLocStyle: core.MoveLocStyle_InCell,
},
players: []*core.Player{
core.NewPlayer("X"), // Human
core.NewAIPlayer("O"), // AI
},
}
}
快来和这位随机落子的傻大个儿开一局吧！
棋盘压缩，偏好排序
欺负傻大个的快感很快就被磨灭，不满足现状才是提升的动力，不是吗？让我们来为井字棋增加一个 smart 的策略吧！
先回顾一下我们人类在进行井字棋对弈时，都在思考什么：
- 对方是不是差一步就赢了？那我得先堵上！
- 我是不是下一步就赢了？那我赶紧连上！
- 谁输谁赢还不一定，那我得选赢面更大的那一步。
上面的人话机器听不懂，咱的翻译翻译：
让计算机先知道（枚举）所有可能的情况。不考虑游戏规则，只考虑落子，共有 9x8x7x...x3x2x1 = 9! = 362,880 种情况。三十六万，小 case 嘛～ 如果再考虑提前结束的终局，会有大量剪枝，总数则更少了。为了描述方便，下文仍以「三十六万」为计井字棋的棋局种类。
这里就涉及到上文提到的「快速定位」棋局，即「如何在三十六万种棋局中找到当前棋局」，「压缩」与「哈希」该上场了：
// IZip 棋盘压缩
type IZip interface {
Zip(mat [][]*core.PlaySignal) interface{}
}
返回值 interface{} ，表示留给实现者的使用空间，建议尽量压成 int32 、 int64 等基础类型。来看看井字棋的压缩效果：
func (t *TicTacToeAI) Zip(mat [][]*core.PlaySignal) interface{} {
// 位运算思路
// 共9个格子，每个格子3种情况：空、X、O
// 2个位可表示4种情况(00, 01, 10, 11)
// 18个位即可表示一个棋盘，返回 int32
res := int32(0b_00_00_00_00_00_00_00_00_00) // 最低2位(右)表示(0, 0)格子
for i, row := range mat {
for j, sgn := range row {
switch sgn {
case t.TicTacToe.players[0].Signal:
res |= 1 << (2 * (3*i + j))
case t.TicTacToe.players[1].Signal:
res |= 1 << ((2 * (3*i + j)) + 1)
}
}
}
return res
}
压缩完的 key 存在哪里呢，这就涉及到「如何记录每一步的胜率」，并在策略中根据一定的思维模式（即某种优先级的排序方式），选择对未来棋局更有利的落子。
在 /ai/alg.go 中可以找到如下定义：
// IChessRecord 棋谱
type IChessRecord interface {
SortRecords(records []*NextRates)
}
// NextRates 下一步胜率集
type NextRates struct {
NextZip interface{}
Rates [3]int // {win, draw, lose}
}
func NewNextRates(nextZip interface{}, rates [3]int) *NextRates {
return &NextRates{NextZip: nextZip, Rates: rates}
}
这里 Rates [3]int 的「胜/平/负率」选择使用 int 表示，是为了比较简单、计算更快速，毕竟我们并不在意胜率具体是 67.834% 还是 67.983% ，大概有个数就行了。故存在「胜+平+负 != 100」的情况，则是因为精度丢失导致的。
IChessRecord.SortRecords() ，即「某种优先级的排序方式」，用来对已知的多种选择，做一个排序。回顾一下上文的「灵魂一问」：
灵魂一问：A、B 两个候选落子点，走 A 点的胜率为 40%、B 点的胜率为 30%，A 点就一定比 B 点更优吗？
不是的，还要看「负率」，A 点负率 50%、B 的负率 10%，则说明 A 是一步险棋，适合风险喜好型选手的孤注一掷；B 则更中规中矩，稳中求胜。
a, b = [3]int{40, 10, 50}, [3]int{30, 60,10}
对于险中求胜者，排序结果也许是 a 优先于 b；而稳中求胜者则相反。
好了，思路整理的差不多了，来看看笔者实现的井字棋 AI 策略是怎样的排序策略：
func (t *TicTacToeAI) SortRecords(rates []*ai.NextRates) {
sort.Slice(rates, func(i, j int) bool {
// 若输率差在 20% 以内，则优先胜率更高的
if math.Abs(float64(rates[i].Rates[2])-float64(rates[i-1].Rates[2])) < 20 {
return rates[i].Rates[0] > rates[j].Rates[0]
}
// 否则，优先输率更低的
return rates[i].Rates[2] < rates[j].Rates[2]
})
}
哈哈，看得出笔者不是一个激进的风险偏好型选手～
别忘了，这只是一个排序。有意思的来了：
- 对于相同的入参（多个可选的落子点），排序的结果是固定的，第一名就一定要选择吗？可否增加一些变换的趣味性 —— 同样的棋局，胜平负率差不多的情况下，这次走这一步试试、下次走那一步试试。
NextRates里只有一个NextZip interface{}的压缩值int32，还没确定(i, j)落子坐标呢！
这是笔者在井字棋中的 smart 策略实现：
func NewTicTacToeAI() *TicTacToeAI {
// 初始化 res
res.DefaultAIImpl = ai_impl2.NewDefaultAIImpl(res.TicTacToe.players)
res.DefaultAIImpl.RegisterStrategy(AIStrategySmart, res.smartStrategy) // 注册 smart 策略
res.DefaultAIImpl.SetCurrentStrategy(AIStrategySmart)
return res
}
func (t *TicTacToeAI) smartStrategy(curr [][]*core.PlaySignal) (i, j int, err error) {
// 当前棋盘的压缩 key
currZip := t.Zip(curr).(int32)
// 从所有（三十六万）棋谱中找到当前棋盘的所有下一步的可能走法
rates := t.ChessRecordGenerator.Zip2NextRates[currZip]
// ...
// 确定下一步走哪里 nextZip
rate := rates[0]
nextZip := rate.NextZip.(int32) // 默认
// 相近结果的多种走法，增加趣味性
if rates[0].Rates[0] < 100 {
// 非必赢的时候
for i := 1; i < len(rates); i++ {
// 输率在 10% 以内，则可任选
if math.Abs(float64(rates[i].Rates[2])-float64(rate.Rates[2])) < 10 {
nextZip = rates[rand.Intn(i)].NextZip.(int32)
}
}
}
// 返回确定落子坐标...
}
是的，为了增加趣味性，笔者在选择下一步棋时，在输率差别不大的情况下做了随机选择，即保证了 AI 看起来不会很明显的「灵光一闪」或者「突然放水」，又增加了不一样棋局出现的场景。
最后得到 currZip 当前棋局与 nextZip 走完下一步后的棋局，进而根据棋局反向的解压缩，定位落子的坐标。这也是为何笔者建议使用二进制压缩的另一个理由：可通过异或运算快速找出差异：
// 确定差异
diff := currZip ^ nextZip
// 求差异的格子值
cell := -1
for diff > 0 { // 最多 9 次
diff >>= 2 // 2 = len(players)
cell++
}
// 确定格子的点位
return cell / 3, cell % 3, nil
返回的 cell/3, cell%3 即落子的 i, j 坐标。
至此，整块人机思考已经完成，万事俱备，只欠「三十六万」棋谱的生成问题了。
枚举胜率棋谱
项目代码来到 /ai_impl/chess_record_generator.go 棋谱生成器。
采用的是枚举方式来生成所有棋谱，想想区区井字棋就已经三十六万种之多，五子棋、围棋、飞行棋、斗兽棋等，岂不基本用不上这种枚举的形式？
是的，肯定不能枚举。但可基于此生成器去改造，思路如：
- 只枚举已有棋子附近的部分区域
- 在原枚举过程中一边计算、一边剪枝
- 完全不用枚举，而是每一步再动态计算落子点位
当然这些在目前的框架里还不包括啦 >.<
先来鸟瞰一下棋谱生成器的全局
type ChessRecordGenerator struct {
chessRecord ai.IChessRecord
zip ai.IZip
boardGame core.BoardGame
// (preZip, nextRates)
Zip2NextRates map[int32][]*ai.NextRates
}
// 生成棋谱
func (gen *ChessRecordGenerator) generate() {
// later @lzh 可考虑多协程并发处理，注意将 Zip2NextRates 改为支持并发的数据结构
gen.dfs(core.NewEmptyMoveSnapshot(gen.boardGame.Board().Width, gen.boardGame.Board().Height), gen.Zip2NextRates)
}
// 通过递归枚举，逐步构建棋谱
func (gen *ChessRecordGenerator) dfs(aSnapshot *core.MoveSnapshot, zip2NextRates map[int32][]*ai.NextRates) *ai.NextRates {
// ...
// dfs() 递归
zip2NextRates[aZip] = gen.sort(gen.filter(allBNextRates))
return ai.NewNextRates(aZip, aRates)
}
// 过滤稳赢/稳输的情况
func (gen *ChessRecordGenerator) filter(rates []*ai.NextRates) []*ai.NextRates {
// ...
}
// 每一层（即每一步）都排好序
func (gen *ChessRecordGenerator) sort(rates []*ai.NextRates) []*ai.NextRates {
if len(rates) == 0 {
return rates
}
if rates[0].Rates[0] == 100 {
return rates // 能赢，无需排序
}
// 调用实现者自定义的 IChessRecord.SortRecords
gen.chessRecord.SortRecords(rates)
return rates
}
源码 120+ 行，相信有兴趣的读者问题不大。
值得一提的是类似经典「Alice & Bob」的动态规划处理：
func (gen *ChessRecordGenerator) dfs(aSnapshot *core.MoveSnapshot, zip2NextRates map[int32][]*ai.NextRates) *ai.NextRates {
// 判断游戏结束，终止递归
// 查找所有可选点位
// 遍历所有可选点位
var aRates = [3]int{}
for i, pos := range bPossibles {
bSnapshot := core.GenSnapshot(aSnapshot.Step+1, pos[0], pos[1], b, aSnapshot)
// 下探一层
bNextRates := gen.dfs(bSnapshot, zip2NextRates)
allBNextRates[i] = bNextRates
// 零和游戏，交叉累计
bRates := bNextRates.Rates
aRates[0] += bRates[2] // a 的胜率 = b 的负率
aRates[1] += bRates[1]
aRates[2] += bRates[0]
}
// 求平均值
for i := 0; i < 3; i++ {
aRates[i] = aRates[i] / len(bPossibles)
}
// 过滤与排序
zip2NextRates[aZip] = gen.sort(gen.filter(allBNextRates))
// 归去来兮
return ai.NewNextRates(aZip, aRates)
}
至此，聪明的 AI 诞生了，领略一下 Ta 的风骚走位吧！
是不是明显有趣多了？都能赢我了…
要是两个 AI 互打…哇喔，想想就刺激，说来就来：
这一刻，我陷入了沉思
看着 Ta 们在棋盘上疯狂地思考、对战厮杀，那么专注、那么乐此不疲
而我，终于放空思绪，呆若木鸡
有那么一刻，仿佛 Ta 们才是有生命的人
花絮小记
从零写框架
说实话，笔者也没写过几次诶 > <
之前做 Java 的时候对 Spring 有些了解，配上一些设计模式的粗浅认识，采用「先实现、再提炼」的方式，就扒拉出来了 —— 都是个人认知的 yy，还要再磨练呀！
代码在半个月前已经提交，本篇起文至今也有一周，考虑到「虽然没人看，但还是要写好」的原则，一再思考行文落笔。对于「搭框架」这件事，这几天又有了一些新的感悟：
框架的上限，还是认知
目标的达成，有其他办法吗？—— 目标 = 接口方法
这个做法，就是唯一的做法了吗？—— 做法 = 方法实现
什么时候需要多想 —— 提炼框架
什么时候是想的太多 —— 过度设计
务实的浪漫
回顾以前做过的一些小玩意，在专项练习的同时，还能保有持续输出的兴趣，原来是一种不错的正循环状态，强烈推荐哟～
就在前天，5月20日，张一鸣同学卸任 CEO 职位的新闻想必大家都知道了，笔者也是感慨，纵使有再繁忙的事务在身，也别忘了我们要去的星辰大海。
一个团队，总有人要仰望星空。
一个人，总要留点时间仰望星空。
一鸣同学真的太浪漫了，选择 520 官宣卸任，直面过去，拥抱更未知的未来。
一鸣同学真的太务实了，有理有据，没有冲动，还是那么冷静。
祝福一鸣！！（破音
最后再上一些花絮图吧，为渐远的网络文字增添一些与现实的关联
下期更新
- 实现运行看板插件：可视化 AI 的思考过程
- 五子棋人机：无法枚举的棋谱，怎么办呢？
- 难度选择：其实就是不同策略嘛，补个前端交互