棋類游戲?qū)?zhàn)的實(shí)現(xiàn)
- 六洲棋
- 五子棋
- AI對(duì)戰(zhàn)
- 藍(lán)牙對(duì)戰(zhàn)
- 在線對(duì)戰(zhàn)
六洲棋
六洲棋，又稱：泥棋芯急、插方勺届、來馬、五福棋娶耍，中國(guó)民間傳統(tǒng)棋類體育形式免姿。源于民間，簡(jiǎn)便榕酒、通俗胚膊、易學(xué)，在民間廣為流行想鹰，深受社會(huì)底層大眾的喜愛紊婉。龍其在淮河流域的安徽省、河南省杖挣、江蘇省肩榕、以及湖北省、山東省非常普及惩妇，并流傳到中國(guó)各地株汉，包括港、澳歌殃、臺(tái)地區(qū)乔妈。起源于勞動(dòng)人民生活，根植于民間大眾之中氓皱，它簡(jiǎn)捷路召、明快，趣味性波材、競(jìng)技性強(qiáng)股淡，是一項(xiàng)長(zhǎng)期流行于民間，富有傳統(tǒng)文化色彩的競(jìng)技項(xiàng)目廷区。對(duì)于啟迪智慧唯灵，休閑娛樂，增進(jìn)交流非常有益隙轻。列安徽省第二批省級(jí)非物質(zhì)文化遺產(chǎn)埠帕。
6*6縱橫線組成垢揩，共三十六個(gè)棋點(diǎn)。每方十八枚棋子敛瓷，以兩色區(qū)分?jǐn)澄摇?/p>
規(guī)則
對(duì)弈過程分三階段叁巨。（鳳陽(yáng)下法）放子：對(duì)弈雙方依次將己子放入空棋點(diǎn)，將手上的棋子放完才開始走子呐籽。逼子：若無棋子被吃锋勺，使得棋子放滿棋盤。則兩人各選對(duì)方一枚敵子移出游戲狡蝶。走子：由后手方開始輪流移動(dòng)己棋宙刘，沿線直橫線一格。吃子：無論是下子或走子階段牢酵，只要己方棋子排成以下排列稱為成城，就要吃掉一定數(shù)量的敵子衙猪，但不可吃掉已成城子的敵棋馍乙。在放子階段，被吃的子先作記號(hào)垫释，等走子階段開始才一齊提取丝格。
成六：六枚棋子以縱、橫和斜3個(gè)方向連成直線(除了四條邊的直線)棵譬。吃掉敵方三子显蝌。
斜五：連子的2頭都靠棋盤邊緣，吃掉敵方兩子订咸。
斜四：連子的2頭都靠棋盤邊緣曼尊，吃掉敵方一子。
斜三：連子的2頭都靠棋盤邊緣脏嚷，吃掉敵方一子骆撇。
成方：四枚棋子組成一個(gè)緊鄰相連的小正方形，吃掉敵方一子父叙。
使對(duì)方只剩下三枚以下則獲勝神郊。因?yàn)槭敲耖g文化，各地稍有差異趾唱。
棋型的算法實(shí)現(xiàn)
//是否形成斜子棋（三子棋涌乳，四子棋，五子棋甜癞，六子棋）
static func isXiZiChess(_ point:SWSPoint,_ chessArray: [[FlagType]]) -> LianZhuState?{
let type = chessArray[point.x][point.y]
let pointLeft = SWSPoint()
let pointRight = SWSPoint()
let ponitTop = SWSPoint()
let pointBottom = SWSPoint()
// 東北方向
var i = 0
while point.x - i >= 0 && point.y + i <= 5 && chessArray[point.x - i][point.y + i] == type {
pointLeft.x = point.x - i
pointLeft.y = point.y + i
i += 1
}
i = 0
while point.x + i <= 5 && point.y - i >= 0 && chessArray[point.x + i][point.y - i] == type {
pointRight.x = point.x + i
pointRight.y = point.y - i
i += 1
}
//西北方向
i = 0
while point.x - i >= 0 && point.y - i >= 0 && chessArray[point.x - i][point.y - i] == type {
ponitTop.x = point.x - i
ponitTop.y = point.y - i
i += 1
}
i = 0
while point.x + i <= 5 && point.y + i <= 5 && chessArray[point.x + i][point.y + i] == type {
pointBottom.x = point.x + i
pointBottom.y = point.y + i
i += 1
}
print(pointRight.x,pointRight.y,pointLeft.x,pointLeft.y,ponitTop.x,ponitTop.y,pointBottom.x,pointBottom.y)
let arr = [3,2,1,0]
for index in arr {
func condition() -> Bool {
if pointRight.x == 2+index && pointRight.y == 0 && pointLeft.x == 0 && pointLeft.y == 2+index {
return true
}
if pointRight.x == 5 && pointRight.y == 3 - index && pointLeft.x == 3 - index && pointLeft.y == 5 {
return true
}
if ponitTop.x == 0 && ponitTop.y == 3-index && pointBottom.x == 2+index && pointBottom.y == 5 {
return true
}
if ponitTop.x == 3-index && ponitTop.y == 0 && pointBottom.x == 5 && pointBottom.y == 2+index {
return true
}
return false
}
if condition() {
switch index {
case 0:
return .threeChess
case 1:
return .fourChess
case 2:
return .fiveChess
case 3:
return .sixChess
default:()
}
}
}
return nil
}
//是否形成方格棋
static func isCheckChess(_ point:SWSPoint,_ chessArray: [[FlagType]]) ->LianZhuState? {
let type = chessArray[point.x][point.y]
//左上
if point.x - 1 >= 0 && point.y - 1 >= 0 && chessArray[point.x][point.y-1] == type &&
chessArray[point.x-1][point.y] == type && chessArray[point.x-1][point.y-1] == type {
return .checkChess
}
//左下
if point.x - 1 >= 0 && point.y + 1 <= 5 && chessArray[point.x][point.y+1] == type &&
chessArray[point.x-1][point.y] == type && chessArray[point.x-1][point.y+1] == type {
return .checkChess
}
//右上
if point.x + 1 <= 5 && point.y - 1 >= 0 && chessArray[point.x][point.y-1] == type &&
chessArray[point.x+1][point.y] == type && chessArray[point.x+1][point.y-1] == type {
return .checkChess
}
//右下
if point.x + 1 <= 5 && point.y + 1 <= 5 && chessArray[point.x][point.y+1] == type &&
chessArray[point.x+1][point.y] == type && chessArray[point.x+1][point.y+1] == type {
return .checkChess
}
return nil
}
小結(jié)
六洲棋夕晓，在我們老家被稱為泥棋，小時(shí)候經(jīng)常玩的一種棋带欢，偶有回憶运授，因此實(shí)現(xiàn)下這個(gè)游戲烤惊，望能找到個(gè)棋友沒事玩玩，這種棋吁朦，玩法多種柒室，很有趣。
五子棋
五子棋五子棋是比較流行的棋類游戲了逗宜，玩法簡(jiǎn)單雄右，基本上人人會(huì)玩，在此就不介紹游戲規(guī)則了纺讲。下面使用 swift實(shí)現(xiàn)五子棋這個(gè)游戲擂仍，主要實(shí)現(xiàn)AI算法，包括極大值極小值算法熬甚，深度搜索算法逢渔，估值函數(shù)，Alpha Beta 剪枝算法等等乡括。
//橫向五子連珠（除去四邊線的五子連珠）
static func isFiveChess(_ point:SWSPoint,_ chessArray: [[FlagType]]) -> Bool {
let type = chessArray[point.x][point.y]
let pointLeft = SWSPoint()
let pointRight = SWSPoint()
let pointTop = SWSPoint()
let pointBottom = SWSPoint()
let pointLeft45 = SWSPoint()
let pointRight45 = SWSPoint()
let pointTop135 = SWSPoint()
let pointBottom135 = SWSPoint()
//東西方向
var i = 0
while point.x - i >= 0 && chessArray[point.x - i][point.y] == type {
pointLeft.x = point.x - i
i += 1
}
i = 0
while point.x + i <= 14 && chessArray[point.x + i][point.y] == type {
pointRight.x = point.x + i
i += 1
}
if pointRight.x - pointLeft.x == 4 && (pointLeft.y != 15 || pointLeft.y != 0){
return true
}
//南北方向
i = 0
while point.y - i >= 0 && chessArray[point.x][point.y-i] == type {
pointTop.y = point.y - i
i += 1
}
i = 0
while point.y + i <= 14 && chessArray[point.x][point.y+i] == type {
pointBottom.y = point.y + i
i += 1
}
if pointBottom.y - pointTop.y == 4 && (pointTop.x != 15 || pointTop.x != 0) {
return true
}
// 東北方向
i = 0
while point.x - i >= 0 && point.y + i <= 14 && chessArray[point.x - i][point.y + i] == type {
pointLeft45.x = point.x - i
pointLeft45.y = point.y + i
i += 1
}
i = 0
while point.x + i <= 14 && point.y - i >= 0 && chessArray[point.x + i][point.y - i] == type {
pointRight45.x = point.x + i
pointRight45.y = point.y - i
i += 1
}
if pointLeft45.y - pointRight45.y == 4{
return true
}
//西北方向
i = 0
while point.x - i >= 0 && point.y - i >= 0 && chessArray[point.x - i][point.y - i] == type {
pointTop135.x = point.x - i
pointTop135.y = point.y - i
i += 1
}
i = 0
while point.x + i <= 14 && point.y + i <= 14 && chessArray[point.x + i][point.y + i] == type {
pointBottom135.x = point.x + i
pointBottom135.y = point.y + i
i += 1
}
if pointBottom135.y - pointTop135.y == 4{
return true
}
return false
}
在 demo中實(shí)現(xiàn)了五子棋的AI肃廓、同機(jī)、藍(lán)牙诲泌、在線對(duì)戰(zhàn)盲赊，下面重點(diǎn)介紹AI對(duì)戰(zhàn)。
五子棋的AI算法實(shí)現(xiàn)
2017年互聯(lián)網(wǎng)最火的技術(shù)毫無疑問就是AI了敷扫，在此嘗試寫了個(gè)算法來和人腦來pk哀蘑。五子棋屬于零和游戲：一方勝利代表另一方失敗，而零和游戲的代表算法就是極大值極小值搜索算法葵第。
極大值極小值搜索算法
A绘迁、B二人對(duì)弈，A先走卒密，A始終選擇使局面對(duì)自己最有利的位置脊髓，然后B根據(jù)A的選擇，在剩下的位置中選擇對(duì)A最不利的位置栅受，以此類推下去直到到達(dá)我們定義的最大搜索深度将硝。所以每一層輪流從子節(jié)點(diǎn)選擇最大值－最小值－最大值－最小值...
我們?nèi)绾沃滥膫€(gè)位置最有利和最不利呢？在此我們引入一套評(píng)估函數(shù)屏镊，來對(duì)棋盤上每個(gè)位置進(jìn)行分?jǐn)?shù)評(píng)估
//活一依疼、活二、活三而芥、活四律罢、連五、眠一，眠二误辑、眠三沧踏、眠四
enum FiveChessType:Int {
case liveOne = 0
case liveTwo
case liveThree
case liveFour
case liveFive
case sleepOne
case sleepTwo
case sleepThree
case sleepFour
case unknown
var score:Int {
switch self {
case .unknown:
return un_known
case .sleepOne:
return sleep_One
case .liveOne,.sleepTwo:
return live_One
case .liveTwo,.sleepThree:
return live_Two
case .liveThree:
return live_Three
case .sleepFour:
return sleep_Four
case .liveFour:
return live_Four
case .liveFive:
return live_Five
}
}
}
let live_Five = 1000000
let live_Four = 100000
let sleep_Four = 10000
let live_Three = 1000
let live_Two = 100
let sleep_Three = 100
let live_One = 10
let sleep_Two = 10
let sleep_One = 1
let un_known = 0
在使用極大值極小值進(jìn)行深度搜索時(shí)，遍歷節(jié)點(diǎn)是指數(shù)增長(zhǎng)的巾钉，如果不進(jìn)行算法優(yōu)化翘狱，將會(huì)導(dǎo)致電腦計(jì)算時(shí)間過長(zhǎng)，影響下棋體驗(yàn)砰苍，所以這里引入 Alpha Beta 剪枝原理潦匈。
Alpha Beta 剪枝原理
AlphaBeta剪枝算法是一個(gè)搜索算法旨在減少在其搜索樹中，被極大極小算法評(píng)估的節(jié)點(diǎn)數(shù)赚导。
Alpha-Beta只能用遞歸來實(shí)現(xiàn)茬缩。這個(gè)思想是在搜索中傳遞兩個(gè)值，第一個(gè)值是Alpha吼旧，即搜索到的最好值凰锡，任何比它更小的值就沒用了，因?yàn)椴呗跃褪侵繟lpha的值圈暗，任何小于或等于Alpha的值都不會(huì)有所提高寡夹。
第二個(gè)值是Beta，即對(duì)于對(duì)手來說最壞的值厂置。這是對(duì)手所能承受的最壞的結(jié)果，因?yàn)槲覀冎涝趯?duì)手看來魂角，他總是會(huì)找到一個(gè)對(duì)策不比Beta更壞的昵济。如果搜索過程中返回Beta或比Beta更好的值，那就夠好的了野揪，走棋的一方就沒有機(jī)會(huì)使用這種策略了访忿。
在搜索著法時(shí)，每個(gè)搜索過的著法都返回跟Alpha和Beta有關(guān)的值斯稳，它們之間的關(guān)系非常重要海铆，或許意味著搜索可以停止并返回。
如果某個(gè)著法的結(jié)果小于或等于Alpha挣惰，那么它就是很差的著法卧斟，因此可以拋棄。因?yàn)槲仪懊嬲f過憎茂，在這個(gè)策略中珍语，局面對(duì)走棋的一方來說是以Alpha為評(píng)價(jià)的。
如果某個(gè)著法的結(jié)果大于或等于Beta竖幔，那么整個(gè)節(jié)點(diǎn)就作廢了板乙，因?yàn)閷?duì)手不希望走到這個(gè)局面，而它有別的著法可以避免到達(dá)這個(gè)局面拳氢。因此如果我們找到的評(píng)價(jià)大于或等于Beta募逞，就證明了這個(gè)結(jié)點(diǎn)是不會(huì)發(fā)生的蛋铆，因此剩下的合理著法沒有必要再搜索。
如果某個(gè)著法的結(jié)果大于Alpha但小于Beta放接，那么這個(gè)著法就是走棋一方可以考慮走的刺啦，除非以后有所變化。因此Alpha會(huì)不斷增加以反映新的情況透乾。有時(shí)候可能一個(gè)合理著法也不超過Alpha洪燥，這在實(shí)戰(zhàn)中是經(jīng)常發(fā)生的，此時(shí)這種局面是不予考慮的乳乌，因此為了避免這樣的局面捧韵，我們必須在博弈樹的上一個(gè)層局面選擇另外一個(gè)著法。鏈接
c代碼實(shí)現(xiàn)原理
int AlphaBeta(int depth, int alpha, int beta)
{
if (depth == 0)
{
return Evaluate();
}
GenerateLegalMoves();
while (MovesLeft())
{
MakeNextMove();
val = -AlphaBeta(depth - 1, -beta, -alpha);
UnmakeMove();
if (val >= beta)
{
return beta;
}
if (val > alpha)
{
alpha = val;
}
}
return alpha;
}
實(shí)際在代碼中的運(yùn)用汉操，代碼比較復(fù)雜請(qǐng)結(jié)合項(xiàng)目理解再来。項(xiàng)目地址
static func getAIPoint(chessArray:inout[[FlagType]],role:FlagType,AIScore:inout [[Int]],humanScore:inout [[Int]],deep:Int) ->(Int,Int,Int)? {
let maxScore = 10*live_Five
let minScore = -1*maxScore
let checkmateDeep = self.checkmateDeep
var total=0, //總節(jié)點(diǎn)數(shù)
steps=0, //總步數(shù)
count = 0, //每次思考的節(jié)點(diǎn)數(shù)
ABcut = 0 //AB剪枝次數(shù)
func humMax(deep:Int)->(Int,Int,Int)? {
let points = self.getFiveChessType(chessArray: chessArray, AIScore: &AIScore, humanScore: &humanScore)
var bestPoint:[(Int,Int)] = []
var best = minScore
count = 0
ABcut = 0
for i in 0..<points.count {
let p = points[i]
chessArray[p.x][p.y] = role
self.updateOneEffectScore(chessArray: chessArray, point: (p.x,p.y), AIScore: &AIScore, humanScore: &humanScore)
var score = -aiMaxS(deep: deep-1, alpha: -maxScore, beta: -best, role: self.reverseRole(role: role))
if p.x < 3 || p.x > 11 || p.y < 3 || p.y > 11 {
score = score/2
}
if TJFTool.equal(a: Float(score), b: Float(best)){
bestPoint.append((p.x,p.y))
}
if TJFTool.greatThan(a: Float(score), b: Float(best)){
best = score
bestPoint.removeAll()
bestPoint.append((p.x,p.y))
}
chessArray[p.x][p.y] = .freeChess
self.updateOneEffectScore(chessArray: chessArray, point: (p.x,p.y), AIScore: &AIScore, humanScore: &humanScore)
}
steps += 1
total += count
if bestPoint.count > 0 {
let num = arc4random()%UInt32(bestPoint.count)
return (bestPoint[Int(num)].0,bestPoint[Int(num)].1,best)
}
return nil
}
func aiMaxS(deep:Int,alpha:Int,beta:Int,role:FlagType) -> Int{
var score = 0
var aiMax = 0
var humMax = 0
var best = minScore
for i in 0..<15{
for j in 0..<15{
if chessArray[i][j] == .freeChess{
aiMax = max(AIScore[i][j], aiMax)
humMax = max(humanScore[i][j], humMax)
}
}
}
score = (role == .blackChess ? 1 : -1) * (aiMax-humMax)
count += 1
if deep <= 0 || TJFTool.greatOrEqualThan(a: Float(score), b: Float(live_Five)){
return score
}
let points = self.getFiveChessType(chessArray: chessArray, AIScore: &AIScore, humanScore: &humanScore)
for i in 0..<points.count{
let p = points[i]
chessArray[p.x][p.y] = role
self.updateOneEffectScore(chessArray: chessArray, point: (p.x,p.y), AIScore: &AIScore, humanScore: &humanScore)
let some = -aiMaxS(deep: deep-1, alpha: -beta, beta: -1 * ( best > alpha ? best : alpha), role: self.reverseRole(role: role)) * deepDecrease
chessArray[p.x][p.y] = .freeChess
self.updateOneEffectScore(chessArray: chessArray, point: (p.x,p.y), AIScore: &AIScore, humanScore: &humanScore)
if TJFTool.greatThan(a: Float(some), b: Float(best)) {
best = some
}
//在這里進(jìn)行ab 剪枝
if TJFTool.greatOrEqualThan(a: Float(some), b: Float(beta)){
ABcut += 1
return some
}
}
if (deep == 2 || deep == 3 || deep == 4) && TJFTool.littleThan(a: Float(best), b: Float(sleep_Four)) && TJFTool.greatThan(a: Float(best), b: -(Float)(sleep_Four)){
if let result = self.checkmateDeeping(chessArray: &chessArray, role: role, AIScore: &AIScore, humanScore: &humanScore, deep: checkmateDeep) {
return Int(Double(result[0].2) * pow(0.8, Double(result.count)) * (role == .blackChess ? 1:-1))
}
}
return best
}
var i = 2
var result:(Int,Int,Int)?
while i <= deep {
if let test = humMax(deep: i) {
result = test
if TJFTool.greatOrEqualThan(a: Float(test.2), b: Float(live_Four)) {
return test
}
}
i += 2
}
if result == nil {
var maxAiScore = 0
for i in 0..<15{
for j in 0..<15 {
if chessArray[i][j] == .freeChess && maxAiScore < AIScore[i][j] {
maxAiScore = AIScore[i][j]
result = (i,j,maxAiScore)
}
}
}
}
return result
}
經(jīng)過Alpha Beta剪枝后，優(yōu)化效果應(yīng)該達(dá)到 1/2 次方磷瘤，也就是說原來需要遍歷XY個(gè)節(jié)點(diǎn)芒篷，現(xiàn)在只需要遍歷X(Y/2)個(gè)節(jié)點(diǎn)，相比之前已經(jīng)有了極大的提升采缚。
不過即使經(jīng)過了Alpha Beta 剪枝针炉，思考層數(shù)也只能達(dá)到四層，也就是一個(gè)不怎么會(huì)玩五子棋的普通玩家的水平扳抽。而且每增加一層篡帕，所需要的時(shí)間或者說計(jì)算的節(jié)點(diǎn)數(shù)量是指數(shù)級(jí)增加的。所以目前的代碼想計(jì)算到第六層是很困難的贸呢。
我們的時(shí)間復(fù)雜度是一個(gè)指數(shù)函數(shù) X^Y镰烧，其中底數(shù)X是每一層節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)，Y 是思考的層數(shù)楞陷。我們的剪枝算法能剪掉很多不用的分支怔鳖，相當(dāng)于減少了 Y，那么下一步我們需要減少 X固蛾，如果能把 X 減少一半结执，那么四層平均思考的時(shí)間能降低到 0.5^4 = 0.06 倍，也就是能從10秒降低到1秒以內(nèi)艾凯。
如何減少X呢昌犹？我們知道五子棋中，成五览芳、活四斜姥、雙三、雙眠四、眠四活三是必殺棋铸敏，于是我們遇到后就不用再往下搜索了缚忧。代碼如下：
static func getFiveChessType(chessArray:[[FlagType]],AIScore:inout [[Int]],humanScore:inout [[Int]]) ->[(x:Int,y:Int)]{
var twos:[(Int,Int)] = []
var threes:[(Int,Int)] = []
var doubleThrees:[(Int,Int)] = []
var sleepFours:[(Int,Int)] = []
var fours:[(Int,Int)] = []
var fives:[(Int,Int)] = []
var oters:[(Int,Int)] = []
for i in 0..<15{
for j in 0..<15{
if chessArray[i][j] == .freeChess && self.effectivePoint(chessArray: chessArray, point: (x: i, y: j)) {
let aiScore = AIScore[i][j]
let humScore = humanScore[i][j]
if aiScore>=live_Five {
return[(i,j)]
}else if humScore >= live_Five {
fives.append((i,j))
}else if aiScore >= live_Four {
fours.insert((i,j), at: 0)
}else if humScore >= live_Four {
fours.append((i,j))
}else if aiScore >= sleep_Four{
sleepFours.insert((i,j), at: 0)
}else if humScore >= sleep_Four{
sleepFours.append((i,j))
}else if aiScore >= 2*live_Three{
doubleThrees.insert((i,j), at: 0)
}else if humScore >= 2*live_Three{
doubleThrees.append((i,j))
}else if aiScore >= live_Three {
threes.insert((i,j), at: 0)
}else if humScore >= live_Three {
threes.append((i, j))
}else if aiScore >= live_Two{
twos.insert((i,j), at: 0)
}else if humScore >= live_Two{
twos.append((i,j))
}else {
oters.append((i,j))
}
}
}
}
if fives.count > 0 {
return [fives[0]]
}
if fours.count > 0 {
return fours
}
if sleepFours.count > 0{
return [sleepFours[0]]
}
if doubleThrees.count > 0{
return doubleThrees + threes
}
let result = threes + twos + oters
var realy:[(Int,Int)] = []
if result.count > limitNum {
realy += result.prefix(limitNum)
return realy
}
return result
}
五子棋是一種進(jìn)攻優(yōu)勢(shì)的棋，依靠連續(xù)不斷地活三或者沖四進(jìn)攻杈笔，最后很容易會(huì)形成必殺棋闪水，所以在進(jìn)行深度搜索時(shí)，我們另開一種連續(xù)進(jìn)攻的搜索蒙具，如果球榆，電腦可以依靠連續(xù)進(jìn)攻獲得勝利，我們可以直接走這條路勁禁筏。這條路勁持钉，其實(shí)也是極大值極小值搜索算法的一種，只不過是只考慮活三沖四這兩種棋型篱昔，指數(shù)的底數(shù)較小每强，搜索的節(jié)點(diǎn)比較少，因此是效率很高的算法州刽。代碼如下：
//有限考慮ai成五
static func findMaxScore(chessArray:[[FlagType]],role:FlagType,aiScore:[[Int]],humanScore:[[Int]],score:Int)->[(Int,Int,Int)]{
var result:[(Int,Int,Int)] = []
for i in 0..<15{
for j in 0..<15{
if chessArray[i][j] == .freeChess {
if self.effectivePoint(chessArray: chessArray, point: (i,j),chessCount: 1) {
let score1 = role == .blackChess ? aiScore[i][j] : humanScore[i][j]
if score1 >= live_Five {
return [(i,j,score1)]
}
if score1 >= score {
result.append((i,j,score1))
}
}
}
}
}
return result.sorted { (a, b) -> Bool in
return b.2 > a.2
}
}
//考慮活三空执，沖四
static func findEnemyMaxScore(chessArray:[[FlagType]],role:FlagType,aiScore:[[Int]],humanScore:[[Int]],score:Int)->[(Int,Int,Int)]{
var result:[(Int,Int,Int)] = []
var fours:[(Int,Int,Int)] = []
var fives:[(Int,Int,Int)] = []
for i in 0..<15{
for j in 0..<15{
if chessArray[i][j] == .freeChess {
if self.effectivePoint(chessArray: chessArray, point: (i,j),chessCount: 1) {
let score1 = role == .blackChess ? aiScore[i][j] : humanScore[i][j]
let score2 = role == .blackChess ? humanScore[i][j] : aiScore[i][j]
if score1 >= live_Five {
return [(i,j,-score1)]
}
if score1 >= live_Four {
fours.insert((i,j,-score1), at: 0)
continue
}
if score2 >= live_Five {
fives.append((i,j,score2))
continue
}
if score2 >= live_Four{
fours.append((i,j,score2))
continue
}
if score1 > score || score2 > score {
result.append((i,j,score1))
}
}
}
}
}
if fives.count > 0 {
return [fives[0]]
}
if fours.count > 0 {
return [fours[0]]
}
return result.sorted { (a, b) -> Bool in
return abs(b.2) > abs(a.2)
}
}
小結(jié)
本次編寫的AI還是比較強(qiáng)的，我勝利的機(jī)會(huì)很少穗椅，但還是存在贏的時(shí)候辨绊，因此AI算法還存在漏洞，主要表現(xiàn)在評(píng)分標(biāo)準(zhǔn)不準(zhǔn)確和搜索深度不夠問題上匹表，如何優(yōu)化評(píng)分標(biāo)準(zhǔn)和搜索算法门坷，是實(shí)現(xiàn)AI無敵的關(guān)鍵工作。
另外桑孩，在增加搜索深度的同時(shí)，遍歷的節(jié)點(diǎn)指數(shù)增長(zhǎng)框冀，計(jì)算時(shí)間增長(zhǎng)流椒，可以結(jié)合哈希算法，保存每次的棋盤評(píng)分明也，一定程度上提高計(jì)算時(shí)間宣虾，這也只是治標(biāo)不治本的做法。
藍(lán)牙對(duì)戰(zhàn)
MultipeerConnectivity框架的使用
MultipeerConnectivity通過WiFi温数、P2P WiFi以及藍(lán)牙個(gè)人局域網(wǎng)進(jìn)行通信的框架绣硝，從而無需聯(lián)網(wǎng)手機(jī)間就能傳遞消息。其原理是通過廣播作為服務(wù)器去發(fā)現(xiàn)附近的節(jié)點(diǎn)撑刺，每個(gè)節(jié)點(diǎn)都以設(shè)備名稱為標(biāo)識(shí)鹉胖。
myPeer = MCPeerID.init(displayName: UIDevice.current.name)
session = MCSession.init(peer: myPeer!, securityIdentity: nil, encryptionPreference: .none)
session?.delegate = self
MCSession的幾個(gè)代理方法必須實(shí)現(xiàn)，否則無法建立連接
//監(jiān)聽連接狀態(tài)
func session(_ session: MCSession, peer peerID: MCPeerID, didChange state: MCSessionState) {
switch state {
case .notConnected:
print("未連接")
case .connecting:
print("正在連接中")
case .connected:
print("連接成功")
}
}
//發(fā)送Dada數(shù)據(jù)
func sendData(_ messageVo: GPBMessage, successBlock:(()->())?,errorBlock:((NSError)->())?) {
guard let session = session else {
return
}
guard let data = NSDataTool.shareInstance().returnData(messageVo, messageId: 0) else {return}
do {
try session.send(data as Data , toPeers: session.connectedPeers, with: .reliable)
}catch let error as NSError {
errorBlock?(error)
return
}
successBlock?()
}
//接收到的Data數(shù)據(jù)
func session(_ session: MCSession, didReceive data: Data, fromPeer peerID: MCPeerID) {
// 解析出過來的data數(shù)據(jù)包
NSDataTool.shareInstance().startParse(data) { (gpbMessage) in
self.getMessageBlock?(gpbMessage)
}
}
//接收到的流數(shù)據(jù)
func session(_ session: MCSession, didReceive stream: InputStream, withName streamName: String, fromPeer peerID: MCPeerID) {
print("streamName")
}
//接收到的文件類型數(shù)據(jù)
func session(_ session: MCSession, didStartReceivingResourceWithName resourceName: String, fromPeer peerID: MCPeerID, with progress: Progress) {
print("resourceName")
}
//接收到的文件類型數(shù)據(jù)，可將文件換路勁
func session(_ session: MCSession, didFinishReceivingResourceWithName resourceName: String, fromPeer peerID: MCPeerID, at localURL: URL, withError error: Error?) {
}
我們通過MCAdvertiserAssistant（廣播）開啟搜索服務(wù)
advertiser = MCAdvertiserAssistant.init(serviceType: serviceStr, discoveryInfo: nil, session: session!)
//發(fā)出廣播
advertiser?.start()
advertiser?.delegate = self
MCBrowserViewControllerDelegate代理方法
/// 發(fā)出廣播請(qǐng)求
func advertiserAssistantWillPresentInvitation(_ advertiserAssistant: MCAdvertiserAssistant) {
print("advertiserAssistantWillPresentInvitation")
}
/// 結(jié)束廣播請(qǐng)求
func advertiserAssistantDidDismissInvitation(_ advertiserAssistant: MCAdvertiserAssistant) {
print("advertiserAssistantDidDismissInvitation")
}
設(shè)置藍(lán)牙連接頁(yè)面甫菠，顯示效果如圖所示：
func setupBrowserVC() {
guard let session = session else {
return
}
browser = MCBrowserViewController.init(serviceType: serviceStr, session: session)
browser?.delegate = self
}
實(shí)現(xiàn)MCBrowserViewControllerDelegate代理方法
func browserViewControllerDidFinish(_ browserViewController: MCBrowserViewController) {
print("藍(lán)牙連接完成")
browser?.dismiss(animated: true, completion: { [weak self] in
self?.browserBlock?()
})
}
func browserViewControllerWasCancelled(_ browserViewController: MCBrowserViewController) {
print("取消藍(lán)牙連接")
browser?.dismiss(animated: true, completion: nil)
}
小結(jié)
使用藍(lán)牙技術(shù)進(jìn)行傳輸數(shù)據(jù)挠铲，盡管不需要連接網(wǎng)絡(luò)服務(wù)，但是真實(shí)因?yàn)檫@樣存在著許多安全隱患寂诱，為此我們引入Google Protobuf框架進(jìn)行數(shù)據(jù)傳輸拂苹。下章會(huì)對(duì)該技術(shù)的運(yùn)用進(jìn)行詳解。
protobuf在iOS中的運(yùn)用
protocolbuffer(以下簡(jiǎn)稱protobuf)是google 的一種數(shù)據(jù)交換的格式痰洒，它獨(dú)立于語(yǔ)言瓢棒，獨(dú)立于平臺(tái)。google 提供了多種語(yǔ)言的實(shí)現(xiàn)：java丘喻、c#脯宿、c++、oc仓犬、go 和 python嗅绰，每一種實(shí)現(xiàn)都包含了相應(yīng)語(yǔ)言的編譯器以及庫(kù)文件。由于它是一種二進(jìn)制的格式搀继，比使用 xml和json 進(jìn)行數(shù)據(jù)交換快許多窘面。可以把它用于分布式應(yīng)用之間的數(shù)據(jù)通信或者異構(gòu)環(huán)境下的數(shù)據(jù)交換叽躯。作為一種效率和兼容性都很優(yōu)秀的二進(jìn)制數(shù)據(jù)傳輸格式财边，可以用于諸如網(wǎng)絡(luò)傳輸、配置文件点骑、數(shù)據(jù)存儲(chǔ)等諸多領(lǐng)域酣难。
我們重點(diǎn)介紹protobuf在iOS中的運(yùn)用，官方文檔
protobuf使用步驟
- 定義.proto文件
- 配置protobuf環(huán)境
- 映射相應(yīng)語(yǔ)言的文件
- 導(dǎo)入第三方庫(kù)protobuf
.proto文件的定義
該文件主要是用來作為你傳遞數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)的文檔黑滴，然后通過終端命令生成我們相應(yīng)語(yǔ)言的model類憨募，導(dǎo)入項(xiàng)目中使用。
.proto的定義語(yǔ)法有官方文檔自己學(xué)習(xí)袁辈，在此不過多介紹菜谣，在此一定要注意的是，一定要使用proto3來定義晚缩，proto2已經(jīng)在很多第三方庫(kù)中被淘汰使用(以前用的都是proto2尾膊，Proto3出來并不了解，報(bào)錯(cuò)信息一度讓我懷疑人生)荞彼。定義文件類似下圖所示：
配置protobuf環(huán)境
使用homebrew進(jìn)行配置（如果沒安裝冈敛，自己谷歌安裝）
- brew install automake
- brew install libtool
- brew install protobuf
- ln -s /usr/local/Cellar/protobuf/(上步中安裝protobuf的版本號(hào))/bin/protoc /usr/local/bin
- git clone https://github.com/alexeyxo/protobuf-objc.git（oc版本）或者
git clone https://github.com/alexeyxo/protobuf-swift.git（swift版本） - cd protobuf-objc
- ./autogen.sh
- ./configure CXXFLAGS=-I/usr/local/include LDFLAGS=-L/usr/local/lib
- make install
映射相應(yīng)語(yǔ)言的文件
- cd 到.proto文件的路勁中
- protoc --plugin=/usr/local/bin/protoc-gen-objc test.proto --objc_out=.
此為生成oc類的命令，其中test.proto是自己生成的proto文件的名字鸣皂。相應(yīng)swift類的命令為：
protoc --plugin=/usr/local/bin/protoc-gen-swift test.proto --swift_out=. - 將生成的文件導(dǎo)入項(xiàng)目中
導(dǎo)入第三方庫(kù)protobuf
這里建議使用pod管理：pod 'Protobuf'
Protobuf庫(kù)的使用
一般就是將Data類型的數(shù)據(jù)映射成model和將model生成data類型數(shù)據(jù)兩個(gè)方法抓谴，他們分別是
使用GPBMessage中的倆個(gè)方法
+ (instancetype)parseFromData:(NSData *)data error:(NSError **)errorPtr {
return [self parseFromData:data extensionRegistry:nil error:errorPtr];
}
- (nullable NSData *)data;
小結(jié)
使用protobuf傳輸還是存在安全問題和數(shù)據(jù)比較大時(shí)的耗能問題暮蹂，于是我們想到了，在直播領(lǐng)域應(yīng)用很普遍的RTMP協(xié)議齐邦。下章詳細(xì)講解椎侠，使用分包思想拆解數(shù)據(jù)包進(jìn)行數(shù)據(jù)傳輸。
RTMP協(xié)議藍(lán)牙傳輸數(shù)據(jù)
RTMP傳統(tǒng)定義
rtmp協(xié)議中基本的數(shù)據(jù)單元被稱為消息（message）結(jié)構(gòu)一般為：
- 時(shí)戳：4 byte措拇，單位毫秒我纪。超過最大值后會(huì)翻轉(zhuǎn)。
- 長(zhǎng)度：消息負(fù)載的長(zhǎng)度丐吓。
- 類型ID：Type Id 一部分ID范圍用于rtmp的控制信令浅悉。還有一部分可以供上層使用，rtmp只是透 傳券犁。這樣可以方便的在rtmp上進(jìn)行擴(kuò)展术健。
- 消息流ID：Message Stream ID，用于區(qū)分不同流的消息粘衬。
消息在網(wǎng)絡(luò)中傳輸時(shí)荞估，會(huì)被分割成很多小的消息塊，進(jìn)行傳輸稚新，增加傳輸?shù)男士彼牛@些消息塊是由消息頭+消息體組成，消息頭就是制定的標(biāo)識(shí)消息的協(xié)議褂删，消息體就是所傳輸?shù)南?nèi)容飞醉。
RTMP在藍(lán)牙中的定義
手機(jī)藍(lán)牙傳輸數(shù)據(jù)，無法保證雙方手機(jī)時(shí)間同步屯阀，因此刨除時(shí)間戳定義改為固定字符串缅帘，因此messageHeader定義為：
struct message_header
{
uint32_t magic;//magic number, 0x98765432
uint32_t total;//包長(zhǎng)度，從這一字段頭算起
uint32_t msgid;//消息ID
uint32_t seqnum;//客戶端使用,自增量
uint32_t version;//協(xié)議版本难衰，目前為1
};
將需要傳輸?shù)臄?shù)據(jù)添加message_header
//GPBMEssage為protobuf庫(kù)里的類,請(qǐng)參考上篇文章
-(NSMutableData*)returnData:(GPBMessage*)req messageId:(int)messageId {
NSString *header=[NSString stringWithFormat:@"98765432%08lx%08x%08lx00000001",(unsigned long)req.data.length+20,messageId,(unsigned long)++self.header_count];
Byte bytes[40];
int j=0;
for(int i=0;i*2+1<header.length;i++)
{
int int_ch; /// 兩位16進(jìn)制數(shù)轉(zhuǎn)化后的10進(jìn)制數(shù)
const char* hex_char=[[header substringWithRange:NSMakeRange(i*2, 2)] UTF8String];
int_ch = (int)strtoul(hex_char, 0, 16);
// DLog(@"int_ch=%d",int_ch);
bytes[j] = int_ch; ///將轉(zhuǎn)化后的數(shù)放入Byte數(shù)組里
j++;
}
NSMutableData *data = [[NSMutableData alloc] init];
[data appendBytes:bytes length:j];
[data appendData:req.data];
return data;
}
接受到數(shù)據(jù)后钦无，需要把長(zhǎng)度小于message_header長(zhǎng)度的數(shù)據(jù)進(jìn)行拼包，并解析message_header結(jié)構(gòu)
//解析數(shù)據(jù)message_header結(jié)構(gòu)
-(void)parseSocketReceiveData:(NSData*)data result:(void (^)(NSData*result ,int messageId,int hearderId))resultBlock finish:(void(^)())finishBlockMessage{
if (_halfData.length>0) {
[_halfData appendData:data];
data=[_halfData copy];
_halfData =[[NSMutableData alloc]init];
}else{
data=[data copy];
}
if (data.length<20) {
[_halfData appendData:data];
if (finishBlockMessage) {
finishBlockMessage();
}
return;
}
Byte *testByte = (Byte*)[data bytes];
int length=(int) ((testByte[4] & 0xFF<<24)
| ((testByte[5] & 0xFF)<<16)
| ((testByte[6] & 0xFF)<<8)
| ((testByte[7] & 0xFF)));
int messageId=(int) ((testByte[8] & 0xFF<<24)
| ((testByte[9] & 0xFF)<<16)
| ((testByte[10] & 0xFF)<<8)
| ((testByte[11] & 0xFF)));
int headerId=(int)((testByte[12] & 0xFF<<24)
| ((testByte[13] & 0xFF)<<16)
| ((testByte[14] & 0xFF)<<8)
| ((testByte[15] & 0xFF)));
if(length==data.length){
if (resultBlock) {
resultBlock([data subdataWithRange:NSMakeRange(20, length-20)],messageId,headerId);
}
if (finishBlockMessage) {
finishBlockMessage();
}
}else if(length<data.length){
if (resultBlock) {
resultBlock([data subdataWithRange:NSMakeRange(20, length-20)],messageId,headerId);
}
[self parseSocketReceiveData:[data subdataWithRange:NSMakeRange(length, data.length-length)] result:resultBlock finish: finishBlockMessage];
}else{
[_halfData appendData:data];
if (finishBlockMessage) {
finishBlockMessage();
}
}
}
小結(jié)
rtmp協(xié)議雖然加快了數(shù)據(jù)傳輸?shù)男矢窍欢ǔ潭壬系陌踩г荩遣⒉皇翘貏e的安全，為避免攻擊者攻擊苍凛，一些安全措施還是有必要的趣席，在這里不過多介紹兵志，有興趣自己調(diào)研醇蝴。
在線對(duì)戰(zhàn)
IM采用的是環(huán)信SDK，環(huán)信作為免費(fèi)的socket服務(wù)想罕，相對(duì)已經(jīng)很好了悠栓，功能也挺全面霉涨，但是，如果作為嚴(yán)謹(jǐn)?shù)墓δ荛_發(fā)惭适，他所暴露出來的api是遠(yuǎn)遠(yuǎn)不夠的笙瑟，如傳輸?shù)臄?shù)據(jù)必須是它定好的結(jié)構(gòu)，雖然有個(gè)自定義字典可以傳輸?shù)邱荆@個(gè)字典也是僅僅限于幾種數(shù)據(jù)類型（做主要的DATA類型不接受）往枷。導(dǎo)入SDK官方文檔
環(huán)信的主要用到的API
環(huán)信的主要用到的API需要實(shí)現(xiàn)的代理
//在初始化是設(shè)置代理
private override init() {
super.init()
EMClient.shared().add(self, delegateQueue: nil)
EMClient.shared().chatManager.add(self, delegateQueue: nil)
EMClient.shared().contactManager.add(self, delegateQueue: nil)
EMClient.shared().groupManager.add(self, delegateQueue: nil)
EMClient.shared().roomManager.add(self, delegateQueue: nil)
}
//在對(duì)象釋放時(shí)，釋放代理對(duì)象
deinit {
EMClient.shared().removeDelegate(self)
EMClient.shared().chatManager.remove(self)
EMClient.shared().contactManager.removeDelegate(self)
EMClient.shared().groupManager.removeDelegate(self)
EMClient.shared().roomManager.remove(self)
}
實(shí)現(xiàn)登錄異常的代理：服務(wù)器斷開凄杯，開啟定時(shí)器定時(shí)重連（環(huán)信并沒有給出重連的api错洁，我發(fā)現(xiàn)調(diào)用環(huán)信的需要連接服務(wù)器的api，sdk會(huì)自動(dòng)重連服務(wù)器戒突，所以斷開服務(wù)器屯碴，定時(shí)調(diào)用上傳錯(cuò)誤日志的api，機(jī)制吧膊存。）
extension ChatHelpTool: EMClientDelegate{
//主要處理斷開服務(wù)器重連機(jī)制
func connectionStateDidChange(_ aConnectionState: EMConnectionState) {
networkState?(aConnectionState)
switch aConnectionState {
case EMConnectionConnected:
print("服務(wù)器已經(jīng)連上")
if reconnectTimer != nil {
reconnectTimer.invalidate()
reconnectTimer = nil
}
case EMConnectionDisconnected:
print("服務(wù)器已斷開")
if reconnectTimer != nil {
reconnectTimer.invalidate()
reconnectTimer = nil
}
DispatchQueue.global().async {
self.reconnectTimer = Timer.weak_scheduledTimerWithTimeInterval(2, selector: { [weak self] in
self?.reconnectNetwork()
}, repeats: true)
self.reconnectTimer.fire()
RunLoop.current.add(self.reconnectTimer, forMode: RunLoopMode.defaultRunLoopMode)
RunLoop.current.run()
}
default:
()
}
}
func autoLoginDidCompleteWithError(_ aError: EMError!) {
if let error = aError {
TJFTool.errorForCode(code: error.code)
TJFTool.loginOutMessage(message: "自動(dòng)登錄失敗导而，請(qǐng)重新登錄。")
}else {
PAMBManager.sharedInstance.showBriefMessage(message: "自動(dòng)登錄成功")
}
}
//異地登錄
func userAccountDidLoginFromOtherDevice() {
TJFTool.loginOutMessage(message: "該賬號(hào)在其他設(shè)備上登錄,請(qǐng)重新登錄隔崎。")
}
func userAccountDidRemoveFromServer() {
TJFTool.loginOutMessage(message: "當(dāng)前登錄賬號(hào)已經(jīng)被從服務(wù)器端刪除,請(qǐng)重新登錄")
}
func userDidForbidByServer() {
TJFTool.loginOutMessage(message: "服務(wù)被禁用,請(qǐng)重新登錄")
}
}
實(shí)現(xiàn)發(fā)送消息的方法：因?yàn)槭亲远x的數(shù)據(jù)結(jié)構(gòu)今艺，所以使用消息的擴(kuò)展，自定義字典傳遞數(shù)據(jù)仍稀。
//發(fā)送消息
extension ChatHelpTool {
// 定義消息model EMMessage
static func sendTextMessage(text:String,toUser:String,messageType:EMChatType,messageExt:[String:Any]?) ->EMMessage?{
let body = EMTextMessageBody.init(text: text)
let from = EMClient.shared().currentUsername
let message = EMMessage.init(conversationID: toUser, from: from, to: toUser, body: body, ext: messageExt)
message?.chatType = messageType
return message
}
//發(fā)送消息
static func senMessage(aMessage:EMMessage,progress aProgressBlock:(( _ progres: Int32)->())?,completion aCompletionBlock:((_ message:EMMessage?,_ error:EMError?)->())?) {
DispatchQueue.global().async {
EMClient.shared().chatManager.send(aMessage, progress: aProgressBlock,completion:aCompletionBlock)
}
}
}
實(shí)現(xiàn)接收消息的代理
extension ChatHelpTool: EMChatManagerDelegate{
//會(huì)話列表發(fā)生變化<EMConversation>
func conversationListDidUpdate(_ aConversationList: [Any]!) {
print("會(huì)話列表發(fā)生變化")
}
//收到消息
func messagesDidReceive(_ aMessages: [Any]!) {
aMessages.forEach { (message) in
if let message = message as? EMMessage {
if let data = message.ext as? [String:Any] {
let model = MessageModel.init(dictionary: data)
if model.gameType == "1" {
self.letterOfChallengeAction(["userName":message.from,"message":(model.challengeList?.message).noneNull,"chessType":model.chessType.noneNull])
}else if model.gameType == "2" {
var role:Role = .blacker
var gameType:GameType = .LiuZhouChess
if model.chessType == "1" {
role = .whiter
gameType = .fiveInRowChess
}
TJFTool.pushToChessChatRoom(message.from,role,chessType: gameType)
}else {
self.buZiChessMessage?(message)
}
}
}
}
}
//收到已讀回執(zhí)
func messagesDidRead(_ aMessages: [Any]!) {
print("收到已讀回執(zhí)")
}
//收到消息送達(dá)回執(zhí)
func messagesDidDeliver(_ aMessages: [Any]!) {
print("收到消息送達(dá)回執(zhí)")
aMessages.forEach { (message) in
if let message = message as? EMMessage {
if let data = message.ext as? [String:Any] {
let model = MessageModel.init(dictionary: data)
if model.gameType == "3" {
}
}
print(message.messageId)
print(TJFTool.timeWithTimeInterVal(time: message.timestamp),TJFTool.timeWithTimeInterVal(time: message.localTime))
}
}
}
//消息狀態(tài)發(fā)生變化
func messageStatusDidChange(_ aMessage: EMMessage!, error aError: EMError!){
print("消息狀態(tài)發(fā)生變化")
}
}
小結(jié)
IM在沒有服務(wù)器的情況下洼滚，使用第三方免費(fèi)的最方便，但是同時(shí)并不能滿足產(chǎn)品的需求技潘，有機(jī)會(huì)遥巴，我會(huì)為大家分享一篇自定義socket服務(wù)器下的即時(shí)通信結(jié)構(gòu)和邏輯的設(shè)定。
最后
代碼具體實(shí)現(xiàn)地址
代碼中具體實(shí)現(xiàn)了兩個(gè)棋類游戲（有時(shí)間會(huì)持續(xù)添加游戲種類）享幽，包括在線對(duì)戰(zhàn)铲掐，人機(jī)對(duì)戰(zhàn)（算法不錯(cuò)哦），藍(lán)牙對(duì)戰(zhàn)值桩。
代碼編寫不易摆霉，喜歡的請(qǐng)點(diǎn)贊，謝謝奔坟！
