黑白棋出现pass 的条件 java_JAVA黑白棋之学习感悟
前言
這是我來到藍杰之后的第一個學習感悟,階段成果也是我第一個覺得小有成就的作品,不在于所用的知識有多么高深,而在與這是第一個凝結了失敗、努力、成功這樣頗有曲折經歷的項目,使我收獲頗多。
下面切入正題,當學完做畫板之后,面臨的一個選擇就是做五子棋或者黑白棋,雖然對于我而言,五子棋要比黑白棋在行的多,但由于考慮到機器搜索的代價,我便毫不猶豫地選擇了制作黑白棋的小游戲,畢竟不是我去對弈,而是要“教”機器如何對弈。
至于我所謂的搜索代價,便是對機器而言,所面臨的需要搜索的節點數。不妨拿黑白棋和五子棋做個對比。首先,黑白棋的棋盤是8*8的,而五子棋的棋盤是15*15的,就這個層面講,無論是空間上還是時間上,對五子棋落子的搜索的代價都要比黑白棋要高;其次,黑白棋每輪下子的位置是有要求的,這便進一步減少了節點的數量,而五子棋則理論上可以下在棋盤上的任何一個空位(當然是有特殊情況的,比如你不能眼睜睜地看著別人出殺招);再者,基于上面兩點,五子棋較黑白棋來講,電腦是更難發起有效進攻的。
當然,黑白棋也有難以處理的地方,比如每下一步,不僅改變了自己棋子的狀態,同時也會改變棋盤上對方棋子的狀態,那么在深搜的過程中,便不能像五子棋那樣先是嘗試一個位置,然后深搜,最后再把嘗試的痕跡抹掉,這樣只用一個二維數組就可以了,而由于黑白棋中對翻轉的棋子進行還原是很麻煩的,所以在深搜的過程中,便只能不斷new一個二維數組,然后再傳遞翻轉后的棋盤,這樣便增大了額外的內存開銷。
版本經歷
老爸曾在我和他談想進藍杰的時候教育過我:“學習是好事,但千萬不要好高騖遠”,起初我聽過龍哥安排我做黑白棋的計劃之后,便陷入了無限的憧憬之中,幻想著自己的黑白棋會多么多么厲害(至少要打敗某某的黑白棋程序,并且讓某某打敗不了我的程序,有點小邪惡- -!……),但卻只是一味的想象,甚至連個框架都沒有做出來,一上午都顯得很毛躁。在龍哥的警醒下,我下午終于開始先投入精力至少把框架做出來,原來想象中的簡單的事情其實也并不是那么簡單,但至少當晚磕磕絆絆地把雙人模式的雛形已經搞出來了,至少走棋的模塊是沒有問題了。
接下來便是對界面的美化和人機算法進行研究了。界面美化其實也不算重點,有了仿WIN7畫板的經歷之后,對Swing組件還是有了一定的了解和應用能力的,因此界面應該不會是大問題。也正如龍哥所說,如果做黑白棋,不把人機算法好好研究一番,是沒有意思的,因此,接下來的主要任務便是拿下人機算法模塊。
由于有了前面李眾力的經驗,我還算很快就把一個簡單的BOT操作的模塊寫出來了,就是依賴格子的權值,盡可能地先占角和邊,而盡量不去碰“C位”(兩條邊上的與角相鄰的的格子)和“星位”(除了C位的另一個和角相鄰的位置)。
有了這個思想,很容易想到,如果我的BOT能夠再往下看一步該多好,因為如果BOT走了一步棋,而Player下一步走了角或者邊上的其他有利位置,那么我的BOT不就虧了么,于是在原有的基礎上,又堆砌了一些代碼來判斷下一步Player可能走的地方。就這樣,v1.0就成型了。
但是后來經測試發現,如果只用權值去判斷到底走哪里好是很吃虧的,因為我很輕松就把它下贏了,這時便試圖去找一些更好地判斷方法。
也許是有點急功近利的心態吧,找到的一些比較高深的資料和論文自己根本沒心思看下去(寫到這里,又聯想到了龍哥的一句話:“你要想趕進度,我一天讓你做一個項目都可以,但關鍵是你要去想怎么把這個項目做精致,你要用心去觀察細節,學會把軟件做得精致一些。”),后來便找了一個也是大概同齡的學生寫的一個用C語言做黑白棋的報告,他是用行動力(就是每輪能夠下子的位置的總數)來作為對棋局評估的標準的,而且還說這樣棋力還不錯,我一想這個挺好的,于是便把思想拿來用了,用了大概半天的時間把這個模塊寫完,并和之前的程序融合到了一起,v2.0便成型了。
然而好景不長,這樣做出的程序依然很傻,到了晚上在藍杰測試的時候,我格外沮喪。這時胡zong開始語重心長地教育我:“哦,你的意思就是說你現在這個黑白棋就相當于3歲的小孩子撒,智力還很低,但你可以每天讓它漲一點撒,我們不多算,你就一個月讓它長一歲,你算算,等到你大四畢業,我靠,它得多……所以你只要不放棄就行,是不?”
聽完胡zong的,我便靜下心來了,晚上回去之后便開始研究起一個中科大學生(柏愛俊)寫的關于黑白棋算法研究的一個論文,同時又開始研究起玄黃整理版的黑白棋對弈策略指南。事后反思的時候,研究這兩個東西才是真正奠定了我的程序的黑白棋算法的基礎,給了我頗多的啟示。首先,單由點權去判定每個點的優劣是絕對行不通的,因為你即使讓對方只剩一顆棋子,他也有可能最后將局面反敗為勝,而且每個點的優劣也是依具體情況而定的;其次,做人機算法,就要充分發揮機器的優勢——快速而精準的暴力,因而在時間允許的范圍內,讓機器多想一點總比少想一點要好;再者,印證了我之前對極大極小搜索理論的一些想法,確立了用深搜的形式去暴力各種可能情況的算法,并限定深搜的層數。
有了上面的感悟,第二天我便把v2.0的人機算法模塊抹掉,重新開始以遞歸的形式去描述我的算法,經過一天的努力,v3.0終于調試成功了。
后一天的早晨我便迫不及待地讓龍哥玩上一把,畢竟如果能贏龍哥還是會很高興的,(*^__^*)。結果龍哥一開始有時候走得太快了,于是便馬失前蹄,被我的程序意外地占了更多優勢,但后來仔細行棋的話,還是可以比較容易地拿下我的BOT的。雖然聽完龍哥說我的這個程序還是滿厲害的,但我還是有些不知足,畢竟還是讓龍哥比較輕松地贏了的。
在后續完善v3.0的過程中,我發現限定深搜的層數有時并不是那么理想,因為如果每層只有很少的節點,那么實際上還是有充足的時間搜索更多步的,何樂而不為呢?于是我便把限定搜索層數改成了限定搜索節點數,這樣便使程序能夠更加有效地利用有限的時間了。
同時,在和別人下的過程中,還發現了對于最終棋局的判定是不宜只著眼于位置的。因為即使你占得位置再好,最后子數少也是明顯不行的。于是便改變了雙方都無子可下時的對棋局的評估函數,這時便著眼于子數的優勢了。
周六的晚上,我便又開始依照那篇論文的指導思想開始研究剪枝優化的博弈樹搜索,也即α-β搜索,由于有了前面MIN-MAX搜索代碼的基礎,在晚上比較晚的時候我便比較容易地寫完了α-β搜索的代碼,v4.0便研發成功了,同時這時一個可喜的戰果便是,我的白棋贏了百度應用上面日文版的那個黑白棋的黑棋(因為這個版本被龍哥評為比較厲害的版本,所以會比較高興),盡管我的黑棋贏不了它的白棋……同時我抱著僥幸的心理挑戰了一下百度應用的聰明黑白棋,結果毫不猶豫地戰敗了……
周日的時候,我便在QQ上面開始用我的程序進行實戰了,大概能到70%的勝率吧,而且還下贏過2000多分的。欣喜之余,我發現有些時候我的BOT會很傻,尤其是最后幾步,有時對手能接連讓我停步好多次,然后戰勝我。后來直到晚上很晚的時候,我突然意識到了我對α-β搜索中有一方pass的處理是有BUG的,到周一中午的時候,我終于把這個BUG修復了,但我發現反倒贏不了之前的日文版的黑白棋了(BUG+BUG也許會減輕BUG的影響,但當消除一個BUG時,另一個BUG的問題就暴漏地很明顯了……),這時我才更加意識到了評估函數的重要性,便又仔細修改了評估函數的值,重新又贏下了日文版,而且這次黑棋也能贏下它的白棋,我便把這個版本記作了v4.5,但我依然贏不下聰明黑白棋。
于是我便又有些沮喪,開始寄希望于網上的資料,結果把從一個外國的論文上找下的一個權值表用上之后,反倒BOT變傻了。吃晚飯回來后,我便仔細分析了一下權值表,覺得它這個權值的分布還是有道理的,同時又結合了我的一些實戰的經驗以及我原創并修改的權值表,對摘過來的外國的權值表上的一些值的影響進行了削弱,并將一些權值的影響進行了加強,并依現在的權值表,對最終的線性合并評估值的常數比例進行了適當的修改,之后我便拿這個程序又抱著僥幸的心理去打聰明黑白棋,這次居然完成了我一周以來夢寐以求的心愿——終于將其打敗了O(∩_∩)O!之后便把這個加強之后版本命名為v4.7。
所謂有目標才能有動力,有動力才能有成功,現在百度應用上比較厲害的黑白棋已經被我的BOT戰勝了,希望我還能有更多地動力繼續將論文上的歷史表和置換表的知識融入到我的程序之中,讓我的BOT變得更聰明,加油哈!
后記
此篇僅作一個階段性的感悟的匯總和留念,具體的開發JAVA黑白棋過程中應用到的各種算法,我還在匯總之中,相信不久就能成文了。
另附我開發的v4.7的黑白棋程序,大家疲勞之時可以娛樂一番,如果有什么建議和指導,還望大家不吝賜教O(∩_∩)O~。
P.S.由于我沒有標記誰下在了哪里,所以有可能有時電腦走完子之后并不能引起我們的視覺注意,但是從當前持子那個位置可以看出來是該誰接著下了,這個問題我會在之后的版本予以修正和改善,我對因此給各位在游戲中帶來的不便表示歉意,謝謝各位對我的諒解和支持。
總結
以上是生活随笔為你收集整理的黑白棋出现pass 的条件 java_JAVA黑白棋之学习感悟的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 烤仔说 | Babe Babe Běib
- 下一篇: 两个地址之间的距离测量(使用高德API)