| 51testing 51testing (51Testing)當(dāng)前離線 UID 2? 帖子 1376? 精華 25? 積分 13794? 綜合技術(shù)指數(shù) 13790 ? 生活情趣指數(shù) 4 ? 鮮花 15 ? 雞蛋 3 ? 閱讀權(quán)限 1? 在線時(shí)間 871 小時(shí)? 注冊時(shí)間 2004-3-17? 最后登錄 2011-9-2? 51Testing 51Testing Team | 2# 發(fā)表于 2007-11-16 17:15 | 只看該作者 推論式思考 相信曾經(jīng)接觸過電腦語言課程，或是自習(xí)過相關(guān)書籍的朋友們，都曾曾經(jīng)聽過一個(gè)著名的程序，那就是井字游戲。用井字游戲作為討論AI的入門教材，我個(gè)人覺得是最適當(dāng)?shù)睦印；蛟S有人還不知道井字游戲怎么玩。只要任何一方在三乘三的方格中先先成一線便勝利了。我們在前面談過的規(guī)則導(dǎo)向，在這里也可以派得上用場。
if任何一線已有我方兩子&&另外一格仍空//我方即將成一線嗎
結(jié)果 = 該空格
if任何一線已有敵方兩子&&另外一格仍空//防止敵方作成一線
結(jié)果 = 該空格
if任何一線已有我方一子&&另外兩格仍空//作成兩子
結(jié)果 = 該空格
有一次我在某本電腦書上，同樣地也看到某些以井字游戲?yàn)榻榻B的范例。不同的是，我?guī)缀蹩床坏饺魏我?guī)則導(dǎo)向的影子。但在仔細(xì)分析該程序碼后，我得到了極大的啟發(fā)，原來AI是可以不用這么多規(guī)則來制作的。它用的方法正是在電腦AI課程中重要的概念：極大極小法。我在這里只說明這法則的概念。繼續(xù)以井字游戲?yàn)槔?#xff0c;電腦先在某處下子，接著會以假設(shè)的方式，替對方下子，當(dāng)然，必須假設(shè)對方下的是最佳位置，否則一切則毫無意義。在假設(shè)對方下子的過程中，自然又需要假設(shè)我方的下一步回應(yīng)，如此一來一往，直到下完整局游戲?yàn)橹埂?底下是節(jié)錄書中的程序片段：
bestMove(int p, int*v)
{ int i;
int lastTie;
int lastMove;
int subV;
/*First, check for a tie*/
if (isTie()) {
*v=0;
return(0);
};
/*If not a tie, try each potential move*/
for (*v=-1, lastTie=lastMove=-1,i=0;i<9;i++)
{
/*If this isn't a possible, skip it*/
if (board!=0) continue;
/* Make the move. */
lastMove=i;
board=p;
/* Did it win? */
if (hasWon(p)) *v=1;
else{
/*If not, find out how good the other side can do*/
bestMove(-p,&subV);
/* If they can only lose, this is still a win.*/
if (subV==-1) *v=1;
/* Or, if it's a tie, remember it. */
else if (subV==0){
*v=0;
lastTie=i;
};
};
/* Take back the move. */
board=0;
/*If we found a win, return immediately
(can't do any better than that)*/
if (*v==1) return(i);
/*If we didn't find any wins, return a tie move.*/
if (*v==0) return(lastTie);
/*If there weren't even any ties, return a loosing move.*/
else return(lastMove);
};
國外的一些論壇曾舉行過256字節(jié)的游戲設(shè)計(jì)比賽。作品非常多，其中有一件作品正巧也是井字游戲。作者用區(qū)區(qū)兩百多行就寫了與上述程序演算方式完全相同的作品，可見功力確實(shí)了的。另外，我也很希望類似的活動能在國內(nèi)推展起來。對了，在這樣的比賽條件限制下，除了匯編語言外，幾乎沒有其它的選擇了。 .386c
code segment byte public use16
assume cs:code, ds:code
org 100h
tictac proc far
start:
push cs
pop ds
mov ax,0B800h ; 清除屏幕
mov es,ax ;
xor di,di ;
mov cx,7D0h ;
mov ax,0F20h ;
rep stosw ;
xor cx,cx ;
mov dl,5
loc_1:
call printBoard
loc_2:
mov ah,8 ; 等待按鍵
int 21h
movzx bx,al
sub bl,31h ; 如果不是1..9
jc loc_2 ; 則重新輸入
cmp bl,8
ja loc_2
cmp data_1[bx],al
jne loc_2
mov byte ptr data_1[bx],'x'
dec dl
jz short loc_3
mov al,'o'
call bestMove
mov [si],al
call isWin ; 判斷是否已取得勝利
jnc loc_1
loc_3:
call printBoard
mov ax,4C00h
int 21h
data_1 db '12'
data_2 db '3456789'
data_3 db 0
tictac endp
printBoard proc near
mov si,offset data_1
mov di,548h
mov cl,3
locloop_4:
movsb
add di,5
movsb
add di,5
movsb
add di,133h
loop locloop_4
retn
printBoard endp
isWin proc near
mov bx,1
mov bp,3
call sub_3 ; 檢查橫向是否完成
inc bx
inc bx
dec bp
dec bp
call sub_3 ; 檢查縱向是否完成
call sub_4 ; 檢查斜向是否完成
clc
retn
isWin endp
loc_5:
stc
retn
sub_3 proc near
mov ah,3
mov si,offset data_1
loc_6:
mov di,si
call sub_5
add si,bp
dec ah
jnz loc_6
retn
sub_3 endp
sub_4 proc near
mov di,offset data_1
inc bx
call sub_5
mov di,offset data_2
dec bx
dec bx
call sub_5
retn
sub_4 endp
sub_5 proc near
mov cl,3
locloop_7:
cmp [di],al
jne short loc_ret_8
add di,bx
loop locloop_7
add sp,4
jmp short loc_5
loc_ret_8:
retn
sub_5 endp
bestMove proc near
mov bx,31FEh
mov cl,9
mov di,offset data_1
locloop_9:
cmp [di],bh ; #empty?
jne short loc_12 ; #no, skip
mov [di],al
pusha
call isWin ; #CY: Win
popa ;
jnc short loc_10 ;
mov bl,1
mov si,di
mov [di],bh
retn
loc_10:
pusha
xor al,17h ; good! toggle 'o' / 'x'
call bestMove
mov data_3,bl
popa
mov ah,data_3
neg ah
cmp ah,bl
jle short loc_11
mov bl,ah
mov si,di
loc_11:
mov [di],bh
loc_12:
inc bh
inc di
loop locloop_9
cmp bl,0FEh
jne short loc_ret_13
xor bl,bl
loc_ret_13:
retn
bestMove endp
code ends
end start
|
|
