### gobang_AI

#### by colingogogo

colingogogo / gobang_AI

260 Stars 91 Forks Last release: Not found 3 Commits 0 Releases

Available items

#### No Items, yet!

The developer of this repository has not created any items for sale yet. Need a bug fixed? Help with integration? A different license? Create a request here:

# 棋型的评估分数

shape_score = [(50, (0, 1, 1, 0, 0)), (50, (0, 0, 1, 1, 0)), (200, (1, 1, 0, 1, 0)), (500, (0, 0, 1, 1, 1)), (500, (1, 1, 1, 0, 0)), (5000, (0, 1, 1, 1, 0)), (5000, (0, 1, 0, 1, 1, 0)), (5000, (0, 1, 1, 0, 1, 0)), (5000, (1, 1, 1, 0, 1)), (5000, (1, 1, 0, 1, 1)), (5000, (1, 0, 1, 1, 1)), (5000, (1, 1, 1, 1, 0)), (5000, (0, 1, 1, 1, 1)), (50000, (0, 1, 1, 1, 1, 0)), (99999999, (1, 1, 1, 1, 1))] ``` 这篇文章的示例是用python代码实现， 上面是我列出的一些常见的五子棋形状，1代表有子落在此处，0代表是空位，下一步可以下在此处。 前面是对应的分值。

```

# 评估函数

def evaluation(isai): totalscore = 0

```if is_ai:
my_list = list1
enemy_list = list2
else:
my_list = list2
enemy_list = list1

score_all_arr = []  # 得分形状的位置 用于计算如果有相交 得分翻倍
my_score = 0
for pt in my_list:
m = pt[0]
n = pt[1]
my_score += cal_score(m, n, 0, 1, enemy_list, my_list, score_all_arr)
my_score += cal_score(m, n, 1, 0, enemy_list, my_list, score_all_arr)
my_score += cal_score(m, n, 1, 1, enemy_list, my_list, score_all_arr)
my_score += cal_score(m, n, -1, 1, enemy_list, my_list, score_all_arr)

score_all_arr_enemy = []
enemy_score = 0
for pt in enemy_list:
m = pt[0]
n = pt[1]
enemy_score += cal_score(m, n, 0, 1, my_list, enemy_list, score_all_arr_enemy)
enemy_score += cal_score(m, n, 1, 0, my_list, enemy_list, score_all_arr_enemy)
enemy_score += cal_score(m, n, 1, 1, my_list, enemy_list, score_all_arr_enemy)
enemy_score += cal_score(m, n, -1, 1, my_list, enemy_list, score_all_arr_enemy)
total_score = my_score - enemy_scoreratio0.1
return total_score
```
```对于AI要走在那里最好，那就是计算它在走在某一个点后， 计算局面的得分，然后取得分最大的那个点，不就是最应该下的点吗？ so easy！  这就是极大值搜索。

AI要考虑3步的话， 那就是搜索深度为3，那就是搜索落在那个点，3步后得分最大。这就可以和看能看3步棋的老家伙对抗了。

```

int MinMax(int depth) { // 函数的评估都是以白方的角度来评估的 　if (SideToMove() == WHITE) {　// 白方是“最大”者 　　return Max(depth); 　} else {　　　　　　　　　　　// 黑方是“最小”者 　　return Min(depth); 　} } 　 int Max(int depth) { 　int best = -INFINITY; 　if (depth <= 0) { 　　return Evaluate(); 　} 　GenerateLegalMoves(); 　while (MovesLeft()) { 　　MakeNextMove(); 　　val = Min(depth - 1); 　　UnmakeMove(); 　　if (val > best) { 　　　best = val; 　　} 　} 　return best; } 　 int Min(int depth) { 　int best = INFINITY;　// 注意这里不同于“最大”算法 　if (depth <= 0) { 　　return Evaluate(); 　} 　GenerateLegalMoves(); 　while (MovesLeft()) { 　　MakeNextMove(); 　　val = Max(depth - 1); 　　UnmakeMove(); 　　if (val < best) { 　// 注意这里不同于“最大”算法 　　　best = val; 　　} 　} 　return best; } ``` 到这里， 感觉不就完了吗？可以和老家伙一决高下了？ 这就错了， 忽略了一个很重要的问题， 就是搜索的计算量， 你以为计算机是机器，cpu是 intel i7就瞬间完成计算啊， 这个博弈树，之所以叫树，那么他的枝点的数量，是以指数增长的，搜索深度3和搜索深度5那计算量差的可不是几倍的概念。而是差指数倍的概念。 所以虽然五子棋棋盘没围棋大， 但是按照这种全部可能性都搜索的方法去搜索，是要死电脑的。

## alpha-beta剪枝搜索

α为已知的最大值， β为已知的最小值， 因为还没搜索不知道是多少，保险起见，初始化为-∞ 和+∞。

# 负值极大算法搜索 alpha + beta剪枝

def negamax(isai, depth, alpha, beta): # 游戏是否结束 | | 探索的递归深度是否到边界 if gamewin(list1) or gamewin(list2) or depth == 0: return evaluation(isai)

```blank_list = list(set(list_all).difference(set(list3)))
order(blank_list)   # 搜索顺序排序  提高剪枝效率
# 遍历每一个候选步
for next_step in blank_list:

```global search_count
search_count += 1

# 如果要评估的位置没有相邻的子， 则不去评估  减少计算
if not has_neightnor(next_step):
continue

if is_ai:
list1.append(next_step)
else:
list2.append(next_step)
list3.append(next_step)

value = -negamax(not is_ai, depth - 1, -beta, -alpha)
if is_ai:
list1.remove(next_step)
else:
list2.remove(next_step)
list3.remove(next_step)

if value &gt; alpha:

print(str(value) + "alpha:" + str(alpha) + "beta:" + str(beta))
print(list3)
if depth == DEPTH:
next_point[0] = next_step[0]
next_point[1] = next_step[1]
# alpha + beta剪枝点
if value &gt;= beta:
global cut_count
cut_count += 1
return beta
alpha = value```
return alpha
```
```此处实际的代码可能不太好理解，上伪代码应该好看些，如下：
```

int negamax(GameState S, int depth, int alpha, int beta) { // 游戏是否结束 || 探索的递归深度是否到边界 if ( gameover(S) || depth == 0 ) { return evaluation(S); } // 遍历每一个候选步 foreach ( move in candidate list ) { S' = makemove(S); value = -negamax(S', depth - 1, -beta, -alpha); unmakemove(S') if ( value > alpha ) { // alpha + beta剪枝点 if ( value >= beta ) { return beta; } alpha = value; } } return alpha; } ```

## 源码

We use cookies. If you continue to browse the site, you agree to the use of cookies. For more information on our use of cookies please see our Privacy Policy.