計算機博弈與“算法設(shè)計與分析”實驗教學(xué)

李淑琴?李寧?劉均梅

摘要：目前“算法設(shè)計與分析”課程的實驗題目主要以驗證課堂所講的理論為主，不利于培養(yǎng)學(xué)生的學(xué)習(xí)興趣、創(chuàng)新意識和能力。提出將計算機博弈競賽項目與“算法設(shè)計與分析”實驗教學(xué)題目相結(jié)合的觀點，并論述了兩者結(jié)合的意義和可行性。

關(guān)鍵詞：算法設(shè)計與分析；計算機博弈；實驗教學(xué)

作者簡介：李淑琴（1963-），女，北京人，北京信息科技大學(xué)計算機學(xué)院，教授；李寧（1964-），男，北京人，北京信息科技大學(xué)計算機學(xué)院，教授。（北京?100101）

基金項目：本文系校研究生優(yōu)質(zhì)課程建設(shè)項目（項目編號：YKJ201104）、校研究生科技創(chuàng)新和實踐能力培養(yǎng)項目、校教學(xué)改革研究項目（項目編號：2010JG19）的研究成果。

中圖分類號：G642.0?????文獻標(biāo)識碼：A?????文章編號：1007-0079（2012）20-0093-02

“算法設(shè)計與分析”是計算機科學(xué)的核心問題之一，是計算機科學(xué)與技術(shù)專業(yè)本科及研究生的一門重要的專業(yè)基礎(chǔ)課，也是計算機軟件開發(fā)人員的必修課?！八惴ㄔO(shè)計與分析”課程主要針對生活中經(jīng)常遇到的實際問題，講授如何設(shè)計并實現(xiàn)計算機算法的基本原理、思想、方法與技術(shù)，從而使學(xué)生在選擇或者設(shè)計算法時可以對其進行時空耗費分析，使算法的時空復(fù)雜性最優(yōu)，進而為其編寫出高效程序、開發(fā)出優(yōu)秀軟件系統(tǒng)奠定基礎(chǔ)。

近年來北京信息科技大學(xué)招考的計算機專業(yè)的研究生中，本科不是計算機科學(xué)或相關(guān)專業(yè)畢業(yè)卻想攻讀計算機科學(xué)碩士學(xué)位的學(xué)生比例不斷加大，這些學(xué)生來自全國各地不同類型的學(xué)校，對應(yīng)該在本科生階段掌握的計算機專業(yè)的理論深度與廣度的把握有較大差別，學(xué)生普遍編程能力較弱，遠達不到靈活運用的程度。而“算法設(shè)計與分析”課程是理論與實踐并重的課程，是一門集應(yīng)用性、創(chuàng)造性及實踐性融為一體的課程。學(xué)生通過學(xué)習(xí)算法設(shè)計與分析課程可以開闊編程思路，編寫出高效程序，對學(xué)生分析問題、解決問題的能力培養(yǎng)起到非常重要的作用。

目前北京信息科技大學(xué)算法課設(shè)置為計算機專業(yè)碩士研究生的一門專業(yè)基礎(chǔ)課，32學(xué)時。為了提高學(xué)生的綜合能力，我們對該課程的實踐題目上下功夫，主要設(shè)計了兩個方面的題目。

第一類題目，稱為驗證型小實踐。主要是將課堂討論的理論加以驗證，一方面加深對理論的理解，另一方面鍛煉編程能力。這部分作業(yè)是實現(xiàn)算法課的最基本要求，因此要求每個學(xué)生必須獨立并保質(zhì)保量地完成。

第二類題目，稱為應(yīng)用型大實踐。作為研究生僅僅停留在算法的驗證上還是不夠的，要使學(xué)生能夠跟上技術(shù)發(fā)展的步伐，增強就業(yè)競爭力，就要加強創(chuàng)新能力培養(yǎng)，全面提高分析問題和解決問題的能力，提高靈活應(yīng)用經(jīng)典算法和當(dāng)前的新技術(shù)進行程序設(shè)計的能力。將計算機博弈競賽題目作為“算法設(shè)計與分析”課程綜合實踐題目是一個可行方案。

