Closed. This question needs to be more
focused。它当前不接受答案。
想改善这个问题吗？更新问题，使其仅通过
editing this post专注于一个问题。
5年前关闭。
Improve this question
我一直在认真尝试创建一个
genetic program，它将以可接受的方式发展为打井字游戏。我正在使用基因组生成一个函数，该函数然后将板子作为输入并输出结果...但是它不起作用。
可以用少于500行的代码（包括空白行和文档）编写此程序吗？也许我的问题是我生成的AI太简单了。
我的研究
A Genetic Algorithm for Tic-Tac-Toe（与我的方法完全不同）。
http://www.tropicalcoder.com/GeneticAlgorithm.htm（太抽象了）。
在相当多的网站中都引用了“神经网络”。他们真的需要吗？
重要免责声明
这不是任何形式的家庭作业，只是为了学习一些酷东西的个人项目。
这不是“给我codz plz”，我正在寻找高级建议。我明确不希望将现成的解决方案作为答案。
请给我一些帮助，并深入了解适用于此特定简单问题的“遗传编程”概念。
@OnABauer：我认为我正在使用基因编程，因为引用了维基百科
在人工智能中，基因编程（GP）是
受生物学启发的基于进化算法的方法
寻找执行用户定义任务的计算机程序的进化。
我正在尝试生成一个程序（在本例中为函数），该程序将执行井字游戏的任务，您可以看到它，因为最重要的
genetic_process函数的输出是一个基因组，然后将其转换函数，因此，如果我正确理解的话，这是遗传编程，因为输出是函数。
程序自省和可能的错误/问题
该代码运行没有错误也没有崩溃。问题在于，最终我得到的是一个不称职的AI，它将试图做出非法举动，并因每次失败而受到惩罚。没有比随机更好的了。
可能是因为我的AI函数非常简单：无条件地对平方的存储值进行计算。
高层描述
您的染色体代表什么？
我的染色体显示了一系列功能，这些功能随后将用于减少存储为三进制的电路板阵列。好，让我举个例子：
*染色体是：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，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()
首先，我不得不说井字游戏确实是一个太简单的问题，无法用基因程序进行合理的攻击。您根本不需要GP的力量就能赢得井字游戏。您可以使用蛮力查找表或简单的游戏树来解决它。
也就是说，如果我理解正确，那么您的基本概念是：
1）创建长度为8的染色体，其中每个基因都是算术运算，而8基因染色体在每个板上均作为板评估功能起作用。就是说，一条染色体接受一个板的表示，并吐出一个代表该板的良性的数字。
并不是很清楚这就是您正在做的事情，因为您的棋盘表示每个都是9个整数（仅1，2，3），但是您的示例是以“获胜三元组”的形式给出的，这是2个整数（0至8） ）。
2）启动AI，然后在AI上获取所有合法举动的清单，针对每个合法举动评估其染色体上的董事会，并...将该数字取模9，然后将其用作下一个举动？当然，其中有一些代码可以处理这种举动是非法的情况。
3）让这些染色体表示中的一堆发挥标准功能，或者互相发挥作用，并根据获胜次数确定适应度。
4）一旦评估了一代完整的染色体，请创建新一代。我不清楚您是如何从游泳池中选择父母的，但是一旦选择了父母，就可以按照80至20条规则从父母那里获取单个基因来生产一个孩子。
您的总体高级策略是合理的，但是执行中存在许多概念和实现方面的缺陷。首先，让我们谈谈完全可观察的游戏以及为它们制作AI的简单方法。如果游戏非常简单（例如Tic Tac Toe），则可以简单地制作一个暴力的minimax游戏树such as this。 TTT非常简单，即使您的手机也可以非常迅速地到达树底。您甚至可以使用查找表通过蛮力解决此问题：只需列出所有董事会职位以及对每个职位的回应即可。
当游戏变得更大时（考虑跳棋，下棋，走棋），这不再是事实，而解决此问题的方法之一就是开发所谓的棋盘评估功能。这是一个占据棋盘位置并返回数字的功能，通常较高者对一个玩家更好，较低者对另一个更好。然后执行搜索到某个可接受的深度，并寻求最高的（例如）董事会评估职能。
这就引出了一个问题：我们如何提出董事会评估职能？最初，有人要求游戏专家为您开发这些功能。 Chellapilla和Fogel有一个很棒的paper，它类似于您要对检查程序执行的操作-他们使用神经网络来确定董事会评估职能，并且至关重要的是，这些神经网络被编码为基因组并得到了进化。然后将它们用于搜索深度为4的树中。最终结果对人类玩家非常有竞争力。
你应该读那篇论文。
我认为您尝试做的事情非常相似，除了您没有尝试将神经网络编码为染色体，而是尝试编写非常受限制的代数表达式，该表达式始终采用以下形式：
((((((((arg1 op1 arg2) op2 arg3) op3 arg4) op4 arg5) op5 arg6) op6 arg7) op7 arg8) op8 arg)
...然后您正在使用它的mod 9进行移动。
现在让我们谈谈遗传算法，遗传程序和新孩子的创建。进化技术的整体思想是将两个希望很好的解决方案的最佳属性结合起来，希望它们会变得更好，而不会陷入局部最大值。
通常，这是通过伴奏选择，交叉和变异来完成的。比赛选择意味着根据他们的健康状况选择父母。交叉是指将染色体分为两个通常连续的区域，并从一个亲本中取一个区域，从另一个亲本中取一个区域。 （为什么是连续的？因为
Holland's Schema Theorem）突变是指偶尔更改基因，以保持种群多样性。
现在让我们看看您在做什么：
1）您的评估板功能-染色体变成的功能，作用于评估板的位置-受到严格限制并且非常武断。将1、2和3分配为这些数字没有太多押韵或理由，但这可能没问题。更大的缺陷是您的功能是整个功能空间中极为有限的一部分。它们的长度始终相同，并且解析树始终看起来相同。
没有理由期望在此受限空间中会有有用的东西。所需要的是提出一种方案，该方案允许使用更通用的解析树集，包括交叉和变异方案。您应该查阅
John Koza的一些论文或书籍，以获取有关此主题的想法。
请注意，Chellapilla和Fogel也具有固定形式的功能，但它们的染色体明显大于其板表示形式。棋盘有32个可玩空间，每个空间可以有5个状态。但是他们的神经网络有大约85个节点，而染色体包含这些节点的连接权重-数百甚至是数千个值。
2）然后是整个模9的事情。我不明白你为什么要这么做。不要那样做您只是争先恐后地检查染色体中的任何信息。
3）您的新生孩子功能很差。即使作为遗传算法，您也应该将染色体分成两部分（在随机点处），并从一侧获取一个亲本的一部分，从另一侧获取另一亲本的另一部分。对于遗传编程（您正在执行的操作），有类似的策略可用于在解析树上进行交叉。参见Koza。
您必须包括突变，否则几乎可以肯定会得到次优的结果。
4a）如果您通过与有能力的AI进行比赛来评估健康度，那么您将意识到自己的染色体永远不会赢。他们会输，否则会平局。称职的AI永远不会输。此外，您的AI可能会一直流失，而最初的几代人可能都是同样（灾难性）的糟糕玩家。使自己摆脱困境并非不可能，但这会很困难。
4b）另一方面，如果像切拉皮拉（Chellapilla）和福格尔（Fogel）一样对自己玩AI，那么最好确定AI可以玩X或O。否则，您永远不会在所有。
5）最后，即使解决了所有这些问题，我也不相信这会取得很好的结果。请注意，跳棋示例搜索的深度为4，这在可能持续20或30个移动的跳棋游戏中并不是一个很大的视野。
TTT只能持续9步。
如果您不执行搜索树，而只是追求最高的评估板功能，那么您可能会得到一些有用的信息。你可能不会。我不确定。如果搜索深度为4，则最好跳至第9级的完整搜索，然后按常规进行。
个人中心
文章发布
退出
26
4
0
我是一名优秀的程序员,十分优秀！