計算機博弈教學中的計算思維能力培養

李淑琴+丁濛+孟坤

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

關鍵詞：計算機博弈；計算思維能力；棋牌游戲

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

中圖分類號：G642

1 背 景

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

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

2 計算機博弈中的計算思維能力培養

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

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

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

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

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

由此，引導學生從計算機資源的角度分析解決問題的時間復雜度（要通過多少步才能解決問題）和空間復雜度（在解決問題時需要多少內存）。

當學生認識到完全展開常見棋類的博弈樹是不可能完成的任務后，介紹如何將博弈樹規模降低到計算機可解決的范圍內，即評估函數和剪枝搜索算法。

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

2.2 以經典方法剖析為基礎，培養學生的抽象和邏輯思維能力

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

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

2.3 由簡到難，培養學生的綜合分析與探索研究能力

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

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

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

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

3 結 語

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

參考文獻：

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

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

[3] 何欽銘， 陸漢權， 馮博琴. 計算機基礎教學的核心任務是計算思維能力的培養[J]. 中國大學教學， 2010（9）： 5-9.

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

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

（編輯：孫怡銘）