我家小朋友最近迷上了井字棋，每天都要拉着大人玩两盘，这两天恰好有闲，写个井字棋程序练练手，同时看看能否提起小朋友对算法的兴趣。
时间有限，目前只完成了核心部分，即根据当前棋盘状态选择下一步最可能获胜的走法，用了基本的maxmin方法。只要用R的交互绘图功能给核心程序套上衣服就可以玩了。
rotate<- function(x, clockwise=T) {
if (clockwise) {
t( apply(x, 2, rev))
} else {
apply( t(x),2, rev)
}
}
checkstate=function(state){
cw=colSums(state)
rw=rowSums(state)
pdw=sum(diag(state))
sdw=sum(diag(rotate(state)))
w=c(cw,rw,pdw,sdw)
if(any(w==3))
return('x')#x:1 win
else if(any(w==-3))
return('o')#o:-1 win
if(!any(state==0))
return('e')#equal
else
return('u')#in progress
}
nextStates=function(state,player){
ids=which(state==0)
if(length(ids)==0)
return(0)#leaf node
post=array(dim=c(3,3,length(ids)))
if(player=='x')
v=1
else
v=-1
for (i in 1:length(ids)){
ns=state
ns[ids[i]]=v
post[,,i]=ns
}
return(post)
}
ceval=function(state){
cc=checkstate(state)
if(cc!='u'){#leaf node
return(c(switch(which(c('x','o','e')==cc),1,-1,0),1))
}
ns=nextStates(state,'x')
rs=apply(X = ns,MARGIN = 3,FUN = peval)
i=which.max(rs[1,])
v=rs[1,i]
return(c(v,i))
}
peval=function(state){
cc=checkstate(state)
if(cc!='u'){#leaf node
return(c(switch(which(c('x','o','e')==cc),1,-1,0),1))
}
ns=nextStates(state,'o')
rs=apply(X = ns,MARGIN = 3,FUN = ceval)
i=which.min(rs[1,])
v=rs[1,i]
return(c(v,i))
}
#state=matrix(data=c(1,-1,0,-1,1,1,1,-1,-1),3,3)
#state=matrix(0,3,3)
state=matrix(data=c(1,-1,0,0,-1,0,0,1,0),3,3)
v=ceval(state)
v