一、計算機博弈與“算法設(shè)計與分析”

計算機博弈，顧名思義就是讓計算機擁有人的思維去進行博弈游戲，能夠像人一樣下棋。計算機博弈是既簡單方便、經(jīng)濟實用又內(nèi)涵豐富、變化無窮的思維邏輯的研究載體，它在國際上作為一個學(xué)科領(lǐng)域，已經(jīng)開展了半個多世紀的研究與競賽活動，經(jīng)過了波瀾壯闊的艱苦歷程。1997年5月IBM“深藍”計算機戰(zhàn)勝世界棋王卡斯帕羅夫，成為計算機博弈和人工智能的里程碑。目前，無論在國際還是國內(nèi)，計算機博弈比賽每年舉辦一次，競賽項目包括六子棋、點格棋、蘇拉卡爾塔棋、亞馬遜棋、幻影圍棋、中國象棋、圍棋、九路圍棋等項目。

編寫一個好的計算機博弈程序需要涉及數(shù)據(jù)結(jié)構(gòu)、編程語言、程序設(shè)計方法、軟件工程、并行計算等綜合知識，可以綜合提高學(xué)生的實踐創(chuàng)新能力。

一個完整的機器博弈系統(tǒng)主要包括棋局表示、著法生成器、搜索引擎以及評估函數(shù)四部分。

棋局表示是對比賽過程中形成的棋局的描述，涉及數(shù)據(jù)結(jié)構(gòu)的選擇，其中包括棋盤、棋子、障礙、空格、棋局、走棋表示的編碼與存儲。良好的數(shù)據(jù)結(jié)構(gòu)可以節(jié)省大量的存儲空間，可以提高存取的效率。為了適應(yīng)博弈樹的展開與搜索，常常還要同時給出棋局的多種數(shù)據(jù)格式。如棋局狀態(tài)、棋子位置、比特棋局和比特向量，還要用到哈希變換和哈希表等。

著法生成器是在已形成的棋局下生成可行的著法，涉及對下棋規(guī)則的描述并根據(jù)規(guī)則生成所有可行著法，是搜索對象的產(chǎn)生器。

搜索引擎是如何找到最優(yōu)著法，這是計算機博弈的核心部分，是對人類思維模擬的最佳體現(xiàn)。搜索算法包括著法生成、博弈樹展開、各種剪枝搜索和各種啟發(fā)式搜索。涉及的核心問題覆蓋了常見的算法設(shè)計策略。

局面評估就是對棋局進行評估，是搜索算法的前提。棋局的靜態(tài)評估是計算機博弈的另一個難點，它不僅需要棋類對弈的基本知識，而且用到直接量化、模式量化、隨機評估、模糊評估等一系列手段。例如象棋，可以給每個棋子和棋位打分，而對于圍棋則要進行定式的抽取和模式的匹配。

以上這些問題都是算法設(shè)計課程的涉及內(nèi)容，也是研究生今后研究工作涉及的主要方面之一。

（1）競賽程序的實現(xiàn)有時間、空間限制，能很好地反映算法設(shè)計與分析技巧在程序設(shè)計中的應(yīng)用意義。

（2）競賽項目難度適中。計算機博弈被稱為人工智能的“果蠅”，因為它具有周期短、變化多、容易實現(xiàn)、便于檢查的特點。個把小時就可以下一盤棋，就可以對電腦的“智能”進行測試，而且可以悔棋、重試、復(fù)盤。

（3）競賽富有挑戰(zhàn)性，趣味盎然。通過編寫、調(diào)試程序，讓計算機下棋，一步步地發(fā)現(xiàn)電腦與人腦功能的差距，從而不斷提高電腦的智力水平。與所學(xué)專業(yè)知識有密切關(guān)系，有效激發(fā)學(xué)生對計算機技術(shù)的興趣。

（4）競賽要求綜合運用多種知識，有助于學(xué)生理解所學(xué)內(nèi)容之間的相互關(guān)系，并創(chuàng)造性地考慮問題。

