简单游戏的遗传编程，对非专家可行吗？
Genetic programming for simple games, feasible for non-experts?
我一直在认真地尝试创建一个 genetic program，它将进化为以可接受的方式玩井字游戏。我正在使用基因组生成一个函数，然后将电路板作为输入并输出结果...但它不起作用。
这个程序能用少于 500 行的代码（包括空行和文档）写出来吗？也许我的问题是我生成的 AI 太简单了。
我的研究
- A Genetic Algorithm for Tic-Tac-Toe（与我的做法大不相同）。
- http://www.tropicalcoder.com/GeneticAlgorithm.htm（太抽象了）。
- 在相当多的网站中有对 'neural networks' 的引用。他们真的需要吗？
重要免责声明
- 这不是任何类型的家庭作业，只是为了学习一些很酷的东西的个人项目。
- 这不是 'give me the codz plz'，我正在寻找高级建议。我明确不希望现成的解决方案作为答案。
请给我一些帮助，让我深入了解这个应用于这个特定简单问题的 'genetic programming' 概念。
@OnABauer：我认为我正在使用 遗传编程 因为引用维基百科
In artificial intelligence, genetic programming (GP) is an
evolutionary algorithm-based methodology inspired by biological
evolution to find computer programs that perform a user-defined task.
我正在尝试生成一个程序（在本例中为函数）来执行玩井字游戏的任务，您可以看到它，因为最重要的 genetic_process 函数的输出是一个基因组，然后将被转换为一个函数，因此，如果我理解正确的话，这就是遗传编程，因为输出是一个函数。
程序自省和可能的bugs/problems
代码运行没有错误也没有崩溃。问题是，最后我得到的是一个无能的人工智能，它会尝试进行非法移动，并且每次都会受到惩罚。不比随机好。
可能是因为我的 AI 函数太简单了：只对方块的存储值进行计算，没有条件。
高级描述
- 你的染色体代表什么？
我的 cromosome rapresents 一个函数列表，然后将用于减少存储为三进制的电路板数组。好的，让我举个例子：
* 染色体为：amMMMdsa（染色体长度必须为 8）。
1. 第一步是在顶部查找 LETTERS_TO_FUNCTIONS 之后将其转换为函数，这给出函数：[op.add,op.mul,op.mod,op.mod,op.mod,op.floordiv,op.sub,op.add]
第二步是将棋盘转换为三元表示法。所以假设棋盘是 "OX XOX " 我们将得到 [2, 3, 1, 1, 3, 2, 3, 1, 1]
第三步是使用上面得到的函数来减少三重关系。下面的函数可以很好地解释这一点：
def reduce_by_all_functions(numbers_list,functions_list):
"""
Applies all the functions in a list to a list of numbers.
>>> reduce_by_all_functions([3,4,6],[op.add,op.sub])
1
>>> reduce_by_all_functions([6,2,4],[op.mul,op.floordiv])
3
"""
if len(functions_list) != len(numbers_list) - 1:
raise ValueError("The functions must be exactly one less than the numbers")
result = numbers_list[0]
for index,n in enumerate(numbers_list[1:]):
result = functions_list[index](result,n)
return result
因此产生的结果是：0 这意味着 ai 决定进入第一个方格
- 你的健身功能是什么？
幸运的是这很容易回答。
def ai_fitness(genome,accuracy):
"""
Returns how good an ai is by letting it play against a random ai many times.
The higher the value, the best the ai
"""
ai = from_genome_to_ai(genome)
return decide_best_ai(ai,random_ai,accuracy)
- 你的突变是如何工作的？
儿子遗传了父亲 80% 的基因和母亲 20% 的基因。除此之外没有任何随机突变。
And how is that reduce_by_all_functions() being used? I see that it
takes a board and a chromosome and returns a number. How is that
number used, what is it meant to represent, and... why is it being
returned modulo 9?
reduce_by_all_functions()用于实际应用染色体先前获得的功能。数字是ai要走的方格。它是模9，因为它必须在0和8之间，因为棋盘是9个空格。
到目前为止我的代码：
import doctest
import random
import operator as op
SPACE = ' '
MARK_OF_PLAYER_1 = "X"
MARK_OF_PLAYER_2 = "O"
EMPTY_MARK = SPACE
BOARD_NUMBERS = """
The moves are numbered as follows:
0 | 1 | 2
---------
3 | 4 | 5
---------
6 | 7 | 8
"""
WINNING_TRIPLETS = [ (0,1,2), (3,4,5), (6,7,8),
(0,3,6), (1,4,7), (2,5,8),
(0,4,8), (2,4,6) ]
LETTERS_TO_FUNCTIONS = {
'a': op.add,
'm': op.mul,
'M': op.mod,
's': op.sub,
'd': op.floordiv
}
def encode_board_as_trinary(board):
"""
Given a board, replaces the symbols with the numbers
1,2,3 in order to make further processing easier.
>>> encode_board_as_trinary("OX XOX ")
[2, 3, 1, 1, 3, 2, 3, 1, 1]
>>> encode_board_as_trinary(" OOOXXX")
[1, 1, 1, 2, 2, 2, 3, 3, 3]
"""
board = ''.join(board)
board = board.replace(MARK_OF_PLAYER_1,'3')
board = board.replace(MARK_OF_PLAYER_2,'2')
board = board.replace(EMPTY_MARK,'1')
return list((int(square) for square in board))
def create_random_genome(length):
"""
Creates a random genome (that is a sequences of genes, from which
the ai will be generated. It consists of randoom letters taken
from the keys of LETTERS_TO_FUNCTIONS
>>> random.seed("EXAMPLE")
# Test is not possible because even with the same
# seed it gives different results each run...
"""
letters = [letter for letter in LETTERS_TO_FUNCTIONS]
return [random.choice(letters) for _ in range(length)]
def reduce_by_all_functions(numbers_list,functions_list):
"""
Applies all the functions in a list to a list of numbers.
>>> reduce_by_all_functions([3,4,6],[op.add,op.sub])
1
>>> reduce_by_all_functions([6,2,4],[op.mul,op.floordiv])
3
"""
if len(functions_list) != len(numbers_list) - 1:
raise ValueError("The functions must be exactly one less than the numbers")
result = numbers_list[0]
for index,n in enumerate(numbers_list[1:]):
result = functions_list[index](result,n)
return result
def from_genome_to_ai(genome):
"""
Creates an AI following the rules written in the genome (the same as DNA does).
Each letter corresponds to a function as written in LETTERS_TO_FUNCTIONS.
The resulting ai will reduce the board using the functions obtained.
>>> ai = from_genome_to_ai("amMaMMss")
>>> ai("XOX OXO")
4
"""
functions = [LETTERS_TO_FUNCTIONS[gene] for gene in genome]
def ai(board):
return reduce_by_all_functions(encode_board_as_trinary(board),functions) % 9
return ai
def take_first_empty_ai(board):
"""
Very simple example ai for tic-tac-toe
that takes the first empty square.
>>> take_first_empty_ai(' OX O XXO')
0
>>> take_first_empty_ai('XOX O XXO')
3
"""
return board.index(SPACE)
def get_legal_moves(board):
"""
Given a tic-tac-toe board returns the indexes of all
the squares in which it is possible to play, i.e.
the empty squares.
>>> list(get_legal_moves('XOX O XXO'))
[3, 5]
>>> list(get_legal_moves('X O XXO'))
[1, 2, 3, 5]
"""
for index,square in enumerate(board):
if square == SPACE:
yield index
def random_ai(board):
"""
The simplest possible tic-tac-toe 'ai', just
randomly choses a random move.
>>> random.seed("EXAMPLE")
>>> random_ai('X O XXO')
3
"""
legal_moves = list(get_legal_moves(board))
return random.choice(legal_moves)
def printable_board(board):
"""
User Interface function:
returns an easy to understand representation
of the board.
"""
return """
{} | {} | {}
---------
{} | {} | {}
---------
{} | {} | {}""".format(*board)
def human_interface(board):
"""
Allows the user to play tic-tac-toe.
Shows him the board, the board numbers and then asks
him to select a move.
"""
print("The board is:")
print(printable_board(board))
print(BOARD_NUMBERS)
return(int(input("Your move is: ")))
def end_result(board):
"""
Evaluates a board returning:
0.5 if it is a tie
1 if MARK_OF_PLAYER_1 won # default to 'X'
0 if MARK_OF_PLAYER_2 won # default to 'O'
else if nothing of the above applies return None
>>> end_result('XXX OXO')
1
>>> end_result(' O X X O')
None
>>> end_result('OXOXXOXOO')
0.5
"""
if SPACE not in board:
return 0.5
for triplet in WINNING_TRIPLETS:
if all(board[square] == 'X' for square in triplet):
return 1
elif all(board[square] == 'O' for square in triplet):
return 0
def game_ended(board):
"""
Small syntactic sugar function to if the game is ended
i.e. no tie nor win occured
"""
return end_result(board) is not None
def play_ai_tic_tac_toe(ai_1,ai_2):
"""
Plays a game between two different ai-s, returning the result.
It should be noted that this function can be used also to let the user
play against an ai, just call it like: play_ai_tic_tac_toe(random_ai,human_interface)
>>> play_ai_tic_tac_toe(take_first_empty_ai,take_first_empty_ai)
1
"""
board = [SPACE for _ in range(9)]
PLAYER_1_WIN = 1
PLAYER_1_LOSS = 0
while True:
for ai,check in ( (ai_1,MARK_OF_PLAYER_1), (ai_2,MARK_OF_PLAYER_2) ):
move = ai(board)
# If move is invalid you lose
if board[move] != EMPTY_MARK:
if check == MARK_OF_PLAYER_1:
return PLAYER_1_LOSS
else:
return PLAYER_1_WIN
board[move] = check
if game_ended(board):
return end_result(board)
def loop_play_ai_tic_tac_toe(ai_1,ai_2,games_number):
"""
Plays games number games between ai_1 and ai_2
"""
return sum(( play_ai_tic_tac_toe(ai_1,ai_2)) for _ in range(games_number))
def decide_best_ai(ai_1,ai_2,accuracy):
"""
Returns the number of times the first ai is better than the second:
ex. if the ouput is 1.4, the first ai is 1.4 times better than the second.
>>> decide_best_ai(take_first_empty_ai,random_ai,100) > 0.80
True
"""
return sum((loop_play_ai_tic_tac_toe(ai_1,ai_2,accuracy//2),
loop_play_ai_tic_tac_toe(ai_2,ai_1,accuracy//2))) / (accuracy // 2)
def ai_fitness(genome,accuracy):
"""
Returns how good an ai is by lettting it play against a random ai many times.
The higher the value, the best the ai
"""
ai = from_genome_to_ai(genome)
return decide_best_ai(ai,random_ai,accuracy)
def sort_by_fitness(genomes,accuracy):
"""
Syntactic sugar for sorting a list of genomes based on the fitness.
High accuracy will yield a more accurate ordering but at the cost of more
computation time.
"""
def fit(genome):
return ai_fitness(genome,accuracy)
return list(sorted(genomes, key=fit, reverse=True))
# probable bug-fix because high fitness means better individual
def make_child(a,b):
"""
Returns a mix of cromosome a and cromosome b.
There is a bias towards cromosome a because I think that
a too weird soon is going to be bad.
"""
result = []
for index,char_a in enumerate(a):
char_b = b[index]
if random.random() > 0.8:
result.append(char_a)
else:
result.append(char_b)
return result
def genetic_process(population_size,generation_number,accuracy,elite_number):
"""
A full genetic process yielding a good tic-tac-toe ai. # not yet
@ Parameters:
@ population_size: the number of ai-s that you allow to be alive
at once
@ generation_number: the number of generations of the gentetic
@ accuracy: how well the ai-s are ordered,
low accuracy means that a good ai may be considered bad or
viceversa. High accuarcy is computationally costly
@ elite_number: the number of best programmes that get to reproduce
at each generation.
@ Return:
@ A genome for a tic-tac-toe ai
"""
pool = [create_random_genome(9-1) for _ in range(population_size)]
for generation in range(generation_number):
best_individuals = sort_by_fitness(pool,accuracy)[:elite_number]
the_best = best_individuals[0]
for good_individual in best_individuals:
pool.append(make_child(the_best,good_individual))
pool = sort_by_fitness(pool,accuracy)[:population_size]
return the_best
def _test():
"""
Tests all the script by running the
>>> 2 + 2 # code formatted like this
4
"""
doctest.testmod()
def main():
"""
A simple demo to let the user play against a genetic opponent.
"""
print("The genetic ai is being created... please wait.")
genetic_ai = from_genome_to_ai(genetic_process(50,4,40,25))
play_ai_tic_tac_toe(genetic_ai,human_interface)
if __name__ == '__main__':
main()
首先，我不得不说，Tic Tac Toe 真的是一个太简单的问题，无法用遗传程序进行合理的攻击。您根本不需要 GP 的力量来赢得 Tic Tac Toe；你可以用蛮力查找 table 或简单的游戏树来解决它。
也就是说，如果我没理解错的话，你的基本概念是这样的：
1）创建长度为8的染色体，其中每个基因都是一次算术运算，8个基因的染色体作用在每个棋盘上作为棋盘评价函数。也就是说，染色体接受棋盘表示，并吐出一个代表该棋盘优劣的数字。
你不是很清楚这就是你在做什么，因为你的棋盘代表每个都是 9 个整数（仅限 1、2、3）但是你的例子是根据 "winning triples" 给出的2 个整数（0 到 8）。
2) 启动 AI，轮到 AI 时，它应该获得所有合法移动的列表，针对每个合法移动根据其染色体评估棋盘，然后...取那个数字，mod ulo 9，并以此为下一步行动？肯定有一些代码可以处理非法移动的情况....
3) 让一堆这些染色体表示要么玩一个标准实现，要么互相玩，根据获胜的次数来确定适应度。
4) 对整代染色体进行评估后，创建新一代。我不清楚你是如何从池中选择 parents 的，但是一旦选择了 parents，只需从 [=74] 中获取单个基因就可以产生 child =]s 遵循 80-20 规则。
您的整体高级战略是合理的，但在执行过程中存在很多概念和实施缺陷。首先，让我们谈谈完全可观察的游戏和为它们制作 AI 的简单方法。如果游戏非常简单（比如井字棋）你可以简单地做一个蛮力minimax游戏树，such as this。 TTT 非常简单，甚至您的单元格 phone 也可以非常快速地一直走到树的底部。您甚至可以通过查找 table 的蛮力解决它：只需列出所有棋盘位置和对每个位置的响应即可。
当游戏变得更大时——想想西洋跳棋、国际象棋、围棋——这就不再正确了，解决这个问题的方法之一是开发所谓的棋盘评估功能。这是一个采用棋盘位置和 returns 数字的函数，通常一个玩家越高越好，另一个玩家越低。然后执行搜索到一定的 acceptable 深度，并以最高（比如说）董事会评估功能为目标。
这就引出了一个问题：我们如何得出董事会评估函数？本来是请游戏里的专家给你开发这些功能的。 Chellapilla 和 Fogel 的一个很棒的 paper 类似于你想为西洋跳棋做的——他们使用神经网络来确定棋盘评估函数，而且，关键的是，这些神经网络被编码为基因组并进化.然后将它们用于搜索深度为 4 的树。最终结果与人类玩家的竞争非常激烈。
你应该阅读那篇论文。
我认为您正在尝试做的事情非常相似，除了您不是将神经网络编码为染色体，而是尝试编写一个非常受限的代数表达式，其形式始终为：
((((((((arg1 op1 arg2) op2 arg3) op3 arg4) op4 arg5) op5 arg6) op6 arg7) op7 arg8) op8 arg)
... 然后你用它 mod 9 来选择一步棋。
现在我们来谈谈遗传算法、遗传程序和新 children 的创造。进化技术的整个思想是结合两个 hopefully-good 解决方案的最佳属性，希望它们会更好，而不会陷入局部最大值。
一般来说，这是通过锦标赛选择、交叉和变异来完成的。锦标赛选择意味着选择 parents 与他们的健康成比例。交叉意味着将染色体分成两个通常相邻的区域，并从一个 parent 中取出一个区域，从另一个 parent 中取出另一个区域。 （为什么是连续的？因为Holland's Schema Theorem）突变意味着偶尔改变一个基因，作为维持种群多样性的一种手段。
现在让我们看看你在做什么：
1) 你的棋盘评估函数——你的染色体变成的作用于棋盘位置的函数——是高度受限且非常随意的。将 1、2 和 3 指定为这些数字没有太多韵律或理由，但这可能没问题。更大的缺陷是您的函数是整个 space 函数中非常受限的一部分。它们的长度总是相同的，解析树看起来也总是一样的。
没有理由期望在这个限制性 space 中有任何有用的东西。需要的是提出一个方案，允许更通用的解析树集，包括交叉和变异方案。您应该查阅 John Koza 的一些论文或书籍以了解有关此主题的想法。
请注意，Chellapilla 和 Fogel 也有固定形式的函数，但他们的染色体比他们的棋盘表示要大得多。跳棋棋盘有 32 个可玩的 space，每个 space 可以有 5 个状态。但他们的神经网络有大约 85 个节点，染色体包含这些节点的连接权重——数百个（如果不是数千个）值。
2) 然后是整个 modulo 9 的事情。我不明白你为什么要那样做。不要那样做。你只是在打乱染色体中可能存在的任何信息。
3) 你的新 children 功能不好。即使作为遗传算法，您也应该将染色体一分为二（在随机点）并从一侧取一部分 parent，另一部分从另一侧取另一 parent。对于您正在做的遗传编程，有类似的策略可以在解析树上进行交叉。见科萨。
您必须包含突变，否则您几乎肯定会得到 sub-optimal 结果。
4a) 如果你通过与有能力的 AI 比赛来评估适应性，那么你会意识到你的染色体永远不会赢。他们要么输，要么平局。一个有能力的人工智能永远不会输。此外，您的 AI 很可能会一直输，而最初几代人可能都同样（灾难性地）表现不佳。使自己脱离困境并非不可能，但会很困难。
4b) 另一方面，如果像 Chellapilla 和 Fogel 一样，你让 AI 与他们自己对抗，那么你最好确保 AI 可以玩 X 或 O。否则你永远不会取得任何进展。
5) 最后，即使所有这些问题都得到解决，我也不相信这会取得很好的结果。请注意，跳棋示例的搜索深度为 4，这对于可能持续 20 或 30 步的跳棋游戏来说并不是一个很大的范围。
TTT 只能持续 9 步。
如果你不做搜索树而只追求最高的董事会评估功能，你可能会得到一些有用的东西。你可能不会。我不确定。如果你搜索到深度 4，你还不如跳到完全搜索到第 9 级，并按常规执行此操作。
我一直在认真地尝试创建一个 genetic program，它将进化为以可接受的方式玩井字游戏。我正在使用基因组生成一个函数，然后将电路板作为输入并输出结果...但它不起作用。
这个程序能用少于 500 行的代码（包括空行和文档）写出来吗？也许我的问题是我生成的 AI 太简单了。
我的研究
- A Genetic Algorithm for Tic-Tac-Toe（与我的做法大不相同）。
- http://www.tropicalcoder.com/GeneticAlgorithm.htm（太抽象了）。
- 在相当多的网站中有对 'neural networks' 的引用。他们真的需要吗？
重要免责声明
- 这不是任何类型的家庭作业，只是为了学习一些很酷的东西的个人项目。
- 这不是 'give me the codz plz'，我正在寻找高级建议。我明确不希望现成的解决方案作为答案。
请给我一些帮助，让我深入了解这个应用于这个特定简单问题的 'genetic programming' 概念。
@OnABauer：我认为我正在使用 遗传编程 因为引用维基百科
In artificial intelligence, genetic programming (GP) is an evolutionary algorithm-based methodology inspired by biological evolution to find computer programs that perform a user-defined task.
我正在尝试生成一个程序（在本例中为函数）来执行玩井字游戏的任务，您可以看到它，因为最重要的 genetic_process 函数的输出是一个基因组，然后将被转换为一个函数，因此，如果我理解正确的话，这就是遗传编程，因为输出是一个函数。
程序自省和可能的bugs/problems
代码运行没有错误也没有崩溃。问题是，最后我得到的是一个无能的人工智能，它会尝试进行非法移动，并且每次都会受到惩罚。不比随机好。
可能是因为我的 AI 函数太简单了：只对方块的存储值进行计算，没有条件。
高级描述
- 你的染色体代表什么？
我的 cromosome rapresents 一个函数列表，然后将用于减少存储为三进制的电路板数组。好的，让我举个例子：
* 染色体为：amMMMdsa（染色体长度必须为 8）。
1. 第一步是在顶部查找 LETTERS_TO_FUNCTIONS 之后将其转换为函数，这给出函数：[op.add,op.mul,op.mod,op.mod,op.mod,op.floordiv,op.sub,op.add]
第二步是将棋盘转换为三元表示法。所以假设棋盘是
"OX XOX "我们将得到 [2, 3, 1, 1, 3, 2, 3, 1, 1]第三步是使用上面得到的函数来减少三重关系。下面的函数可以很好地解释这一点：
def reduce_by_all_functions(numbers_list,functions_list): """ Applies all the functions in a list to a list of numbers. >>> reduce_by_all_functions([3,4,6],[op.add,op.sub]) 1 >>> reduce_by_all_functions([6,2,4],[op.mul,op.floordiv]) 3 """ if len(functions_list) != len(numbers_list) - 1: raise ValueError("The functions must be exactly one less than the numbers") result = numbers_list[0] for index,n in enumerate(numbers_list[1:]): result = functions_list[index](result,n) return result因此产生的结果是：
0这意味着 ai 决定进入第一个方格- 你的健身功能是什么？
幸运的是这很容易回答。
def ai_fitness(genome,accuracy):
"""
Returns how good an ai is by letting it play against a random ai many times.
The higher the value, the best the ai
"""
ai = from_genome_to_ai(genome)
return decide_best_ai(ai,random_ai,accuracy)
- 你的突变是如何工作的？
儿子遗传了父亲 80% 的基因和母亲 20% 的基因。除此之外没有任何随机突变。
And how is that reduce_by_all_functions() being used? I see that it takes a board and a chromosome and returns a number. How is that number used, what is it meant to represent, and... why is it being returned modulo 9?
reduce_by_all_functions()用于实际应用染色体先前获得的功能。数字是ai要走的方格。它是模9，因为它必须在0和8之间，因为棋盘是9个空格。
到目前为止我的代码：
import doctest
import random
import operator as op
SPACE = ' '
MARK_OF_PLAYER_1 = "X"
MARK_OF_PLAYER_2 = "O"
EMPTY_MARK = SPACE
BOARD_NUMBERS = """
The moves are numbered as follows:
0 | 1 | 2
---------
3 | 4 | 5
---------
6 | 7 | 8
"""
WINNING_TRIPLETS = [ (0,1,2), (3,4,5), (6,7,8),
(0,3,6), (1,4,7), (2,5,8),
(0,4,8), (2,4,6) ]
LETTERS_TO_FUNCTIONS = {
'a': op.add,
'm': op.mul,
'M': op.mod,
's': op.sub,
'd': op.floordiv
}
def encode_board_as_trinary(board):
"""
Given a board, replaces the symbols with the numbers
1,2,3 in order to make further processing easier.
>>> encode_board_as_trinary("OX XOX ")
[2, 3, 1, 1, 3, 2, 3, 1, 1]
>>> encode_board_as_trinary(" OOOXXX")
[1, 1, 1, 2, 2, 2, 3, 3, 3]
"""
board = ''.join(board)
board = board.replace(MARK_OF_PLAYER_1,'3')
board = board.replace(MARK_OF_PLAYER_2,'2')
board = board.replace(EMPTY_MARK,'1')
return list((int(square) for square in board))
def create_random_genome(length):
"""
Creates a random genome (that is a sequences of genes, from which
the ai will be generated. It consists of randoom letters taken
from the keys of LETTERS_TO_FUNCTIONS
>>> random.seed("EXAMPLE")
# Test is not possible because even with the same
# seed it gives different results each run...
"""
letters = [letter for letter in LETTERS_TO_FUNCTIONS]
return [random.choice(letters) for _ in range(length)]
def reduce_by_all_functions(numbers_list,functions_list):
"""
Applies all the functions in a list to a list of numbers.
>>> reduce_by_all_functions([3,4,6],[op.add,op.sub])
1
>>> reduce_by_all_functions([6,2,4],[op.mul,op.floordiv])
3
"""
if len(functions_list) != len(numbers_list) - 1:
raise ValueError("The functions must be exactly one less than the numbers")
result = numbers_list[0]
for index,n in enumerate(numbers_list[1:]):
result = functions_list[index](result,n)
return result
def from_genome_to_ai(genome):
"""
Creates an AI following the rules written in the genome (the same as DNA does).
Each letter corresponds to a function as written in LETTERS_TO_FUNCTIONS.
The resulting ai will reduce the board using the functions obtained.
>>> ai = from_genome_to_ai("amMaMMss")
>>> ai("XOX OXO")
4
"""
functions = [LETTERS_TO_FUNCTIONS[gene] for gene in genome]
def ai(board):
return reduce_by_all_functions(encode_board_as_trinary(board),functions) % 9
return ai
def take_first_empty_ai(board):
"""
Very simple example ai for tic-tac-toe
that takes the first empty square.
>>> take_first_empty_ai(' OX O XXO')
0
>>> take_first_empty_ai('XOX O XXO')
3
"""
return board.index(SPACE)
def get_legal_moves(board):
"""
Given a tic-tac-toe board returns the indexes of all
the squares in which it is possible to play, i.e.
the empty squares.
>>> list(get_legal_moves('XOX O XXO'))
[3, 5]
>>> list(get_legal_moves('X O XXO'))
[1, 2, 3, 5]
"""
for index,square in enumerate(board):
if square == SPACE:
yield index
def random_ai(board):
"""
The simplest possible tic-tac-toe 'ai', just
randomly choses a random move.
>>> random.seed("EXAMPLE")
>>> random_ai('X O XXO')
3
"""
legal_moves = list(get_legal_moves(board))
return random.choice(legal_moves)
def printable_board(board):
"""
User Interface function:
returns an easy to understand representation
of the board.
"""
return """
{} | {} | {}
---------
{} | {} | {}
---------
{} | {} | {}""".format(*board)
def human_interface(board):
"""
Allows the user to play tic-tac-toe.
Shows him the board, the board numbers and then asks
him to select a move.
"""
print("The board is:")
print(printable_board(board))
print(BOARD_NUMBERS)
return(int(input("Your move is: ")))
def end_result(board):
"""
Evaluates a board returning:
0.5 if it is a tie
1 if MARK_OF_PLAYER_1 won # default to 'X'
0 if MARK_OF_PLAYER_2 won # default to 'O'
else if nothing of the above applies return None
>>> end_result('XXX OXO')
1
>>> end_result(' O X X O')
None
>>> end_result('OXOXXOXOO')
0.5
"""
if SPACE not in board:
return 0.5
for triplet in WINNING_TRIPLETS:
if all(board[square] == 'X' for square in triplet):
return 1
elif all(board[square] == 'O' for square in triplet):
return 0
def game_ended(board):
"""
Small syntactic sugar function to if the game is ended
i.e. no tie nor win occured
"""
return end_result(board) is not None
def play_ai_tic_tac_toe(ai_1,ai_2):
"""
Plays a game between two different ai-s, returning the result.
It should be noted that this function can be used also to let the user
play against an ai, just call it like: play_ai_tic_tac_toe(random_ai,human_interface)
>>> play_ai_tic_tac_toe(take_first_empty_ai,take_first_empty_ai)
1
"""
board = [SPACE for _ in range(9)]
PLAYER_1_WIN = 1
PLAYER_1_LOSS = 0
while True:
for ai,check in ( (ai_1,MARK_OF_PLAYER_1), (ai_2,MARK_OF_PLAYER_2) ):
move = ai(board)
# If move is invalid you lose
if board[move] != EMPTY_MARK:
if check == MARK_OF_PLAYER_1:
return PLAYER_1_LOSS
else:
return PLAYER_1_WIN
board[move] = check
if game_ended(board):
return end_result(board)
def loop_play_ai_tic_tac_toe(ai_1,ai_2,games_number):
"""
Plays games number games between ai_1 and ai_2
"""
return sum(( play_ai_tic_tac_toe(ai_1,ai_2)) for _ in range(games_number))
def decide_best_ai(ai_1,ai_2,accuracy):
"""
Returns the number of times the first ai is better than the second:
ex. if the ouput is 1.4, the first ai is 1.4 times better than the second.
>>> decide_best_ai(take_first_empty_ai,random_ai,100) > 0.80
True
"""
return sum((loop_play_ai_tic_tac_toe(ai_1,ai_2,accuracy//2),
loop_play_ai_tic_tac_toe(ai_2,ai_1,accuracy//2))) / (accuracy // 2)
def ai_fitness(genome,accuracy):
"""
Returns how good an ai is by lettting it play against a random ai many times.
The higher the value, the best the ai
"""
ai = from_genome_to_ai(genome)
return decide_best_ai(ai,random_ai,accuracy)
def sort_by_fitness(genomes,accuracy):
"""
Syntactic sugar for sorting a list of genomes based on the fitness.
High accuracy will yield a more accurate ordering but at the cost of more
computation time.
"""
def fit(genome):
return ai_fitness(genome,accuracy)
return list(sorted(genomes, key=fit, reverse=True))
# probable bug-fix because high fitness means better individual
def make_child(a,b):
"""
Returns a mix of cromosome a and cromosome b.
There is a bias towards cromosome a because I think that
a too weird soon is going to be bad.
"""
result = []
for index,char_a in enumerate(a):
char_b = b[index]
if random.random() > 0.8:
result.append(char_a)
else:
result.append(char_b)
return result
def genetic_process(population_size,generation_number,accuracy,elite_number):
"""
A full genetic process yielding a good tic-tac-toe ai. # not yet
@ Parameters:
@ population_size: the number of ai-s that you allow to be alive
at once
@ generation_number: the number of generations of the gentetic
@ accuracy: how well the ai-s are ordered,
low accuracy means that a good ai may be considered bad or
viceversa. High accuarcy is computationally costly
@ elite_number: the number of best programmes that get to reproduce
at each generation.
@ Return:
@ A genome for a tic-tac-toe ai
"""
pool = [create_random_genome(9-1) for _ in range(population_size)]
for generation in range(generation_number):
best_individuals = sort_by_fitness(pool,accuracy)[:elite_number]
the_best = best_individuals[0]
for good_individual in best_individuals:
pool.append(make_child(the_best,good_individual))
pool = sort_by_fitness(pool,accuracy)[:population_size]
return the_best
def _test():
"""
Tests all the script by running the
>>> 2 + 2 # code formatted like this
4
"""
doctest.testmod()
def main():
"""
A simple demo to let the user play against a genetic opponent.
"""
print("The genetic ai is being created... please wait.")
genetic_ai = from_genome_to_ai(genetic_process(50,4,40,25))
play_ai_tic_tac_toe(genetic_ai,human_interface)
if __name__ == '__main__':
main()
首先，我不得不说，Tic Tac Toe 真的是一个太简单的问题，无法用遗传程序进行合理的攻击。您根本不需要 GP 的力量来赢得 Tic Tac Toe；你可以用蛮力查找 table 或简单的游戏树来解决它。
也就是说，如果我没理解错的话，你的基本概念是这样的：
1）创建长度为8的染色体，其中每个基因都是一次算术运算，8个基因的染色体作用在每个棋盘上作为棋盘评价函数。也就是说，染色体接受棋盘表示，并吐出一个代表该棋盘优劣的数字。
你不是很清楚这就是你在做什么，因为你的棋盘代表每个都是 9 个整数（仅限 1、2、3）但是你的例子是根据 "winning triples" 给出的2 个整数（0 到 8）。
2) 启动 AI，轮到 AI 时，它应该获得所有合法移动的列表，针对每个合法移动根据其染色体评估棋盘，然后...取那个数字，mod ulo 9，并以此为下一步行动？肯定有一些代码可以处理非法移动的情况....
3) 让一堆这些染色体表示要么玩一个标准实现，要么互相玩，根据获胜的次数来确定适应度。
4) 对整代染色体进行评估后，创建新一代。我不清楚你是如何从池中选择 parents 的，但是一旦选择了 parents，只需从 [=74] 中获取单个基因就可以产生 child =]s 遵循 80-20 规则。
您的整体高级战略是合理的，但在执行过程中存在很多概念和实施缺陷。首先，让我们谈谈完全可观察的游戏和为它们制作 AI 的简单方法。如果游戏非常简单（比如井字棋）你可以简单地做一个蛮力minimax游戏树，such as this。 TTT 非常简单，甚至您的单元格 phone 也可以非常快速地一直走到树的底部。您甚至可以通过查找 table 的蛮力解决它：只需列出所有棋盘位置和对每个位置的响应即可。
当游戏变得更大时——想想西洋跳棋、国际象棋、围棋——这就不再正确了，解决这个问题的方法之一是开发所谓的棋盘评估功能。这是一个采用棋盘位置和 returns 数字的函数，通常一个玩家越高越好，另一个玩家越低。然后执行搜索到一定的 acceptable 深度，并以最高（比如说）董事会评估功能为目标。
这就引出了一个问题：我们如何得出董事会评估函数？本来是请游戏里的专家给你开发这些功能的。 Chellapilla 和 Fogel 的一个很棒的 paper 类似于你想为西洋跳棋做的——他们使用神经网络来确定棋盘评估函数，而且，关键的是，这些神经网络被编码为基因组并进化.然后将它们用于搜索深度为 4 的树。最终结果与人类玩家的竞争非常激烈。
你应该阅读那篇论文。
我认为您正在尝试做的事情非常相似，除了您不是将神经网络编码为染色体，而是尝试编写一个非常受限的代数表达式，其形式始终为：
((((((((arg1 op1 arg2) op2 arg3) op3 arg4) op4 arg5) op5 arg6) op6 arg7) op7 arg8) op8 arg)
... 然后你用它 mod 9 来选择一步棋。
现在我们来谈谈遗传算法、遗传程序和新 children 的创造。进化技术的整个思想是结合两个 hopefully-good 解决方案的最佳属性，希望它们会更好，而不会陷入局部最大值。
一般来说，这是通过锦标赛选择、交叉和变异来完成的。锦标赛选择意味着选择 parents 与他们的健康成比例。交叉意味着将染色体分成两个通常相邻的区域，并从一个 parent 中取出一个区域，从另一个 parent 中取出另一个区域。 （为什么是连续的？因为Holland's Schema Theorem）突变意味着偶尔改变一个基因，作为维持种群多样性的一种手段。
现在让我们看看你在做什么：
1) 你的棋盘评估函数——你的染色体变成的作用于棋盘位置的函数——是高度受限且非常随意的。将 1、2 和 3 指定为这些数字没有太多韵律或理由，但这可能没问题。更大的缺陷是您的函数是整个 space 函数中非常受限的一部分。它们的长度总是相同的，解析树看起来也总是一样的。
没有理由期望在这个限制性 space 中有任何有用的东西。需要的是提出一个方案，允许更通用的解析树集，包括交叉和变异方案。您应该查阅 John Koza 的一些论文或书籍以了解有关此主题的想法。
请注意，Chellapilla 和 Fogel 也有固定形式的函数，但他们的染色体比他们的棋盘表示要大得多。跳棋棋盘有 32 个可玩的 space，每个 space 可以有 5 个状态。但他们的神经网络有大约 85 个节点，染色体包含这些节点的连接权重——数百个（如果不是数千个）值。
2) 然后是整个 modulo 9 的事情。我不明白你为什么要那样做。不要那样做。你只是在打乱染色体中可能存在的任何信息。
3) 你的新 children 功能不好。即使作为遗传算法，您也应该将染色体一分为二（在随机点）并从一侧取一部分 parent，另一部分从另一侧取另一 parent。对于您正在做的遗传编程，有类似的策略可以在解析树上进行交叉。见科萨。
您必须包含突变，否则您几乎肯定会得到 sub-optimal 结果。
4a) 如果你通过与有能力的 AI 比赛来评估适应性，那么你会意识到你的染色体永远不会赢。他们要么输，要么平局。一个有能力的人工智能永远不会输。此外，您的 AI 很可能会一直输，而最初几代人可能都同样（灾难性地）表现不佳。使自己脱离困境并非不可能，但会很困难。
4b) 另一方面，如果像 Chellapilla 和 Fogel 一样，你让 AI 与他们自己对抗，那么你最好确保 AI 可以玩 X 或 O。否则你永远不会取得任何进展。
5) 最后，即使所有这些问题都得到解决，我也不相信这会取得很好的结果。请注意，跳棋示例的搜索深度为 4，这对于可能持续 20 或 30 步的跳棋游戏来说并不是一个很大的范围。
TTT 只能持续 9 步。
如果你不做搜索树而只追求最高的董事会评估功能，你可能会得到一些有用的东西。你可能不会。我不确定。如果你搜索到深度 4，你还不如跳到完全搜索到第 9 级，并按常规执行此操作。