益智遊戲「L棋(LGAME)」之電腦解法及分析國立臺灣師範大學.doc

《益智遊戲「L棋(LGAME)」之電腦解法及分析國立臺灣師範大學.doc》由会员分享，可在线阅读，更多相关《益智遊戲「L棋(LGAME)」之電腦解法及分析國立臺灣師範大學.doc（13页珍藏版）》请在三一办公上搜索。

1、益智遊戲棋(L-Game)之電腦解法及分析蔡明原、林順喜國立臺灣師範大學資訊教育系摘要由英國劍橋大學Edward De Bono教授所發明的L-Game，是一個兩人對奕的有趣遊戲，本文嘗試利用電腦來分析這個遊戲是否存在必贏的策略？先下手的一方是否有占便宜？是否存在纏鬥最久的盤面？經過我們的分析，發現此遊戲雙方總共有36736種盤面(每一方18368種)，其中有240種輸的盤面，而且先後下棋的雙方擁有一樣多對應盤面，沒有任何一方占便宜，而且並不存在必贏的方法，下棋的雙方如果都沒有下錯，依一定的下棋策略，這個遊戲就不斷進行下去，也就是不斷地纏鬥下去。最後我們將研究的成果設計成CGI程式，放在網頁上

2、供大家與我們的程式下棋。一、 緒論1. 棋(L-Game)介紹：我們偶然在網際網路上尋找一些有趣的的遊戲網站時，發現了一個GamePuzzle的網站， De Bono (黎波諾) 教授所設計的遊戲。這個遊戲的玩法如下：(圖一)(圖二)說明：(圖一)為44棋盤，上置兩個L形棋子及兩顆圓形棋子，其玩法為一人一個L形棋子，決定先後手後，一方拿起他自己的L形棋子，可任意翻轉後放回棋盤，但不可放回原位，然後可以移動一顆圓形棋子或者不移，如此輪流移動，直到有一方拿起他自己的L形棋子後無處可放則為負方。舉例來說，(圖二)持黑色的一方沒法再動了，就輸了這場棋賽。查詢相關資料，發現民國74年11月27日的報紙上

3、有一則有關L棋的報導：三個師大附中的學生寫了一個以人工智慧方法設計的程式來玩L棋，程式從與人的對戰中學習，不重複錯誤的下棋盤面，並建立一個資料庫儲存盤面，而在下棋時，選擇過去下棋經驗中離失敗最遠的盤面來下，這樣訓練的結果，他們的程式越來越會下L棋，而且總有一天這個有關L棋的資料庫會學習到所有的盤面與相對應的下棋方法，在當時他們能以高中生的身份踏入人工智慧的研究，實在不容易，可惜他們並未證明L棋是否存在必贏的下棋方法？先下L棋的一方是否擁有較多的勝算？所以我們希望能以不同的方式來研究L棋。後來我們在圖書館找到了水牛出版社於民國七十七年所出版的水平思考五日訓練法一書，這是黎波諾教授出版的書，敘述面

4、對一些問題時，我們應該如何以水平思考的方式去分析問題，其中第三個單元就是以L棋為例來分析互相競爭下最容易發生的問題及如何思考下棋的策略。黎波諾教授指出，與其他需要集中精神去移動許多棋子的遊戲比起來，L棋是一個構造簡單卻需要仔細思考的遊戲，L棋有五個特點：(1) 每個人只有一顆子(L形棋子)(2) 棋盤不大(16格)(3) 規則簡單容易記(4) 下棋需要仔細的思考(因為棋子的移動方法很多)(5) L-Game不像井字遊戲，受到盤面的限制，當雙方把所有的格子填滿，遊戲就結束，而L-Game的棋子不會增減，必定要有一方的L形棋子不能移動，才會結束。(6) 勝負無限制，先下手或後下手無關勝負。雖然黎波

5、諾教授對於他所設計的遊戲給予很高的評價，但是從文獻中我們並沒有發現黎波諾教授如何證明這個遊戲真的就如他的分析，沒有好的方法致勝？也沒有說明為何當初要要設計那樣的啟始盤面，而且文中有一段黎波諾教授指出：下棋的一方有50種以上下棋的方法，對方也有50種以上對應的方法，要一一檢討優劣是困難的，如果要預先考慮個兩三手，既使是巨大的電子計算機也不可能做到。真的是如此嗎？所以我們希望以程式來證明我們能以電腦來分析此棋戲，而且能找出最佳的下棋方法。2. 人腦玩此遊戲和電腦玩有何不同之處？以人腦來玩這樣的對奕遊戲，除了要考慮自己的攻守策略外，還要考慮對方的可能採取的攻守策略，但是人常常會考慮得不夠周延，而且對

