# 賭勝負

## Alpha-Beta修剪

Minimax演算法的一個主要問題是它可以探索那些無關的樹的部分，導致資源的浪費。 因此，必須有一個策略來決定樹的哪一部分是相關的，哪一個是無關緊要的，並且將不相關的部分留給未開發的部分。 Alpha-Beta修剪就是這樣一種策略。

Alpha-Beta修剪演算法的主要目標是避免搜尋樹中沒有任何解決方案的那些部分。 Alpha-Beta修剪的主要概念是使用名為Alpha的兩個邊界(最大下界)和Beta，即最小上界。 這兩個引數是限制可能解決方案集合的值。 它將當前節點的值與alpha和beta引數的值進行比較，以便它可以移動到具有解決方案的樹部分並丟棄其餘部分。

## 建設機器人玩遊戲

``````pip install easyAI
``````

## 一個機器人玩最後的硬幣

``````from easyAI import TwoPlayersGame, id_solve, Human_Player, AI_Player
from easyAI.AI import TT
``````

``````class LastCoin_game(TwoPlayersGame):
def __init__(self, players):
``````

``````self.players = players
self.nplayer = 1
``````

``````self.num_coins = 15
``````

``````self.max_coins = 4
``````

``````def possible_moves(self):
return [str(a) for a in range(1, self.max_coins + 1)]
``````

``````def make_move(self, move):
self.num_coins -= int(move)
``````

``````def win_game(self):
return self.num_coins <= 0
``````

``````def is_over(self):
return self.win()
``````

``````def score(self):
return 100 if self.win_game() else 0
``````

``````def show(self):
print(self.num_coins, 'coins left in the pile')
if __name__ == "__main__":
tt = TT()
LastCoin_game.ttentry = lambda self: self.num_coins
``````

``````r, d, m = id_solve(LastCoin_game,
range(2, 20), win_score=100, tt=tt)
print(r, d, m)
``````

``````game = LastCoin_game([AI_Player(tt), Human_Player()])
game.play()
``````

``````d:2, a:0, m:1
d:3, a:0, m:1
d:4, a:0, m:1
d:5, a:0, m:1
d:6, a:100, m:4
1 6 4
15 coins left in the pile
Move #1: player 1 plays 4 :
11 coins left in the pile
Player 2 what do you play ? 2
Move #2: player 2 plays 2 :
9 coins left in the pile
Move #3: player 1 plays 3 :
6 coins left in the pile
Player 2 what do you play ? 1
Move #4: player 2 plays 1 :
5 coins left in the pile
Move #5: player 1 plays 4 :
1 coins left in the pile
Player 2 what do you play ? 1
Move #6: player 2 plays 1 :
0 coins left in the pile
``````

## 機器人玩井字遊戲

Tic-Tac-Toe非常熟悉，是最受歡迎的遊戲之一。我們通過使用Python中的easyAI庫來建立這個遊戲。 以下程式碼是這款遊戲的Python程式碼 -

``````from easyAI import TwoPlayersGame, AI_Player, Negamax
from easyAI.Player import Human_Player
``````

``````class TicTacToe_game(TwoPlayersGame):
def __init__(self, players):
``````

``````self.players = players
self.nplayer = 1
``````

``````self.board = [0] * 9
``````

``````def possible_moves(self):
return [x + 1 for x, y in enumerate(self.board) if y == 0]
``````

``````def make_move(self, move):
self.board[int(move) - 1] = self.nplayer
``````

``````def umake_move(self, move):
self.board[int(move) - 1] = 0
``````

``````def condition_for_lose(self):
possible_combinations = [[1,2,3], [4,5,6], [7,8,9],
[1,4,7], [2,5,8], [3,6,9], [1,5,9], [3,5,7]]
return any([all([(self.board[z-1] == self.nopponent)
for z in combination]) for combination in possible_combinations])
``````

``````def is_over(self):
return (self.possible_moves() == []) or self.condition_for_lose()
``````

``````def show(self):
print('\n'+'\n'.join([' '.join([['.', 'O', 'X'][self.board[3*j + i]]
for i in range(3)]) for j in range(3)]))
``````

``````def scoring(self):
return -100 if self.condition_for_lose() else 0
``````

``````if __name__ == "__main__":
algo = Negamax(7)
TicTacToe_game([Human_Player(), AI_Player(algo)]).play()
``````

``````. . .
. . .
. . .
Player 1 what do you play ? 1
Move #1: player 1 plays 1 :
O . .
. . .
. . .
Move #2: player 2 plays 5 :
O . .
. X .
121
. . .
Player 1 what do you play ? 3
Move #3: player 1 plays 3 :
O . O
. X .
. . .
Move #4: player 2 plays 2 :
O X O
. X .
. . .
Player 1 what do you play ? 4
Move #5: player 1 plays 4 :
O X O
O X .
. . .
Move #6: player 2 plays 8 :
O X O
O X .
. X .
``````