最近閑來無事，沒事玩都會和三兩好友一起切磋棋藝（五子棋），與菜雞對決，往往十幾招之內(nèi)必見分曉。但與強者切磋，往往不到數(shù)十個回合難以分出勝負。
偶然間突發(fā)奇想，五子棋棋盤為15行，15列。黑子與白子總計225枚，黑子較白子多出一枚，試想是否存在兩位高手直至將棋盤下滿，但仍未決出勝負的情況出現(xiàn)，鄙人苦思良久，查閱相關文章，特此總結。
由于鄙人才疏學淺，穩(wěn)重若有紕漏，還請大人們不吝賜教。

鄙人戰(zhàn)況最激烈的時候也不過30多步，沒想到下面是大佬啊！
這兩個人還真是旗鼓相當啊！
接下來言歸正傳！
博弈一向被認為是最富挑戰(zhàn)的智力游戲，有著難以言語的魅力。自從出現(xiàn)計算機后人們就開始有了與計算機下棋的想法。早在上世紀60年代就已經(jīng)出現(xiàn)若干博弈程序，并達到較高的水平，現(xiàn)已出現(xiàn)計算機博弈程序能夠與人類博弈大師抗衡的局面。博弈理論的研究不斷為人類科學提供新的課題，同時也對深層次的知識研究提出了嚴峻的挑戰(zhàn)。如何表示博弈問題的狀態(tài)，博弈過程和取勝的知識是目前人類仍在探討的問題。就拿五子棋游戲來講，棋面有15×15 = 225 個落子點，對方走完一步后，計算機差不多有200多種選擇每一種選擇對應搜索樹的一個節(jié)點，即棋局上的一個狀態(tài)。計算機走完一步后就應該考慮對方會走哪一步，此時同樣有200種選擇，因此有200×200種可能的選擇，對應搜索分支達到200×200個，如果博弈程序要考慮20回合，搜索樹就有40層，總結點大約有10^92 個。這個數(shù)字即使是計算機以每秒萬億次的速度計算，走一步棋也要一年。因此提高博弈問題的求解程序效率，因該做到以下兩點：
1，改進生產(chǎn)過程，使之只產(chǎn)生好的節(jié)點，即選擇比較好的節(jié)點去擴展。
2，改進測試過程，使最好的步驟能夠及時被確認，確認的代價不能太大。
目前博弈論比較常用的的搜索策略有極大極小搜索策略，深度優(yōu)先的alpha-beta剪枝搜索等。本文僅討論極大極小搜索策略和深度優(yōu)先的alpha-beta剪枝搜索策略。
一，極大極小值搜索
極大極小值搜索始終站在博弈一方的立場上給棋局估值，有利于這一方的棋局給一個較高的評價值，不利于這一方（有利于另一方）的給予一個較低的評價值，雙方優(yōu)劣不明顯的局面給予一個中間評價值（一般是0）本方行棋的時候選擇評價值極大的節(jié)點走步，另一方行棋時則選擇評價值極小的子節(jié)點走步。這就是一個極大極小的過程。基本思想如下：當輪到對手走棋時應考慮最壞的情況；當輪到自己走棋時應考慮最好的情況；當評價往回倒退時，相應于兩位棋手的對抗策略，在不同層次上交替使用前兩種方法往回傳遞倒退值。下面舉例詳細說明。
假如A,B兩位棋手行棋，B棋手落子后現(xiàn)在輪到A棋手落子，A棋手經(jīng)過分析發(fā)現(xiàn)目前有三個落子點P1，P2，P3為最優(yōu)落子點，于是A棋手分別對三個落子點進行分析以確定最好的一個落子點。開始對P1進行分析，當在P1落子點落子后棋手B會按照與棋手A相同的博弈思想選擇一個對己方最有利的落子點假設為Q1，當Q1落子后A棋手就會對棋局評分，假設為40分；按同樣的方法分析P2與P3點，假設與P2，P3相對應的Q2，Q3落子后棋局的評分分別為50分，30分。經(jīng)過以上分析棋手A可以得出結論，P1，P2，P3三個落子點中P2為最優(yōu)落子點，因為在P2落子點落子后即使對手在對我方最不利的落子點落子我方的評分是50分，而其他兩種落子點卻是30和40（這里棋局對A棋手的有利程度與分數(shù)成正比）.采用極大極小搜索策略的博弈程序使計算機與棋手A有相同的分析過程。
二，深度優(yōu)先的alpha-beta搜索
在極大極小搜索的過程中存在著一定的數(shù)據(jù)冗余，提出這些冗余數(shù)據(jù)是減小搜索空間的必然做法，所采用的方法就是1975年Monroe Newborn 提出的alpha-bete剪枝。
把alpha-bete剪枝應用到極大極小搜索中就形成了alpha-bete搜索。
若任一極小層節(jié)點的bete值小于或等于他任一先輩節(jié)點的alpha值，則可終止該極小層中該MIN節(jié)點一下的搜索過程，這個MIN節(jié)點最終的倒退值就確定為bete值。這一過程就稱為alpha剪枝。
若任一極大層節(jié)點的alpha值大于或等于他任一先輩極小層節(jié)點的bete值，則可終止該MAX節(jié)點以下的搜索過程，這個MAX節(jié)點的最終倒退值就確定為alpha值。這一過程就稱為bete剪枝。
為了使整個過程更加清晰依然以上面的例子說明alpha-bete搜索過程。
假如A棋手在P2落子點落子后B棋手經(jīng)過分析得到三個對己方最有利的節(jié)點，分別是Q2a，Q2b，Q2c。因此有以下三種情況：A棋手選擇P2節(jié)點落子，B棋手選擇Q2a節(jié)點落子；A棋手選擇P2節(jié)點落子，B棋手選擇Q2b節(jié)點落子；A棋手選擇P2節(jié)點落子，B棋手選擇Q2c節(jié)點落子。根據(jù)這三種情況A棋手分別對棋局進行評分，如果第一種情況下棋局的得分為35分，那么A棋手就可以不必分析后兩種情況的棋局得分而直接得出p1節(jié)點比P2節(jié)點好的結論。這樣一來A棋手就可以迅速從三個最好落子點中排除P2落子點，對于計算機來說就節(jié)省了CPU時間。因為A棋手把B棋手想像的足夠聰明，B棋手會選擇Q2a，Q2b，Q2c三個落子點中對A棋手最不利的一個節(jié)點，所以只要以上三種情況中有一種情況的棋局得分比P1落子點小那么P1落子點就比P2落子點優(yōu)秀。從以上分析中我們可以看到alpha-bete搜索對節(jié)點的排列非常敏感對于同一層上的節(jié)點如果排列合適剪枝效率就很高，可以使實際搜索的博弈樹達到最小樹。
這里給出alpha-bete搜索的java代碼實現(xiàn)。
此處文章出自：
原文鏈接：https://blog.csdn.net/john0101/article/details/4286291