6、於重複的盤面不能有效的記錄，所以不能歸納出有效的下棋策略，常常都是從不斷的練習中減少自己犯錯的機會，但是也不能保證自己一定不會再出錯。而這個遊戲中，由於盤面是正方形的，雙方的棋子數目及形狀也具有對稱性，所以一個盤面有八種對稱的相同盤面，對於人腦的記憶是蠻大的負擔。此外，人類在下棋時，常常採取所謂的經驗法則，就像之前師大附中的學生所設計的人工智慧程式一樣，從不斷的下棋經驗中去找自己最佳的下棋策略，但是經驗未必代表就是最佳解，可能只是還沒失敗過而已。如果我們要讓電腦來解這樣的對奕遊戲，和人腦最大的不同，就是電腦能有效地記錄所走過的盤面，並且能從展開Game-tree的過程中尋找最佳的對應盤面，而且

7、能判斷盤面的對稱性，不過這樣的假設前提是要有一個好的方法去記錄盤面及分析盤面，否則只是浪費大量的記憶體及時間。此外，電腦在面對許多可選擇的盤面時，可以用機率的方式計算每一個可以走的盤面有多少勝利的機率，尋找最佳的盤面。另一方面由於電腦可以建構Game-tree窮舉所有的盤面，所以我們也能透過分析Game-tree的勝負分佈來找出好的下棋策略，幫助往後人們在玩這樣的棋類時，有更明確的判斷依據。而這個研究最後的目的，我們希望能讓我們的程式在與人玩L-Game的時候，能立於不敗的情況。二、 電腦解題之演算法面對這個遊戲，如果要讓電腦解題，第一步就是要有效的記錄盤面，我們設計以下的方法 (x1,y1,

8、dir1),(x2,y2,dir2),(n1,n2),who來表示，其中x1、y1、dir1、x2、y2、dir2都是0到3的整數，n1、n2是0到6的整數，who是0或1，所以一個盤面占用19bits來記錄。雖然盤面只有4*4，但是每一個L形的棋子有八個可能的形狀(圖三)，但是在盤面的一個位置上不可能八種形狀都能放入，分析的結果發現如果以L形突出的那一點(x,y)為記錄點，可能的擺放方式剛好是上(dir=0)、下(dir=1)、左(dir=2)、右(dir=3)四種可能性。而兩個中立的圓形棋子的記錄方法如果以一個二維的座標(16個可能位置)來記錄，兩顆棋子就可能有8*15種組合，其實當兩個L

9、形的棋子放好時，盤面上只剩8個空位，兩個圓形棋子只可能有4*7種排列方式，所以我們只要記錄這兩個圓形棋子之前各別的空白格子數n1及n2，便可以推算它在盤面中的位置，而且可以節省記錄空間。最後加上一個bit(who)記錄下一步該那一方下手，因此記錄一個盤面只需要19個bit的空間。(圖三)L形棋子8種可能形狀yx01230123(圖四)以上方(圖四)的盤面為例，這樣的盤面記錄為(x1,y1,dir1),(x2,y2,dir2),(n1,n2),who =(2,1,0),(0,1,3),(1,5),0，(2,1,0)是指灰色的L形突出來的那一點在座標(x1,y1) =(2,1)，其它三格在它上方，

10、所以記錄為dur1=0，同樣的，黑色的L形突出的那一點在(x2,y2) =(0,1)，其它三格在它的右方，記錄為dir2=3，而兩顆圓形的棋子，(3,1)的那一顆，之前只有(3,0)這一個空白，所以記錄為1，(2,3)的那一顆之前有五個空白，所以記錄為5，最後的who=0表示下一步該持灰色L棋子的一方下手。雖然19個bit的記錄空間已經算滿小的，但是還是需要3*219 bytes(1536K bytes)的記憶體空間(因為每一個盤面要3個bytes來做pointer)，以前16位元的DOS作業系統，在64K的限制之下，記憶體配置不可能達到1536K，所以我們整個程式是在32位元的作業系統下執行

