- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
在我的方法 newminimax499 中,我有一个利用内存和 alpha beta 修剪的 minimax 算法。该方法通常适用于 3x3 游戏,但是当我玩 4x4 游戏时,我会得到奇怪的、意想不到的计算机位置选择。他仍然从不输,但他似乎并不是为了赢而比赛。为了说明这里的问题,我们使用 2 个 3x3 和 4x4 游戏的场景。首先是一个 3x3 游戏的场景,其中玩家是 X 并迈出第一步:
这还不错,事实上,这正是人们希望计算机执行的操作。现在来看一个 4x4 游戏的场景。同样,O 是计算机,X 启动:
如您所见,计算机只是将 Os 一个接一个地按系统顺序排列,只有在它有可能获胜时才打破该顺序来阻止 X。这是非常防守的打法,不像在 3x3 比赛中看到的那样。那么为什么该方法对于 3x3 和 4x4 表现不同?
代码如下:
//This method returns a 2 element int array containing the position of the best possible
//next move and the score it yields. Utilizes memoization and alpha beta
//pruning to achieve better performance.
public int[] newminimax499(int a, int b){
//int bestScore = (turn == 'O') ? +9 : -9; //X is minimizer, O is maximizer
int bestPos=-1;
int alpha= a;
int beta= b;
int currentScore;
//boardShow();
String stateString = "";
for (int i=0; i<state.length; i++)
stateString += state[i];
int[] oldAnswer = oldAnswers.get(stateString);
if (oldAnswer != null)
return oldAnswer;
if(isGameOver()!='N'){
int[] answer = {score(), bestPos};
oldAnswers.put (stateString, answer);
return answer;
}
else{
for(int x:getAvailableMoves()){
if(turn=='X'){ //X is minimizer
setX(x);
//System.out.println(stateID++);
currentScore = newminimax499(alpha, beta)[0];
revert(x);
if(currentScore<beta){
beta=currentScore;
bestPos=x;
}
if(alpha>=beta){
break;
}
}
else { //O is maximizer
setO(x);
//System.out.println(stateID++);
currentScore = newminimax499(alpha, beta)[0];
revert(x);
if(currentScore>alpha){
alpha=currentScore;
bestPos=x;
}
if(alpha>=beta){
break;
}
}
}
}
if(turn=='X'){
int[] answer = {beta, bestPos};
oldAnswers.put (stateString, answer);
return answer;
}
else {
int[] answer = {alpha, bestPos};
oldAnswers.put (stateString, answer);
return answer;
}
}
以下是你们运行代码所需的其他组件和补充方法。我的类 State2 中使用的字段和构造函数:
private char [] state; //Actual content of the board
private char turn; //Whose turn it is
private Map<String,int[]> oldAnswers; //Used for memoization. It saves every state along with the score it yielded which allows us to stop exploring the children of a certain node if a similar node's score has been previously calculated. The key is the board state(i.e OX------X for example), the int array is a 2 element array containing the score and position of last placed seed of the state.
private Map<Integer, int []> RowCol; //A mapping of positions from a board represented as a normal array to a board represented as a 2d array. For example: The position 0 maps to 0,0 on a 2d array board, 1 maps to 0,1 and so on.
private static int n; //Size of the board
private static int stateID; //An simple incrementer used to show number of recursive calls in the newminiax49 method.
private static int countX, countO; //Number of placed Xs and Os
private static int lastAdded; //Position of last placed seed
private char [][] DDState; //A 2d array representing the board. Contains the same values as state[]. Used for simplicity in functions that check the state of the board.
public State2(int n){
int a=0;
State2.n=n;
state=new char[n*n];
RowCol=new HashMap<Integer, int []>();
countX=0;
countO=0;
//Initializing the board with empty slots
for(int i = 0; i<state.length; i++){
state[i]='-';
}
//Mapping
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
RowCol.put(a, new int[]{i, j});
a++;
}
}
a=0;
DDState=new char[n][n];
//Initializing the 2d array with the values from state[](empty slots)
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
DDState[i][j]=state[a];
a++;
}
}
oldAnswers = new HashMap<String,int[]>();
}
补充方法:
getAvailableMoves,返回一个数组,其中包含棋盘上的空槽(即可能的下一步)。
public int[] getAvailableMoves(){
int count=0;
int i=0;
for(int j=0; j<state.length; j++){
if(state[j]=='-')
count++;
}
int [] availableSlots = new int[count];
for(int j=0; j<state.length; j++){
if(state[j]=='-')
availableSlots[i++]=j;
}
return availableSlots;
}
isGameOver2(),简单地检查棋盘的当前状态以判断游戏是否结束。返回一个字符 'X'、'O'、'D' 和 'N',分别代表 X 获胜、O 获胜、平局和未游戏结束。
public char isGameOver2(){
char turnOpp;
int count;
if(turn=='X'){
count=countO;
turnOpp='O';
}
else {
count=countX;
turnOpp='X';
}
if(count>=n){
for(int i=0; i<n; i++){
if(DDState[i][RowCol.get(lastAdded)[1]]!=turnOpp)
break;
if(i==(n-1)){
return turnOpp;
}
}
//Check row for win
for(int i=0; i<n; i++){
if(DDState[RowCol.get(lastAdded)[0]][i]!=turnOpp)
break;
if(i==(n-1)){
return turnOpp;
}
}
//Check diagonal for win
if(RowCol.get(lastAdded)[0] == RowCol.get(lastAdded)[1]){
//we're on a diagonal
for(int i = 0; i < n; i++){
if(DDState[i][i] != turnOpp)
break;
if(i == n-1){
return turnOpp;
}
}
}
//check anti diagonal
for(int i = 0; i<n; i++){
if(DDState[i][(n-1)-i] != turnOpp)
break;
if(i == n-1){
return turnOpp;
}
}
//check for draw
if((countX+countO)==(n*n))
return 'D';
}
return 'N';
}
boardShow,返回棋盘当前状态的矩阵显示:
public void boardShow(){
if(n==3){
System.out.println(stateID);
for(int i=0; i<=6;i+=3)
System.out.println("["+state[i]+"]"+" ["+state[i+1]+"]"+" ["+state[i+2]+"]");
System.out.println("***********");
}
else {
System.out.println(stateID);
for(int i=0; i<=12;i+=4)
System.out.println("["+state[i]+"]"+" ["+state[i+1]+"]"+" ["+state[i+2]+"]"+" ["+state[i+3]+"]");
System.out.println("***********");
}
}
score,是一个简单的评估函数,O 获胜时返回 +10,X 获胜时返回 -10,平局返回 0:
public int score(){
if(isGameOver2()=='X')
return -10;
else if(isGameOver2()=='O')
return +10;
else
return 0;
}
播种机:
//Sets an X at a certain location and updates the turn, countX and lastAdded variables
public void setX(int i){
state[i]='X';
DDState[RowCol.get(i)[0]][RowCol.get(i)[1]]='X';
turn='O';
countX++;
lastAdded=i;
}
//Sets an O at a certain location and updates the turn, countO and lastAdded variables
public void setO(int i){
state[i]='O';
DDState[RowCol.get(i)[0]][RowCol.get(i)[1]]='O';
turn='X';
countO++;
lastAdded=i;
}
还原,简单地还原移动。例如,如果一个 X 被放置在位置 0 revert(0) 设置一个 '-' 在它的位置并更新由 setX 更改的变量:
public void revert(int i){
state[i]='-';
DDState[RowCol.get(i)[0]][RowCol.get(i)[1]]='-';
if(turn=='X'){
turn = 'O';
countO--;
}
else {
turn = 'X';
countX--;
}
}
main 方法可能是这样的:
public static void main(String[] args) {
State2 s=new State2(4);
int [] results=new int[2];
s.setX(0);
long startTime = System.currentTimeMillis();
results=s.newminimax499(Integer.MIN_VALUE,Integer.MAX_VALUE);
long endTime = System.currentTimeMillis();
System.out.println("Score: "+results[0]+" Position: "+ results[1]);
System.out.println("Run time: " + (endTime-startTime));
s.boardShow();
}
最佳答案
我不相信这里有一个错误——如果 O 在较早的位置之一,它会 fork ,而如果它在中间,它会强制平局。大概 4x4 游戏更难赢/输,所以计算机无动于衷地选择了第一个开放的方格。
下面,1
表示O的强制响应,2
表示X的 fork 走法,?
表示可能的获胜位置。
X|O|
-+-+-
2|X|?
-+-+-
?| |1
X| |O
-+-+-
X|2|?
-+-+-
1| |?
X|2|?
-+-+-
O|X|
-+-+-
|?|1
关于java - TicTacToe minimax 算法在 4x4 游戏中返回意外结果,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32119093/
滑动窗口限流 滑动窗口限流是一种常用的限流算法,通过维护一个固定大小的窗口,在单位时间内允许通过的请求次数不超过设定的阈值。具体来说,滑动窗口限流算法通常包括以下几个步骤: 初始化:设置窗口
表达式求值:一个只有+,-,*,/的表达式,没有括号 一种神奇的做法:使用数组存储数字和运算符,先把优先级别高的乘法和除法计算出来,再计算加法和减法 int GetVal(string s){
【算法】前缀和 题目 先来看一道题目:(前缀和模板题) 已知一个数组A[],现在想要求出其中一些数字的和。 输入格式: 先是整数N,M,表示一共有N个数字,有M组询问 接下来有N个数,表示A[1]..
1.前序遍历 根-左-右的顺序遍历,可以使用递归 void preOrder(Node *u){ if(u==NULL)return; printf("%d ",u->val);
先看题目 物品不能分隔,必须全部取走或者留下,因此称为01背包 (只有不取和取两种状态) 看第一个样例 我们需要把4个物品装入一个容量为10的背包 我们可以简化问题,从小到大入手分析 weightva
我最近在一次采访中遇到了这个问题: 给出以下矩阵: [[ R R R R R R], [ R B B B R R], [ B R R R B B], [ R B R R R R]] 找出是否有任
我正在尝试通过 C++ 算法从我的 outlook 帐户发送一封电子邮件,该帐户已经打开并记录,但真的不知道从哪里开始(对于 outlook-c++ 集成),谷歌也没有帮我这么多。任何提示将不胜感激。
我发现自己像这样编写了一个手工制作的 while 循环: std::list foo; // In my case, map, but list is simpler auto currentPoin
我有用于检测正方形的 opencv 代码。现在我想在检测正方形后,代码运行另一个命令。 代码如下: #include "cv.h" #include "cxcore.h" #include "high
我正在尝试模拟一个 matlab 函数“imfill”来填充二进制图像(1 和 0 的二维矩阵)。 我想在矩阵中指定一个起点,并像 imfill 的 4 连接版本那样进行洪水填充。 这是否已经存在于
我正在阅读 Robert Sedgewick 的《C++ 算法》。 Basic recurrences section it was mentioned as 这种循环出现在循环输入以消除一个项目的递
我正在思考如何在我的日历中生成代表任务的数据结构(仅供我个人使用)。我有来自 DBMS 的按日期排序的任务记录,如下所示: 买牛奶(18.1.2013) 任务日期 (2013-01-15) 任务标签(
输入一个未排序的整数数组A[1..n]只有 O(d) :(d int) 计算每个元素在单次迭代中出现在列表中的次数。 map 是balanced Binary Search Tree基于确保 O(nl
我遇到了一个问题,但我仍然不知道如何解决。我想出了如何用蛮力的方式来做到这一点,但是当有成千上万的元素时它就不起作用了。 Problem: Say you are given the followin
我有一个列表列表。 L1= [[...][...][.......].......]如果我在展平列表后获取所有元素并从中提取唯一值,那么我会得到一个列表 L2。我有另一个列表 L3,它是 L2 的某个
我们得到二维矩阵数组(假设长度为 i 和宽度为 j)和整数 k我们必须找到包含这个或更大总和的最小矩形的大小F.e k=7 4 1 1 1 1 1 4 4 Anwser是2,因为4+4=8 >= 7,
我实行 3 类倒制,每周换类。顺序为早类 (m)、晚类 (n) 和下午类 (a)。我固定的订单,即它永远不会改变,即使那个星期不工作也是如此。 我创建了一个函数来获取 ISO 周数。当我给它一个日期时
假设我们有一个输入,它是一个元素列表: {a, b, c, d, e, f} 还有不同的集合,可能包含这些元素的任意组合,也可能包含不在输入列表中的其他元素: A:{e,f} B:{d,f,a} C:
我有一个子集算法,可以找到给定集合的所有子集。原始集合的问题在于它是一个不断增长的集合,如果向其中添加元素,我需要再次重新计算它的子集。 有没有一种方法可以优化子集算法,该算法可以从最后一个计算点重新
我有一个包含 100 万个符号及其预期频率的表格。 我想通过为每个符号分配一个唯一(且前缀唯一)的可变长度位串来压缩这些符号的序列,然后将它们连接在一起以表示序列。 我想分配这些位串,以使编码序列的预
我是一名优秀的程序员,十分优秀!