高中信息技术粤教版选修5 人工智能初步第四章问题求解4.4 求解博弈问题优质课ppt课件

展开

这是一份高中信息技术粤教版选修5 人工智能初步第四章问题求解4.4 求解博弈问题优质课ppt课件，共12页。PPT课件主要包含了博弈问题，井字棋问题等内容，欢迎下载使用。

谁来说说田忌赛马的故事？
“田忌赛马”就是典型的博弈问题。博弈（Game Playing)是对策性游戏，例如，跳棋、象棋、围棋、桥牌都是博弈。人工智能发展的早期就开始了对博弈问题的研究。人工智能研究博弈的主要目的不仅是为了让计算机与人进行下棋、打牌，更进一步的是通过对博弈问题的研究来促进人工智能技术在规划、决策等方面的应用；同时，通过对博弈过程的模拟，以促进人工智能技术的研究和发展。
井字棋的游戏规则为：（1）井字棋的棋盘上有三行三列，两个棋手轮流摆棋子。（2）如果我们用“ ”代表棋手甲的棋子，用“×”代表棋手乙的棋子，每人每次摆一个棋子，先形成三子一线者获胜，如图所示。
假设甲、乙双方釆用博弈策略的启发函数为：若摆的棋子能增加自己取胜的机会，得1分；若摆的棋子能减少对方取胜的机会，得1分；若摆的棋子能增加自己取胜的机会且能减少对方取胜的机会，得2分。例如：如图所示，如果甲方在第三行第二列摆子，造成取胜机会，启发函数值为1。
如图所示，如果乙方在第三行第三列摆子，造成取胜机会，且能减小对方取胜的机会，启发函数值为2。
如图所示，如果乙方在第一行第二列摆子，减小对方取胜的机会，启发函数值为1。
假如，乙先走，右图画出了甲、乙双方对弈示意图的一部分，树的奇数层为乙方摆棋子后的可能状态，树的偶数层为甲方摆棋子后的可能状态。
在井字棋博弈问题中，如果把上图看成是一棵对应于井字棋各个状态而构成的状态树，那么，求解博弈问题的方法是：把根节点作为棋盘的初始状态，把取胜的棋盘状态作为棋盘的目标状态，用启发函数指导搜索，找寻从棋盘的初始状态到棋盘的目标状态的路径。上述对弈井字棋时，我们把得分值作为启发函数值，摆棋子时，启发函数值应尽可能取得最大，以求多得分，从而增加取胜机会。二人对弈问题实际情况变化复杂，需运用比较多的知识与经验，因此，启发函数也比较复杂。这里，我们只是讨论了一种简单的情况，来说明用启发函数指导对弈策略的意义。