11、Borland C+ Builder 3.0。完成了盤面記錄的設計後，便讓程式去產生Game-tree，並把雙方的所有可能盤面及輸贏盤面記錄下來，並從Game-tree的追蹤將每一個盤面的最佳對應盤面找出，並尋找此遊戲是否存在最佳的下棋策略及防守策略。第二個需要克服的問題，就是Game-Tree的記錄，因為一個盤面平均有50個以上的對應盤面(最少13個，最多221個)，所以我們在設計Game-Tree時應該把Child node指向Parent node。以L-Game的啟始盤面為例，共有65個對應盤面，所以這65個盤面都指向啟始盤面。我們把啟始盤面的編號設成(Node 0)其盤面記錄為(1,

12、0,3),(2,3,2),(0,6),0，它沒有Parent，所以指向-1，而它之下的65個Node，分別編號為(Node 1)(Node 65)，而他們的指標就指向(Node 0)。當展開的過程中發現該Node(例如圖五的Node 210)經程式判斷為不能再動的盤面，就記錄不能動的一方為輸。 (圖五)Game-Tree的架構圖Node 9298(2,0,3),(2,2,0),(1,5),03 (灰色輸)Node 210(2,0,3),(3,2,2),(1,5),1 0(2,0,3),(2,3,2),(0,0),1 0(2,0,3),(2,3,2),(1,6),10(2,0,3),(2,3,2

13、),(0,6),1 0Node 65Node 3Node 2Node 1(1,0,3),(2,3,2),(0,6),0 -1Node 0在Game-Tree展開的過程中，會有重覆的盤面出現，對於這樣的盤面，我們就不再展開它。除此之外，我們還需要一個陣列把所有輸的盤面(就是找不到下一步的盤面，以下叫這些輸的Node是LoseNode)記下來。接下來，我們要用倒推方式找出LoseNode所有可能的前一步盤面，前一步的盤面不一定是上圖中LoseNode的Parent node，舉例而言，上圖中Node 210是灰色方的一個LoseNode，而Node 3是它的Parent Node，但Node 21

14、0倒推回去的前一步有24個之多，上圖Node 9298就是一個可能是Node 210的上一步。這24個Node(以下我們叫這樣的Node是WinNode)，表示在下棋的過程中如果有機會到達這一盤面，就應該下讓對方輸的盤面來讓自己贏。而這樣的WinNode的前一步可能的Node(以下我們叫這樣的Node是GeneralNode)，GeneralNode在選擇最佳的的下一步時，一定不能考慮走到這些WinNode，才不會輸。所有的Node，除了LoseNode及WinNode之外，都是屬於GeneralNode，這些GeneralNode，可以走的下一盤面可能不只一個，如何從這些可以走的盤面找一個對

15、自己最佳的盤面，我們就必須分析可以走的盤面之致勝機率來下決定，致勝機率的算法待會兒再介紹。依這樣的方法，我們可以把原來Game-Tree上的每一個Node找到最好的下一步，加以記錄。請注意，這邊所說的LoseNode、WinNode、GeneralNode，還必須分辨是屬於哪一方。三個之間的在Game-Tree中的關係是LoseNode(A方)指向WinNode(B方)指向GeneralNode(A方)。三、 程式執行結果與分析我們程式的執行環境，是在Pentium MMX-233的主機，64MB SDRAM，Win98作業系統下，程式語言使用Borland C+ Builder 3.0。程式

16、第一部份是架構Game-Tree，展開所有的盤面並找出所有的LoseNode。第二部份將LoseNode以倒推方式標出所有的WinNode。第三部份找出特別的GeneralNode(下面文中會介紹為何特別)，並將Game-Tree重新整理。第四部份將所有Node的最佳下一步找出，並輸出至檔案，整個程式執行時間大概兩分鐘。以下用問答的方式說明程式執行結果與分析。1. L棋有多少個不重覆不對稱的盤面?我們以程式窮舉了Game-Tree下所有的盤面，發現總共有36736個Node，雙方各擁有18368種可能但不重覆的盤面，其中有6144種盤面是必贏(WinNode)，120種盤面必輸(LoseNod

17、e)，先下手及後下手的雙方都擁有一樣多的對應盤面，這點證實了黎波諾教授所說的L棋的特性：勝負無限制。也就是先下手或後下手並無差別。而雙方加起來所有的盤面只有36736(接近215)種可能，遠比219還小，這表示之前我們對於盤面的記錄方式仍有改進的空間。而這些盤面具有對稱性，所以如果我們把對稱的情況扣除(每個盤面有8個對稱情況)，則L棋的雙方有2296 種不重覆不對稱的盤面，其中有768個WinNode、15個LoseNode。2. Game-Tree的每一個Node，擁有多少個Child Node?每一個盤面，如果可以找到一個L形棋子可以放的位子，其它兩個圓形棋子就有13種可能的擺法(兩顆都不

18、動1種，動第一顆圓形棋子的有6種，動第二顆的有6種)，也就是說，每一個盤面之下的對應盤面必定是13的倍數。我們統計的結果發現一個Node最多可以擁有221個Child Node。Child Node個數統計0個13個26個39個52個65個78個91個104個24014402400288048803456392030722016117個130個143個156個169個182個195個208個221個32003696153612488964805120864總計36736個盤面，平均1個Node有88.89個Child NodeChild Node中WinNode個數統計0個13個26個39個5

