Car*_*orc 3 python artificial-intelligence genetic-algorithm
我一直在认真地尝试创建一个基因程序,它将以可接受的方式发展为井字游戏.我正在使用基因组生成一个函数,然后将板作为输入并输出结果......但它不起作用.
这个程序可以用少于500行代码(包括空行和文档)编写吗？也许我的问题是我正在生成过于简单的AI.
请给我一些帮助和洞察这个适用于这个特定简单问题的"遗传编程"概念.
@OnABauer:我认为我使用遗传编程是因为引用了维基百科
在人工智能中,遗传编程(GP)是一种基于进化算法的方法,其灵感来自生物进化,以发现执行用户定义任务的计算机程序.
我正在尝试生成一个程序(在这种情况下是函数),它将执行玩tic-tac-toe的任务,你可以看到它,因为最重要的输出 genetic_process函数是一个基因组,然后将转换为一个函数因此,如果我理解正确,这是遗传编程,因为输出是一个函数.
代码运行时没有错误也没有崩溃.问题是,最终我得到的是一个无能的人工智能,它将试图非法行动并因每次失败而受到惩罚.它并不比随机更好.
可能是因为我的AI功能如此简单:只需对没有条件的正方形的存储值进行计算.
我的cromosome显示了一系列函数,这些函数将用于减少存储为trinary的电路板数组.好吧,让我举一个例子:*染色体是: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%的基因.除此之外,没有任何随机变异.
那reduce_by_all_functions()是如何被使用的呢？我看到它需要一块板和一条染色体并返回一个数字.这个数字是如何使用的,它代表什么意思,以及...为什么它以模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; 您可以使用强力查找表或简单的游戏树来解决它.
也就是说,如果我理解正确,你的基本观点是这样的:
1)创建长度为8的染色体,其中每个基因是算术运算,并且8基因染色体作为板评估函数作用于每个板.也就是说,染色体接受一个板表示,并吐出一个代表该板的优点的数字.
这是你正在做的事情并不是很清楚,因为你的电路板表示每个都是9个整数(仅限1,2,3),但你的例子是根据"获胜的三元组"给出的,它是2个整数(0到8) ).
2)启动AI,在AI轮到它时,它应该得到所有合法移动的列表,为每个合法移动评估每个染色体的板子...并取这个数字,模9,并将其用作下一步？当然有一些代码来处理这一举动是非法的情况......
3)让一堆这些染色体表示或者发挥标准实现,或者相互发挥作用,并根据获胜次数确定适合度.
4)一旦评估了整整一代染色体,就要创造新一代染色体.我不清楚你是如何从池中选择父母的,但是一旦选择了父母,就可以通过80-20规则从父母那里获取单个基因来生产孩子.
您的整体高级策略是合理的,但执行中存在许多概念和实现缺陷.首先,让我们谈谈完全可观察的游戏以及为他们制作AI的简单方法.如果游戏非常简单(比如Tic Tac Toe),你可以简单地制作一个蛮力极小极大的游戏树,比如这个.TTT很简单,甚至你的手机也可以很快地一直到树的底部.您甚至可以使用查找表通过强力解决它:只需列出所有电路板位置和每个电路板的响应.
当游戏变得更大时 - 想想棋子,国际象棋,去 - 这已不再适用,其中一个方法是开发所谓的棋盘评估功能.这是一个占据董事会位置并返回一个数字的函数,通常对于一个玩家更好,对另一个玩家更好.然后,人们执行搜索到某个可接受的深度,并针对最高(比较)的评估板功能.
这引出了一个问题:我们如何提出董事会评估功能？最初,有人要求游戏专家为您开发这些功能.Chellapilla和Fogel 有一篇很好的论文,类似于你想要为棋子做的事情 - 他们使用神经网络来确定棋盘评估函数,而且,关键的是,这些神经网络被编码为基因组并进化.然后将它们用于搜索深度4树.最终结果与人类玩家竞争非常激烈.
你应该阅读那篇论文.
我想你要做的是非常相似的,除了不将神经网络编码为染色体,你试图编写一个非常有限的代数表达式,总是这样:
((((((((arg1 op1 arg2) op2 arg3) op3 arg4) op4 arg5) op5 arg6) op6 arg7) op7 arg8) op8 arg)
...然后你用mod 9来选择一个动作.
现在让我们谈谈遗传算法,遗传程序和新生儿的创造.进化技术的整体思想是结合两种希望良好的解决方案的最佳属性,希望它们能够更好,而不会陷入局部最大化.
通常,这通过touranment选择,交叉和变异来完成.锦标赛选择意味着按比例选择父母的健康状况.交叉意味着将染色体分成两个通常连续的区域,并从一个亲本获得一个区域而从另一个亲本获得另一个区域.(为什么是连续的？因为荷兰的图式定理)突变意味着偶尔改变基因,作为维持种群多样性的手段.
现在让我们来看看你在做什么:
1)您的电路板评估功能 - 您的染色体变成的功能,它作用于电路板位置 - 受到高度限制并且非常随意.将1,2和3分配为这些数字的韵律或理由并不多,但这可能没什么问题.更大的缺陷是你的功能是整个功能空间的一个非常有限的部分.它们的长度始终相同,并且解析树看起来总是一样.
没有理由期望在这个限制性空间中有任何有用的东西.我们需要的是提出一个允许更一般的解析树集的方案,包括交叉和变异方案.你应该查看John Koza关于这个主题的一些论文或书籍.
请注意,Chellapilla和Fogel也具有固定形式的功能,但是它们的染色体比它们的板表示大得多.跳棋板有32个可玩空间,每个空间可以有5个状态.但是他们的神经网络有大约85个节点,染色体包含这些节点的连接权重 - 数百(如果不是数千)个值.
2)然后就是整个模9的东西.我不明白你为什么那样做.不要那样做.你只是在争论你的染色体中可能存在的任何信息.
3)你创造新孩子的功能很糟糕.即使作为遗传算法,您也应该将染色体分成两部分(在随机点)并从一侧获取一部分父母,而另一部分从另一部分获取另一部分.对于你正在做的遗传编程,有一些类似的策略可以在解析树上进行交叉.见Koza.
您必须包含变异,否则您几乎肯定会得到次优结果.
4a)如果你通过对抗一个称职的人工智能来评估健康状况,那么你就会意识到你的染色体永远不会赢.他们会失败,或者他们会画画.一个称职的AI永远不会失败.此外,你的AI可能会一直失去,而初期几代人可能都是同等(灾难性)的穷人.把你的遗体从那个洞里拿出来并不是不可能的,但这很难.
4b)另一方面,如果像Chellapilla和Fogel一样,你对自己玩AI,那么你最好确定AI可以玩X或O.否则你永远不会取得任何进展所有.
5)最后,即使解决了所有这些问题,我也不相信这会得到很好的结果.请注意,检查器示例搜索深度为4,这在跳棋游戏中可能持续20或30次移动并不是一个很大的视野.
TTT只能持续9次移动.
如果您不进行搜索树并且只是寻求最高的评估板功能,那么您可能会得到一些有用的东西.你可能不会.我不确定.如果搜索到深度4,您也可以跳到完全搜索到9级并按常规执行此操作.