数据结构与程序设计(王丽苹)13tic-ta.ppt
5/27/2023,数据结构与程序设计,1,数据结构与程序设计(13),王丽苹,5/27/2023,数据结构与程序设计,2,你可曾听说过“深蓝”？,1997年5月11日，IBM开发的“深蓝”击败了国际象棋冠军卡斯帕罗夫。,1980年他获得世界少年组冠军 1982年他并列夺得苏联冠军 1985年22岁的卡斯帕罗夫成为历史上最年轻的国 际象棋冠军积分是2849，这一分数是有史以来最高分。远远领先于第二位的克拉姆尼克的2770,卡氏何许人也？,5/27/2023,数据结构与程序设计,3,5/27/2023,数据结构与程序设计,4,游戏树（对弈树）,树根：是初始情况，对应于棋盘开始时候的格局。树叶：表示可能出现的结局。对弈的过程：就是沿着树根经过若干分支到达树叶的过程。,5/27/2023,数据结构与程序设计,5,Eight Game,假设：First为人 second为电脑,怎样帮助电脑选择最好的下棋方案？,5/27/2023,数据结构与程序设计,6,假设：以下为一棵博弈树，且各种结局的权值已经设置。,电脑,人,注意：各种结局的权值是根据电脑的角度来评估的。例如：电脑赢棋可能越大，得分越多，则权值越高,5/27/2023,数据结构与程序设计,7,用极大极小法为电脑找到最佳方案。,电脑,人,5/27/2023,数据结构与程序设计,8,5.4.2 极大极小法小结,(1)设博弈的双方中一方为S，另一方为F。然后为其中的一方(例如S)寻找一个最优行动方案。(2)为了找到当前的最优行动方案，需要对各个可能的方案所产生的后果进行比较,具体地说，就是要考虑每一方案实施后对方可能采取的所有行动，并计算可能的得分。(3)为计算得分，需要根据问题的特性信息定义一个估价函数，用来估算当前博弈树叶子节点的得分。此时估算出来的得分称为静态估值。,5/27/2023,数据结构与程序设计,9,(4)当叶子节点的估值计算出来后，再推算出父节点的得分，推算的方法是：对S所在的层，选其子节点中一个最有利的得分作为父节点的得分，这是为了使自己在可供选择的方案中选一个对自己最有利的方案；对F所在的层，选其子节点中对对方最不利的得分作为父节点的得分，这是为了立足于最坏的情况。这样计算出的父节点的得分称为倒推值。(5)如果一个行动方案能获得较大的倒推值，则它就是当前最好的行动方案。,5/27/2023,数据结构与程序设计,10,Tic-Tac-Toe（井子游戏）,目录Tic_Tac_Toe下例程,5/27/2023,数据结构与程序设计,11,TicTacToeGameWin,目录TicTacToeGameWin下例程,5/27/2023,数据结构与程序设计,12,练习，画出此时的博弈树,X：Person0：Computer,1,2,3,4,为方便画博弈树，设1，2，3，4为对当前空闲棋格的编号,电脑为第二个选手；人为第一个选手；,5/27/2023,数据结构与程序设计,13,。,1,2,3,4,2,2,2,1,1,1,3,3,3,3,3,4,输,4,4,4,4,输,4,2,输,输,3,2,输,平,4,平,3,输,4,平,1,输,3,平,1,假设各个叶子节点的权值为：(考虑到博弈树的最大深度为9)如果打平则为：0；如果第一个选手赢了：10-层数；/越大，越有利于第一个选手。如果第二个选手赢了：层数-10；/越小，越有利于第二个选手。,7,5,0,第二个选手,第一个选手,5/27/2023,数据结构与程序设计,14,棋盘的存储数据结构设计,井子游戏棋盘的大小为3*3。可以用二维数组来存放当前棋盘的信息。游戏开始前，棋盘为空，可设二维数组的各个元素值为0。第一个选手开始下棋，则将他的棋子所在的位置设置为1。第二个选手开始下棋，则将他的棋子所在的位置设置为2。,5/27/2023,数据结构与程序设计,15,棋盘的存储数据结构设计,0,0,0,0,1,1,1,2,2,当前棋盘在内存的存储,1,2,3,4,5/27/2023,数据结构与程序设计,16,确定电脑走法的算法描述,Look_ahead at game(棋盘);if 递归搜索结束 即搜索到最后一层或者已经分出胜负 返回该位置的评价。else 对当前每一种走法 依次尝试各种走法，从而产生新的棋盘，通过递归调用得到当前棋盘的评价。通过对各种走法的尝试，找到当前下棋者的最佳选项。并将该值返回。,5/27/2023,数据结构与程序设计,17,Tic-Tac-ToeClass Move,class Move public:Move();Move(int r,int c);int row;int col;,5/27/2023,数据结构与程序设计,18,Tic-Tac-ToeClass Move,Move:Move()/*Post:The Move is initialized to an illegal,default value.*/row=3;col=3;Move:Move(int r,int c)/*Post:The Move is initialized to the given coordinates.*/row=r;col=c;,5/27/2023,数据结构与程序设计,19,Tic-Tac-ToeClass Board,#includeMove.h#includeMyStack.cppclass Board public:Board();bool done()const;void print()const;void instructions()const;bool better(int value,int old_value)const;bool ValidStep(Move try_it)const;void play(Move try_it);int worst_case()const;int evaluate()const;int legal_moves(MyStack,5/27/2023,数据结构与程序设计,20,Tic-Tac-ToeClass Board,Board:Board()/*Post:TheBoard is initialized as empty.*/for(int i=0;i 3;i+)for(int j=0;j 3;j+)squaresij=0;moves_done=0;,5/27/2023,数据结构与程序设计,21,Tic-Tac-ToeClass Board,void Board:instructions()constcoutThis is a Tic-Tac-Toe game.Wait for computer going.endl;,5/27/2023,数据结构与程序设计,22,Tic-Tac-ToeClass Board,void Board:print()constfor(int i=0;i 3;i+)for(int j=0;j 3;j+)cout squaresij;cout endl;coutendl;,5/27/2023,数据结构与程序设计,23,Tic-Tac-ToeClass Board,bool Board:ValidStep(Move try_it)constif(squarestry_it.rowtry_it.col=0)return true;elsereturn false;,5/27/2023,数据结构与程序设计,24,Tic-Tac-ToeClass Board,void Board:play(Move try_it)/*Post:The Move try_it is played on theBoard.*/squarestry_it.rowtry_it.col=moves_done%2+1;moves_done+;,5/27/2023,数据结构与程序设计,25,Tic-Tac-ToeClass Board P206,int Board:the_winner()const/*Post:Return either a value of 0 for a position where neither player has won,a valueof 1 if the first player has won,or a value of 2 if the second player has won.*/int i;for(i=0;i 3;i+)if(squaresi0,5/27/2023,数据结构与程序设计,26,Tic-Tac-ToeClass Board,bool Board:done()const/*Post:Return true if the game is over;either because a player has already won orbecause all nine squares have been filled.*/return moves_done=9|the_winner()0;,5/27/2023,数据结构与程序设计,27,Tic-Tac-ToeClass Board P207,int Board:legal_moves(MyStack,5/27/2023,数据结构与程序设计,28,Tic-Tac-ToeClass Board,int Board:evaluate()const/*Post:Return either a value of 0 for a position where neither player has won,a positive value between 1 and 9 if the first player has won,or a negative value between-1 and-9 if the second player has won,*/int winner=the_winner();if(winner=1)return 10-moves_done;/for first player 1else if(winner=2)return moves_done-10;/for second player 2else return 0;,5/27/2023,数据结构与程序设计,29,Tic-Tac-ToeClass Board,bool Board:better(int value,int old_value)const/for second player 2if(moves_done%2)return valueold_value;,5/27/2023,数据结构与程序设计,30,Tic-Tac-ToeClass Board,int Board:worst_case()constif(moves_done%2)return 10;/for second player 2else return-10;/for first player 1,5/27/2023,数据结构与程序设计,31,int look_ahead(const Board,5/27/2023,数据结构与程序设计,32,Tic-Tac-ToeMain,void main()Board game;Move recommended;int x,y;int i=9;game.instructions();while(!game.done()coutx;couty;Move me(x,y);game.play(me);game.print();if(game.done()break;look_ahead(game,i-1,recommended);/for computer1game.play(recommended);coutComputer1:endl;game.print();i-;if(game.the_winner()=2)coutGame over with computer win.endl;else if(game.the_winner()=1)coutGame over with you win.endl;else coutGame over with a draw.endl;,5/27/2023,数据结构与程序设计,33,Tic-Tac-Toe,问题1：如何使电脑智能降低？问题2：如何改写成电脑对电脑的程序？问题3：如何改写成电脑先走的程序？问题4：如何检测人走棋合法性？,5/27/2023,数据结构与程序设计,34,改写成电脑对电脑的程序1,This is a Tic-Tac-Toe game.Wait for computer going.Computer1:0 0 0 0 0 0 0 0 1Computer2:0 0 0 0 2 0 0 0 1Computer1:0 0 0 0 2 0 0 1 1Computer2:0 0 0 0 2 0 2 1 1,5/27/2023,数据结构与程序设计,35,改写成电脑对电脑的程序2,Computer1:0 0 1 0 2 0 2 1 1Computer2:0 0 1 0 2 2 2 1 1Computer1:0 0 1 1 2 2 2 1 1Computer2:0 2 1 1 2 2 2 1 1Computer1:1 2 1 1 2 2 2 1 1Game over with a draw.,5/27/2023,数据结构与程序设计,36,上机作业,实现Tic-Tac-Toe程序。,