19、2個65個78個91個104個0032964648488009281040117個130個143個156個169個182個195個208個221個1216204813127848804645120864總計12288個(雙方各6144個)如果我們再加以分析這些Node，其中擁有169個以上Child Node的盤面，他們的幾乎都是WinNode(195個以上的就必定是)，因為他們的Child Node之中必定擁有讓對方輸的LoseNode。所以當我們在與對手下L棋時，如果發現自己的L形棋子有13種以上的擺法時(13*13=169)，表示我們要贏了，千萬別放過對方唷。3. 下L棋有沒有必勝的策略

20、？L-Game並沒有必勝的策略，但是只要依循下面的幾個規則，便可以與對手繼續纏鬥下去，直到有一方露出破綻，不小心走到對方的WinNode，而輸了遊戲。我們從Game-Tree分析出四個玩L棋的策略：(1) L形棋子盡量不要放在棋盤的角落(2) 棋子盡量不要放在對稱的位子(3) 圓形棋子要和自己的L形棋子接觸(4) 要把自己的L形棋子放在對方的直角部份內側但是這四個下棋策略，還需要彼此配合，才能做好防守的工作，例如：不把自己L形棋子放在棋盤的角落之外，還要注意自己L形棋子的直角內側不要讓對方有機會卡死自己，才不會反而輸了。換句話說，不要輕視圓形棋子的位子，它很可能是救你一命的大功臣唷，以下我們舉

21、個例子來說明：(圖七)是比賽中一個盤面，輪到灰色下手，(圖七B)、(圖七C)、(圖七D)是其中三個對應盤面，其中(圖七C)是把灰色L形棋子放在角落，而(圖七B)、(圖七D)是把灰色L形棋子遠離角落，但是其中(圖七D)是最差的方法，因為雖然它沒放在角落，但是他讓別人可以放到他的直角內側，造成(圖七E)，所以輸了，而其他兩種還不會馬上輸。(A)(E)(B)(C)(D)(圖七)4. LoseNode擁有什麼樣的特性？有沒有辦法不走到對方的WinNode？當我們把盤面的對稱性扣除，發現15個(1208=15)必輸的盤面(LoseNode)之中有12個盤面，輸的一方把它的L形棋子放在棋盤的角落，但是有三

22、個盤面並非如此，所以L形棋子盡量不要放在棋盤的角落只是勝算較大，仍要移動圓形棋子來配合保護自己。以下將這15種必輸盤面列出(持左上角灰色L形棋子的一方輸)不在角落不在角落不在角落5. GeneralNode應該怎麼計算致勝機率才容易贏？由上述的LoseNode(A方)-WinNode(B方)-GeneralNode(A方)的關係中我們知道，在遊戲中任一個GeneralNode(A方)的下一步，必定包含一些WinNode(B方)和一些GeneralNode(B方)，我們當然不能選擇WinNode(B方)來當自己(A方)的下一步，所以我們要分析比較其它剩下的GeneralNode(B方)的優缺點來

23、選擇。而這些GeneralNode(B方)，他們的下一步的選擇中也必定含有一些WinNode(A方)和一些GeneralNode(A方)，如果WinNode(A方)的個數比GeneralNode(A方)的個數多，表示如果剛才我們(A方)選擇了這個GeneralNode(B方)，B方的下一步如果不小心，就很容易選錯步，選到WinNode(A方)，我們(A方)就贏了 (圖八)以樹狀圖來表示(Gnode=GeneralNode、Wnode=WinNode)Gnode1(A方)Gnode1 Gnode2 Wnode1 Wnode2 Gnode3(方) (方) (方) (方) (方)Gnode2 Gno

