計算機博弈教學(xué)中的計算思維能力培養(yǎng)

李淑琴+丁濛+孟坤

摘 要：在強調(diào)計算思維重要性的基礎(chǔ)上，提出以學(xué)生喜聞樂見的、高對抗性的棋牌游戲為教育和研究載體，將計算思維能力培養(yǎng)貫穿于計算機博弈系統(tǒng)的實踐教學(xué)中，具體闡述如何通過計算思維概念的建立、經(jīng)典方法剖析、具體問題具體分析等手段，由淺到深地培養(yǎng)學(xué)生的形式化描述、抽象思維和邏輯思維能力。

關(guān)鍵詞：計算機博弈；計算思維能力；棋牌游戲

文章編號：1672-5913（2017）05-0022-03

中圖分類號：G642

1 背 景

計算思維是運用計算機科學(xué)的思想與方法進行問題求解、系統(tǒng)設(shè)計、人類行為理解等涵蓋計算機科學(xué)之廣度的一系列思維活動[1]。在信息化時代，計算思維是一種和邏輯思維一樣的基本能力。美國卡內(nèi)基·梅隆大學(xué)周以真教授認為，與“讀寫算”一樣，計算思維應(yīng)該是21世紀每個人都必須具備的基本技能[1]。蔣宗禮教授認為：一個人若不具備計算思維能力，將在從業(yè)競爭中處于劣勢；一個國家若不能使廣大受教育者得到計算思維能力的培養(yǎng)，在激烈競爭的國際環(huán)境中將處于落后地位[2]。教育部高等學(xué)校大學(xué)計算機課程教學(xué)指導(dǎo)委員會于2010年7月發(fā)表了《九校聯(lián)盟（C9）計算機基礎(chǔ)教學(xué)發(fā)展戰(zhàn)略聯(lián)合聲明》，正式提出計算思維教學(xué)改革宣言[3]。宣言明確指出：要旗幟鮮明地把計算思維能力的培養(yǎng)作為計算機基礎(chǔ)教學(xué)的核心任務(wù)，加強以計算思維能力培養(yǎng)為核心的計算機基礎(chǔ)教學(xué)課程體系和教學(xué)內(nèi)容的研究。

近幾年來，為了在計算機基礎(chǔ)教學(xué)中加強對計算思維能力的培養(yǎng)，筆者嘗試以計算機博弈為落腳點，通過計算機博弈教學(xué)提升學(xué)生的計算思維能力。計算思維能力主要包括以形式化和模型化為基礎(chǔ)的形式化描述、抽象思維與邏輯思維能力[2]，棋類對弈過程集中展現(xiàn)出來的邏輯思維、形象思維和靈感思維完美地覆蓋了計算思維能力涉及的各個方面，而計算機博弈恰好是棋類對弈這種人類高級思維活動的直接模擬。一個計算機博弈項目的實施涵蓋了下棋規(guī)則問題的描述：棋盤、棋子障礙、空格、棋局、走棋表示等形式化數(shù)據(jù)描述；存儲方式的選取；搜索算法、評估函數(shù)模型的計算機描述；并行程序設(shè)計思想和問題求解的效率。

2 計算機博弈中的計算思維能力培養(yǎng)

2.1 通過遞進式教學(xué)，學(xué)生建立起計算思維概念

人類博弈的棋種很多，全國大學(xué)生計算機博弈大賽暨全國計算機博弈錦標賽2016年的比賽共設(shè)置了17個項目，大學(xué)生項目包括五子棋、六子棋、不圍棋、點格棋、蘇拉卡爾塔棋、亞馬遜棋、幻影圍棋、愛恩斯坦棋、軍棋、海克斯棋10種棋類；錦標賽項目包括中國象棋、圍棋、13圍棋、9路圍棋、國際跳棋（100格）、國際跳棋（64格）、二打一撲克牌（斗地主）7種棋牌類。教學(xué)中筆者發(fā)現(xiàn)學(xué)生根據(jù)興趣選定一個棋種后，常常不知如何下手。此時，筆者給學(xué)生引入計算思維的概念，即遇到具體問題時，首先考慮人類與計算機各自解決該問題的優(yōu)勢以及問題的可計算性。