（5）競賽項目與課程題目掛鉤，一舉多得。作業(yè)完成得好的學(xué)生可以參加全國競賽，獲得獎項還能提升就業(yè)機會，同時也在一定程度上提高學(xué)校的知名度，促進良好校風(fēng)的形成。

二、綜合實驗的實施與評定

實踐主要以提交課程報告形式，考核學(xué)生算法分析與設(shè)計的綜合能力。課程報告內(nèi)容包括算法設(shè)計、算法實現(xiàn)、算法效率分析、程序測試等。對于小實踐作業(yè)根據(jù)學(xué)生撰寫報告內(nèi)容、程序的質(zhì)量綜合給分。對于大實踐作業(yè)主要通過集中匯報的方式，驗收、比較程序的運行效率。另外參考是否參加科技競賽、是否獲得獎項、是否做出不錯的科研成果以及是否發(fā)表學(xué)術(shù)論文等綜合因素給分。

目前綜合實驗作業(yè)的完成是采取3～4個學(xué)生組織成研究小組的方式進行的。分組上采取學(xué)生自由組合，選題上采用任意挑選競賽題目的方式。要求小組中每個學(xué)生都要有明確的任務(wù)分工，期末匯報自己所做的工作；每組推選一位小組長，負責(zé)整個小組的組織和協(xié)調(diào)工作。通過這種分組和匯報的形式大大提高了學(xué)生團隊合作和學(xué)術(shù)交流的能力，對他們將來從事科研工作或找工作都起到很好的幫助作用。

綜合實踐作業(yè)完成情況的評定主要由三個方面組成。一是提交課程報告。課程報告內(nèi)容包括算法設(shè)計、算法實現(xiàn)、算法效率分析、程序測試等，考核學(xué)生算法分析與設(shè)計的綜合能力。二是集中匯報。每個人敘述自己所做的工作，驗收程序能否執(zhí)行、同一題目的小組之間進行比賽，比較程序的運行效率。三是提供輔助材料。參考學(xué)生是否參加科技競賽、是否獲得獎項、是否做出不錯的科研成果以及是否發(fā)表學(xué)術(shù)論文等綜合因素給分。

三、小結(jié)

近兩年來，筆者將計算機博弈競賽項目與“算法設(shè)計與分析”實驗教學(xué)題目相結(jié)合取得良好效果。作業(yè)完成得好的學(xué)生參加了兩屆全國計算機博弈大賽，取得點格棋項目組季軍、六字棋、蘇拉卡爾塔棋和亞馬遜棋二等獎的好成績。實踐表明，提出的將計算機博弈競賽和“算法設(shè)計與分析”課程教學(xué)相結(jié)合的觀點是可行的，有助于培養(yǎng)學(xué)生的學(xué)習(xí)興趣和創(chuàng)新意識，有助于學(xué)生創(chuàng)新能力、實踐能力、編程能力、自學(xué)能力、協(xié)作能力、分析和解決問題能力等多方面能力的培養(yǎng)，提高了學(xué)生在今后社會工作的素質(zhì)和能力，符合21世紀計算機科學(xué)與技術(shù)專業(yè)人才培養(yǎng)的要求。

參考文獻：

[1]徐子珊.“算法設(shè)計與分析”教學(xué)中理論與技術(shù)的平衡[J].計算機教育,2008,10(2):72-73.

[2]徐心和,鄧志力,王驕,等.機器博弈研究面臨的各種挑戰(zhàn)[J].智能系統(tǒng)學(xué)報,2008,3(4):288-293.

[3]楊春明,陳念年.基于競賽模式的“算法分析與設(shè)計”教學(xué)探索與實踐[J].計算機教育,2009,(20):146-147.

[4]李淑琴,趙延,劉均梅.機器人足球仿真競賽與程序設(shè)計能力培養(yǎng)[J].計算機教育,2010,(13):31-32.

[5]張云洲,吳成東,崔建江,等.基于機器人競賽的大學(xué)生創(chuàng)新素質(zhì)培養(yǎng)與實踐[J].電氣電子教學(xué)學(xué)報,2007,29(1):116-119.

（責(zé)任編輯：王祝萍）