24、de3 Wnode1 Wnode2 Gnode4 Wnode3 Wnode4(方) (方) (方) (方) (方) (方) (方)如果我們是A方，處在Gnode1(A方)，我們有Gnode1(B方)、Gnode2(B方、Gnode3(B方) 、Wnode1(B方)、Wnode2(B方)五條路，我們一定不會去選Wnode1(B方)和Wnode2(B方)讓自己輸，所以我們要從其它三條路來比較優劣，其中Gnode1(B方)之下有四條路，而Gnode3(B方)之下有三條路，比較起來，我們(A方)選擇Gnode3(B方)會比較有利，因為我們選了Gnode3(B方)，對方有三分之二的機會走進Wnode3(

25、A方)或Wnode4(A方)，所以Gnode1(B方)的致勝機率是50%，而Gnode3(B方)有66%。依這樣的方法我們可以為所有的GeneralNode找到最好的一條路。你可能有這樣的疑問，在所有的盤面中有沒有可能有一個GeneralNode的下一步，全部都是對方的WinNode？事實上是有的，而且還對我們的研究產生某些影響，因為這個原因，原來的LoseNode及WinNode個數就增加了。我們將在下一段中詳細介紹。6.所有的盤面中有沒有可能有一個GeneralNode的下一步，全部都是對方的WinNode？我們在為每一個GeneralNode找最佳下一步時，的確發現36736個盤面中，有

26、48個GeneralNode的Child Node全部都是對方的WinNode，所以這48個特殊盤面的價值就跟LoseNode是一樣的，只要遇到這樣的盤面，只要我們下任何一步，只要對方不放水，我們就輸定了。48個盤面，去除對稱性，只取一方的話，就是有三個盤面，以下把這三個盤面列出。(圖九)三種特殊的GeneralNode，輪到灰色的一方要下手，但不管怎麼走，都輸定了。這三個盤面還有一個相同的地方，就是灰色的一方只有一個位置可以放，配合上圓形棋子，總共會有13種可能的下棋法，13個方法都是必輸走法。如果我們把雙方的這三個盤面及其對稱也當成LoseNode(等於現在有240+48=288個)，再將

27、原來的Game-Tree重新整理(因為這48個特殊Node原來被當成GeneralNode，現在被當成是LostNode，所以WinNode的個數會改變，Game-Tree的分析也會改變)。整理後又發現48個原來被當成GeneralNode，現在因為Game-Tree的分析改變，所以他們的Child Node變成全部都是對方的WinNode。以下再把這三個盤面(去掉對稱並只取灰色的一方)列出。這三個盤面跟剛才的三個盤面有一樣的特性，都是會有13種可能的下棋法，13個方法都是必輸走法。我們再把這三個盤面及其對稱也當成LoseNode(等於現在有240+96=336個)，再送進Game-Tree做

28、分析，發現又出現了80個Node擁有之前發現的特性，不禁讓我們猜想，會不會就這樣一直把新發現的Node加入LoseNode中，就可以找到所有盤面的最佳解了呢？很可惜的，答案並非如此。我們總共用這樣的方法找到了224(48+48+80+48)個新的LoseNode，也因為如此，WinNode的個數也從雙方各6144個，變成8048個。多出來的LoseNode表示雖然不會馬上輸，但是一定會輸；相同的，多出來的WinNode表示是一個陷阱，對方只要踏進來了就遲早會輸。以下將除了剛才列出的六個特殊盤面(6*2*8=96=48+48)以外的八個擁有一樣特性的盤面：(八個是因為224種去掉96個之後去掉對

29、稱性，並只取灰色的一方)從這14種特殊的盤面，我們不難看出他們的相似性，就是大部份輸的一方的L形棋子都放到棋盤的角落，不然就是因為圓形棋子擺得不好所以產生的破綻，又再次呼應了之前所歸納出來的下棋策略。四、 結論1.L-Game沒有必贏的策略，但是如果位置下錯，勝負將立即分曉。L-Game對於人類而言是一個極需思考周全的的遊戲，因為既使能記下所有的失敗盤面，在實際對奕時，常常因為盤面的對稱，而不小心走到錯誤的盤面。2.L-Game先下手的一方與後下手的一方，擁有一樣多的對應盤面，所以先後並沒有差別。3.盡量不要把自己L形棋子放在棋盤的角落，80%的失敗盤面都是因為L形棋子卡死。圓形棋子要和自己的

30、L形棋子接觸，讓直角內側不被對方攻擊。相同的道理，要把自己的L形棋子放在對方的直角部份內側，會有較大致勝的機會。這是從所有的輸棋的盤面(包括遲早會輸的特殊盤面)分析出來的結果。 4.我們成功的以Game-tree的方式，以電腦找出L-Game所有的盤面，並加以分析。我們將我們的研究成果設計成CGI程式放在網頁上，提供大家上網挑戰我們的L-Game程式，不過我們的程式是不會輸的唷，不信你可以試試看J。請看附錄一中CGI程式部份執行畫面。(http:/www.ice.ntnu.edu.tw/u84340/L-game/)5.發現雙方各擁有18368種可能的盤面，其中有6144個盤面是必贏，120個

31、盤面必輸。加上一些特殊的Node(遲早會輸的盤面，每一方有112個)，所以只要雙方都沒有走進對方的WinNode，就會持續纏鬥下去，直到有一方走錯。6.對於盤面記錄的方式，期望能找到更好的記錄，用於其它棋類遊戲的研究。因為雖然目前的電腦速度及容量都不錯，但是面對棋類遊戲的盤面記錄，仍需要有好的資料結構與演算法，讓研究的效率更好。目前我們想到的方法是針對兩顆中立的圓形棋子的紀錄方式做改變：我們知道，當兩個L型的棋子位置確定後，兩個圓形的棋子就只有28種可能的位置，目前的紀錄方式是用兩個0到6的數字(n1,n2)來記錄，事實上我們發現0n1n26，所以如果我們把(n1,n2)的紀錄方式改成一個變數

32、round來記錄(0round27)，就可以節省接近一半的記憶體空間(原來用兩個變數，需要49單位記憶體，現在只要28單位就可以了)。五、參考文獻Edword De Bono (1988) 余阿勳 譯. 水平思考五日訓練法. 水牛出版社.Grimaldi Ralph P. (1994). Discrete and combinatorial mathematics : an applied introduction. 3rd ed.Ronald E. Walpole & Raymond H. Myers (1993). Probability and Statistics for Engine

33、ers and Scientists 5th Edition by Prentice-Hall, Inc.Wackerly & Mendenhall & Scheaffer (1996). Mathematical Statistics with Applications 5th Edition by Wadsworth Publishing Company.David Kincaid & Ward Cheney (1996). Numeriacl analysis : mathematics of scientific computing. 2nd ed.Harry R. Lewis & C

34、hristos H. Papadimitriou (1998). Elements of the theory of computation. 2nd ed.Neapolitan & Naimipour (1996). Foundations of algorithms by D. C. Heath and CompanyHorowitz & Sahni (1994). Fundamentals of Data Structures in Pascal 4th Edition by Computer Science PressGilbert Strang (1988). Linear Alge

35、bra and Its Applications 3rd Edition by Harcourt Brace Jovanovich, Inc.冼鏡光 (1990). : 名題精選百則 技巧篇 - 使用C語言。格致圖書公司。 (附錄一)L-Game的CGI程式執行畫面一、 遊戲介紹畫面(http:/www.ice.ntnu.edu.tw/u84340/L-game/index.html)本畫面簡單對L-Game做介紹，並提供使用者選擇要先下還是讓電腦先下。選擇之後會將不同的參數傳入我們所設計的CGI程式lgame.cgi之中，並開始遊戲。二、 輪到玩家下棋時畫面程式列出目前的盤面(Current

36、 State)，以及所有可能的下一步盤面供玩家選擇，選擇完後按下Submit鍵，會將玩家的選擇傳出，輪到電腦下。電腦會針對使用者所選擇的盤面尋找最佳的對應盤面，並秀出電腦的下一步(畫面詳見下一頁)。三、輪到電腦下棋時畫面程式列出目前的盤面(Current State)，以及電腦所選擇的下一步盤面，玩家可以從電腦的棋法中看出電腦的對應方法，玩家看完後按下Submit鍵就又輪到玩家選擇下一步如果電腦發現自己沒有下一步了，就會印出You Win !，告訴玩家已經勝利，但是我們的程式，玩家是不可能玩到讓電腦沒路走的J。四、玩家輸電腦的畫面輪到玩家時，如果電腦發現玩家沒有下一步可以選擇時，就秀出You Lose !，告訴玩家已經輸了，玩家可以選Restart L-game 重新再玩一次。