人類在處理復(fù)雜的決策與對策問題時，主要依靠思考，而思考過程就是在腦海中搜索的過程，即根據(jù)腦中存儲的數(shù)據(jù)、知識、經(jīng)驗、方法、關(guān)系等，力圖在可能的著法中找到最佳的著法（“解”）。人類下棋具有全局觀或?qū)従钟^，缺點是人類思考的深度有限。計算機下棋就是模仿人類下棋的思考過程，主要方法是在龐大的狀態(tài)空間和博弈樹中搜索。計算機的優(yōu)勢在于強勁的計算力，每秒可以計算上萬億個節(jié)點，但缺點是審局觀差，很有可能一招不慎滿盤皆輸。

博弈樹是一種形式化描述方法，通過介紹博弈樹，讓學(xué)生對形式化描述棋類博弈的過程有一個直觀的認識，進而引導(dǎo)學(xué)生深刻理解對實際問題進行形式化描述的含義。

計算機并不能解決生活中所有的實際問題，因此學(xué)生在編寫程序前需要了解要解決問題的復(fù)雜度，即問題的可計算性。筆者通過描述博弈樹廣度和寬度的含義，以具體棋種的博弈樹為例，讓學(xué)生理解復(fù)雜度的概念。表1展示了幾種不同棋種的近似棋局狀態(tài)數(shù)目。

由此，引導(dǎo)學(xué)生從計算機資源的角度分析解決問題的時間復(fù)雜度（要通過多少步才能解決問題）和空間復(fù)雜度（在解決問題時需要多少內(nèi)存）。

當(dāng)學(xué)生認識到完全展開常見棋類的博弈樹是不可能完成的任務(wù)后，介紹如何將博弈樹規(guī)模降低到計算機可解決的范圍內(nèi)，即評估函數(shù)和剪枝搜索算法。

至此，學(xué)生明白了一個計算機博弈系統(tǒng)程序至少包括棋局表示、走法生成、搜索引擎以及局面評估函數(shù)4個部分。棋局表示是對比賽過程中形成的棋局的描述。走法產(chǎn)生是將一個局面的所有可能走法羅列出來的程序。不同棋類由于規(guī)則不同，走法產(chǎn)生的復(fù)雜程度也有很大區(qū)別。搜索是如何找到最優(yōu)著法，這是計算機博弈的核心部分。局面評估就是對棋局進行評估，是搜索算法的前提，要編寫局面評估函數(shù)向人類學(xué)習(xí)如何審局。

2.2 以經(jīng)典方法剖析為基礎(chǔ)，培養(yǎng)學(xué)生的抽象和邏輯思維能力

對于博弈樹的搜索，經(jīng)典的搜索方法是極大極小搜索算法。通過對極大極小搜索算法的剖析，使學(xué)生深刻理解該算法背后的原理以及該算法可以選出最優(yōu)結(jié)果的核心邏輯，訓(xùn)練學(xué)生的分析能力和邏輯思維能力，通過該算法遞歸實現(xiàn)的實例演示，強化學(xué)生的抽象空間思維能力。通過具體特例，向?qū)W生展示該算法可以被進一步優(yōu)化的原因，然后介紹Alpha-Beta剪枝算法，通過具體實例演示，學(xué)生先對AB剪枝算法產(chǎn)生直觀的認識，而后對其算法進行剖析，強化訓(xùn)練學(xué)生的邏輯思維能力，即對于某些滿足特定條件的局面，為什么不用繼續(xù)進行極大極小搜索。

再如，對于某些很難給出評價函數(shù)的棋類（如圍棋），研究人員提出使用蒙特卡洛方法，通過大量隨機模擬對弈的結(jié)果得到著法。這種方法的底層有一個堅實的數(shù)學(xué)基礎(chǔ)，上層使用并行計算，通過計算、模擬、采樣、優(yōu)化等一系列數(shù)學(xué)方法獲得評估結(jié)果。AlphaGo采用蒙特卡洛樹加深度學(xué)習(xí)的方法使計算機圍棋技術(shù)有了明顯的提高。

2.3 由簡到難，培養(yǎng)學(xué)生的綜合分析與探索研究能力

站在巨人肩膀上學(xué)習(xí)，是人類在探索世界的過程中不斷進步的根本原因。對于博弈的4個主要部分，應(yīng)指導(dǎo)學(xué)生學(xué)會查閱資料，應(yīng)了解解決目前問題已有的技術(shù)和方法及其優(yōu)缺點。例如，為了讓計算機下棋，要將所有棋局元素，包括棋盤、棋子、棋局、著法、規(guī)則、知識等，通過數(shù)字化方法（編碼）轉(zhuǎn)變?yōu)閿?shù)據(jù)元素，各種數(shù)據(jù)元素再以特定關(guān)系構(gòu)成相應(yīng)的數(shù)據(jù)結(jié)構(gòu)進行存儲和處理。設(shè)計一種數(shù)據(jù)結(jié)構(gòu)表示一種棋類游戲的狀態(tài)往往要考慮幾個方面的問題：占用的空間大小、操作數(shù)據(jù)的速度、使用方便與否。

