from?graphics?import?*
from?math?import?*
import?numpy?as?np

GRID_WIDTH?=?40

COLUMN?=?15
ROW?=?15

list1?=?[]??#?AI
list2?=?[]??#?human
list3?=?[]??#?all

list_all?=?[]??#?整個棋盤的點
next_point?=?[0?0]??#?AI下一步最應該下的位置

ratio?=?1??#?進攻的系數???大于1?進攻型，??小于1?防守型
DEPTH?=?3??#?搜索深度???只能是單數。??如果是負數，?評估函數評估的的是自己多少步之后的自己得分的最大值，并不意味著是最好的棋，?評估函數的問題


#?棋型的評估分數
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））]


def?ai（）:
????global?cut_count???#?統計剪枝次數
????cut_count?=?0
????global?search_count???#?統計搜索次數
????search_count?=?0
????negamax（True?DEPTH?-99999999?99999999）
????print（“本次共剪枝次數：“?+?str（cut_count））
????print（“本次共搜索次數：“?+?str（search_count））
????return?next_point[0]?next_point[1]


#?負值極大算法搜索?alpha?+?beta剪枝
def?negamax（is_ai?depth?alpha?beta）:
????#?游戲是否結束?|?|?探索的遞歸深度是否到邊界
????if?game_win（list1）?or?game_win（list2）?or?depth?==?0:
????????return?evaluation（is_ai）

????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?>?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?>=?beta:
????????????????global?cut_count
????????????????cut_count?+=?1
????????????????return?beta
????????????alpha?=?value

????return?alpha


#??離最后落子的鄰居位置最有可能是最優點
def?order（blank_list）:
????last_pt?=?list3[-1]
????for?item?in?blank_list:
????????for?i?in?range（-1?2）:
????????????for?j?in?range（-1?2）:
????????????????if?i?==?0?and?j?==?0:
????????????????????continue
????????????????if?（last_pt[0]?+?i?last_pt[1]?+?j）?in?blank_list:
????????????????????blank_list.remove（（last_pt[0]?+?i?last_pt[1]?+?j））
????

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2017-07-14?08:50??gobang_AI-master\
?????文件???????12737??2017-07-14?08:50??gobang_AI-master\README.md
?????文件???????10575??2017-07-14?08:50??gobang_AI-master\gobang_AI.py
?????文件???????31552??2017-07-14?08:50??gobang_AI-master\graphics.py