極大值搜索過程：protected int findMax(int alpha,int beta,int step){int mx = alpha;//極大最小值；if(step == 0){ //達到特定深度返回；return evaluate();}//循環(huán)調(diào)用findmin，找出當前節(jié)點對應的最大值；for(int i = 3;i<11;i++){for(int j = 3;j<11;j++){//搜索范圍為3×11；if(chess[i][j] ==0){if(getType(i,j,startbw)==1)//getTepy()得到當前棋局的棋型；return 100*getMark(1);//getMark()返回特定棋型的得分；chess[i][j] = startbw;int t = findMin(mx,beta,step-1);//調(diào)用極小值搜索；chess[i][j] = 0;if(t > mx)mx = t;//搜索極大值；if(mx >= beta)//beta剪枝；return mx;//退出搜索；}}}return mx;}極小值搜索過程：protected int findMin(int alpha,int beta,int step){int mn = beta;//極小最大值；if(step == 0){return evaluate();}int[][] rt = getBests(3-startbw);//返回部分最優(yōu)解；for(int i = 0;i<rt.length;i++){int ii = rt[i][0];int jj =rt[i][1];if(getType(ii,jj,3-startbw)==1)return -100*getMark(1);chess[ii][jj]= 3-startbw;int t = findMax(alpha,mn,step-1);chess[ii][jj]=0;if(t < mn)mn=t;if(mn <= alpha)//alpha 剪枝；return mn;}return mn;}

可以這樣理解，若兩名玩家均足夠聰明，那么先手具有的優(yōu)勢足夠他獲勝的了！
某乎上有篇文章：五子棋中，先手下棋到底有多大的優(yōu)勢？
https://www.zhihu.com/question/267273167
不錯不錯，沒看太懂！嘻嘻嘻！
如有錯誤紕漏，還望指出，小白一枚，繼續(xù)學習！
喜歡就點個贊吧！

總結

以上是生活随笔為你收集整理的茶余饭后-五子棋棋盘究竟够大么？的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。