以往，博弈棋盤的實現(xiàn)有兩種：一是數(shù)組棋盤，二是位棋盤。數(shù)組棋盤就是定義一個數(shù)組，并利用數(shù)組的每個元素標示棋盤中每個位置的棋子情況。位棋盤亦稱比特棋盤，用棋子狀態(tài)條件的布爾值表示。棋局的存儲也可采用Zobrist哈希技術(shù)實現(xiàn)，哈希數(shù)的最大優(yōu)點在于它計算的是64位數(shù)的異或和，當(dāng)棋局發(fā)生了變化，只要將相應(yīng)變化棋子的哈希數(shù)再異或一次，便可以轉(zhuǎn)變成新局面對應(yīng)的哈希數(shù)。

2.4 具體問題具體分析，拿出可行方案

了解了現(xiàn)有技術(shù)，就需要針對具體的項目給出可行方案。例如，“深藍”憑借強大的計算能力，借助窮舉法窮盡了國際象棋對弈的所有變化，取得了勝利，但對于圍棋，計算機如果仍借助窮舉推算，是不可能獲得所有變化的。蒙特卡洛算法并不是全新算法，AlphaGo除了使用蒙特卡洛樹進行搜索外，還采用了基于機器學(xué)習(xí)的神經(jīng)網(wǎng)絡(luò)。神經(jīng)網(wǎng)絡(luò)有很大的作用：第一是通過學(xué)習(xí)高水平棋手的棋譜，獲得如何在盤面落子的棋感；第二是通過機器的增強型學(xué)習(xí)，獲得形勢判斷的棋感。這兩個棋感通過蒙特卡洛樹搜索技術(shù)進行驗證，使AlphaGo實現(xiàn)了技術(shù)突破。

3 結(jié) 語

培養(yǎng)學(xué)生具備計算思維能力，就是培養(yǎng)學(xué)生像計算機科學(xué)家那樣思維，處理問題時學(xué)會從考慮人類與計算機的優(yōu)勢與局限性、要解決問題的復(fù)雜度、該類問題目前已有的解決方法及技術(shù)等方面著手，最后針對當(dāng)前問題提出具體的算法、數(shù)據(jù)結(jié)構(gòu)、程序語言等解決方案。計算機博弈是一種既簡單方便、經(jīng)濟實用，又內(nèi)涵豐富、變化無窮的思維邏輯研究載體，以學(xué)生喜聞樂見的、高對抗性的棋牌游戲作為教育和研究載體，將計算思維能力培養(yǎng)貫穿于計算機博弈系統(tǒng)實現(xiàn)的教學(xué)中，大大調(diào)動了學(xué)生的學(xué)習(xí)與研究熱情。近6年來，筆者所在單位的學(xué)生在全國大學(xué)生計算機博弈比賽中，獲得冠、亞、季軍10余次，累計獎項50余項，這表明計算機博弈確實是提升學(xué)生計算思維能力的有效途徑。

參考文獻：

[1] Jeannette M Wing. Computational Thinking[J]. Communications of the ACM， 2006， 49（3）： 33-35.

[2] 蔣宗禮. 計算思維之我見[J]. 中國大學(xué)教學(xué)， 2013（9）： 5-10.

[3] 何欽銘， 陸漢權(quán)， 馮博琴. 計算機基礎(chǔ)教學(xué)的核心任務(wù)是計算思維能力的培養(yǎng)[J]. 中國大學(xué)教學(xué)， 2010（9）： 5-9.

[4] 李淑琴. 北京信息科技大學(xué)計算機博弈競賽及創(chuàng)新基地建設(shè)情況介紹[J]. 中國人工智能學(xué)會通訊， 2015（12）： 15-17.

[5] 王亞杰， 邱虹坤， 尹航. 計算機博弈競賽與創(chuàng)新人才培養(yǎng)模式改革[J]. 實驗技術(shù)與管理， 2016， 33（10）： 10-14.

（編輯：孫怡銘）