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

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

文章編號：1672-5913〔2022〕05-0022-03

中圖分類號：G642

1背景

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

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

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

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

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

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

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

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

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

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

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

2.2以經(jīng)典辦法剖析為根底，培養(yǎng)學生的抽象和邏輯思維能力

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

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

2.3由簡到難，培養(yǎng)學生的綜合分析與探索研究能力站在巨人肩膀上學習，是人類在探索世界的過程中不斷進步的基本原因。對于博弈的4個主要局部，應指導學生學會查閱資料，應了解解決目前問題已有的技術(shù)和辦法及其優(yōu)缺點。示例，為了讓計算機下棋，要將所有棋局元素，包括棋盤、棋子、棋局、著法、規(guī)那么、知識等，通過數(shù)字化辦法〔編碼〕轉(zhuǎn)變?yōu)閿?shù)據(jù)元素，各種數(shù)據(jù)元素再以特定關(guān)系構(gòu)成相應的數(shù)據(jù)結(jié)構(gòu)進行存儲和處理。設計一種數(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ù)的異或和，當棋局發(fā)生了變化，只要將相應變化棋子的哈希數(shù)再異或一次，便可以轉(zhuǎn)變成新局面對應的哈希數(shù)。

2.4具體問題具體分析，拿出可行計劃

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

3結(jié)語

培養(yǎng)學生具備計算思維能力，就是培養(yǎng)學生像計算機科學家那樣思維，處理問題時學會從考慮人類與計算機的優(yōu)勢與局限性、要解決問題的復雜度、該類問題目前已有的解決辦法及技術(shù)等方面著手，最后針對當前問題提出具體的算法、數(shù)據(jù)結(jié)構(gòu)、程序語言等解決計劃。計算機博弈是一種既簡單方便、經(jīng)濟實用，又內(nèi)涵豐盛、變化