2009年8月7日 星期五

【Neil自製】五子棋遊戲~v1.5



---------------- 以下是前言+廢話,可跳過 --------------------
五子棋?那不是幾百年前就有的老遊戲嗎?
而且網路上五子棋遊戲多到爆炸...那我寫這幹麼?(自嘲中...


其實阿...我會突然想寫這是因為,自從我大一讀了淡大資工系
開始寫程式到現在,已經要升大四了
在學校寫的程式作業不外乎都一些程式的寫作小技巧跟演算法實作
寫出來的東西幾乎沒辦法拿來作啥,更別說當遊戲玩
在我無聊時逛伊莉論壇的C/C++討論版
看到幾位高手寫出俄羅斯方塊、圈圈叉叉、坦克大戰等等小遊戲
看了覺得他們好厲害...都是一些我不知該怎寫東西...頓時覺得我好遜...
在論壇某篇有人提問說:「圈叉遊戲3*3好判斷,那五子棋遊戲該如何判斷勝負呢?」
我靈感一來...這好像蠻有趣的感覺...就開始想這問題,因此就開始寫看看五子棋遊戲啦~
順便當作練練程式功力...
----------------- 以上前言+廢話已結束 -----------------------

---------------------------------------------------------------
遊戲版本:1.5
最後更新日期:2010/01/06

***更新紀錄***
※1.5版:2010/01/06
1. 增加了連線對玩的功能:
.一方當server另一方就當client,server端必須先開遊戲程式,然後按「等待連線」按鈕。
.接著client端打開遊戲後,按「連線至...」按鈕,輸入server端的IP位址後按確定即可連線。
.我預設由server端先開始下棋。
2. 在連線方面我從很多主機去測試,連線功能是沒太大的問題,只是特殊處理的部份會有不少小bug在(例如玩到一半突然中斷的處理,或者結束一局後的處理等等),等我心血來潮再去修改那些bug...

※1.4版:2009/08/11
1. 調整權重值
2. 修正一些條件相衝之後的值,並新增一些特殊狀況條件
3. 弄掉1.3版每次跟電腦玩會跑出check_table.txt的檔案...這個檔是我用來檢測電腦跑出結果的相關資訊...在1.3版我忘了把他弄掉了= =

※1.3版:2009/08/10
1. 調整權重值及順序
2. 處理平手狀態
3. 增加一條規則,以減少權重值皆為0狀況:「對方在該空位是否能行成半活四」
4. 增加一條規則,以減少權重值皆為0狀況:「對方在該空位是否能行成半活三」
5. 用了三維陣列當stack,紀錄每點會形成的東西,較方便又準確判斷及給權重值
6. 新增電腦放棋速度隨機延遲...預設為0.3秒~1.8秒
7. 新增啟用或關閉使用鍵盤操作功能
這次改版改蠻多東西的..修正不少bug,增加準確度,增加一堆規則(搞得我頭好暈),個人感覺電腦AI有變得比較強...雖然不稱不上高智商AI,不過也算不低了...應該啦= =,連續好幾天不斷調整並發現AI有很多小地方要加強,雖然發現很多需要加強...但是加強完之後...只會發現更多的地方要修正...更多狀況出現...很難搞到很完美...畢竟電腦不是人腦...體會到AI這東西,真是與人腦無緣阿~

※v1.2版:2009/08/08
1. 增加了一條規則「對方在該空位是否能行成雙半活四」
2. 稍微調整權重值
3. 修改「偵測半活四」小bug
4. 以空白鍵當下棋,新增W、S、A、D控制上下左右
5. 增加一些跟電腦下棋輸贏的對話...

※v1.1版:2009/08/07
1. 新增了能夠用鍵盤上下左右來控制,Ctrl鍵來下棋,這是為了在雙人玩時避免搶滑鼠事件發生...
2. 重畫準心圖案,當換白色下棋時,準心變白色;當黑色下棋時,準心變黑色,比較好分辨輪到誰
3. 增加電腦下棋一條規則:「電腦在該空位是否能行成半活三」,為了降低權限值都是零的狀況
4. 存檔讀檔一些BUG修正
---------------------------------------------------------------

這程式呢,我用C++ Builder 2008寫的
玩法我應該不用講,大家都會玩...
剛開始寫這程式時,我一直在想這程式需要哪些變數,哪些功能,還有大概架構
先把東西打在txt記事本裡,這樣方法是有好處的
如果伊一始就寫,寫到一半一定會有東少一個西少一個,東加一個,西加一個
到時候寫出來程式碼很凌亂,不好debug
所以大概的架構想好了我才開始動手
一開始第一個碰到的問題就是,該如何判斷勝負?
我想到的方式是:一共要判斷四種方向「\」、「|」、「/」、「—」
當玩家一下棋子,就馬上以該位至為中心,判斷四種方向有沒有連續五個
每種方向都先移動到最開頭的位置,開始沿路算,如果算到末端,有五顆一樣的,那就是贏了

剛寫出來時候,其實只有雙打的功能,也就是人跟人玩,沒有跟電腦玩
想說如果是電腦該怎下...這應該判斷很多情況很複雜吧...
可是一個五子棋遊戲,如果只能雙打....這也太鳥了點吧...
於是去請教咕狗大神~~~~~搜搜搜
果然有五子棋的演算法~只是沒找到程式碼,不過我也不想要原始碼...
因為懶得看,而且不一定看得懂...有些原始碼沒半個註解,有些就算有註解,也不太懂他在寫啥...
不如靠自己去推敲...
到後來我是參考這篇,引用該篇的二樓說法;

五子棋AI演算法

  五子棋遊戲因為棋盤較大,五子棋遊戲因此不能考慮所有組合,而是利用一些五子棋落子的技巧,來設計演算法。利用五子棋AI 的演算法來說明,本作業C++ Builder五子棋遊戲電腦AI部分,則用此演算法。

1. 電腦對棋盤上的每一空位都有一個值,起始值為0。

2. 當對手下子後,電腦在決定接下來該下那一步前會先判斷棋盤上所有空位橫、豎、左斜、右斜四個方向的棋子構成不同的棋型。

3. 將所有棋盤上的空位對黑棋和白棋的價值算出來,給於不同的值。

  例如 :

判斷對手下在該空位是否能行成活四,權值最高。

判斷電腦下在該空位是否能行成活四,權值第二高。

判斷對手下在該空位是否能行成活三,權值第三高。

判斷電腦下在該空位是否能行成活三,權值第四高。

判斷對手下在該空位是否能行成活二,權值第五高。

判斷電腦下在該空位是否能行成活二,權值第六高。

4. 棋盤空位的值越高代表該空位越重要。

5. 電腦最後選擇棋盤上空位的值最高的一點作為下子的點。

6. 一直重複上述之步驟 直到分出勝負為止。

此演算法之缺點 : 每當對手下子之後,皆要重新計算棋盤上所有空位的值,因此較浪費執行時間

我看了這段話,剛開始想的時候覺得...這樣可以嗎?這樣就夠了嗎?還蠻懷疑的
後來想想...靈光一閃~咦,好像可以耶,只要把他方式增加一些規則進去,稍微修改一下
應該還可以
引用那段話裡面說權值最高,代表電腦要下該位置
不過他好像沒提到要累加的關係

舉個簡單的例子:
假設電腦形成活三權重值是20,玩家形成活三權重值是15
如果該空格能形成一條電腦活三、一條玩家活三(不累加權重是20,累加是35),另一個空格只能形成一條電腦活三(不累加權重是20)
總不能因為不累加,就隨便擺一個位子吧?如果累加的話,自己可以作活三,又能檔對方形成活三
所以應該要有累加權重值可能比較好~
所以我就修改成能累加權重值的方式
不過這時權重設定就要很小心
例如電腦可以形成兩個活三,累加權重是40,對方可以形成一個活四,假設是30
兩個活三累加超過一個活四...那電腦就等輸啦...
其實狀況還蠻多的...所以要小心設定數值

因為他舉出來的規則好像有點少,我就慢慢增加一些比較必要的規則,整理出如下:

電腦在該空位是否能形成五條
對方在該空位是否能形成五條
電腦在該空位是否能形成活四
電腦在該空位是否能形成雙半活四
對方在該空位是否能形成雙半活四
對方在該空位是否能形成活四
電腦在該空位是否能形成半活四
電腦在該空位是否能形成活三
對方在該空位是否能形成活三
電腦在該空位是否能形成活二
對方在該空位是否能形成活二
對方在該空位是否能形成半活四
電腦在該空位是否能形成半活三
對方在該空位是否能形成半活三

這些規則由上而下,權重由高到低 (2009/08/10)

因此電腦AI就這樣被我設定出來了~
話說我在寫的時候...真的是要人命...
因為要判斷有沒有兩邊都活路,還是說一邊有活路一邊沒活路,要算有幾顆,要看有沒有出界...
X軸Y軸的位置,傳參數後陣列的位置,要怎樣把執行效率提高,不能死腦的算法等等等等......
全部混在一起....真的是搞很久= =寫得超悶............
到最後寫出來整個只有爽字可以形容...
這邊大概是最難寫的部份了...也是修改最久的部份...

寫出來我玩第一場...就輸給電腦......= =
玩到最後覺得,我感覺電腦AI其實算普普吧...給朋友玩,朋友覺得算強...(可能我朋友太遜XDD)
或許權重值設定不夠好,或許這演算法有少東西...我有空在慢慢想好了

我後來
用clock函數測試1.4版五子棋電腦AI計算下棋位置所花的時間,發現每次都是0,也就是說每次電腦運算下棋位置時,花不到0.001秒就算出電腦該下哪個位置。不過...我單獨測WinAPI的播放音效函數,小小的放音效函數竟然需要花0.078~0.096秒...怎會這麼花時間...難怪我每次跟電腦下,都會有一點點停頓一下下,都要等0.156~0.192秒左右(玩家放一次,電腦放一次,所以兩次音效),我還一直以為是我電腦AI寫不好,運算慢的關係,沒想到原來都是那該死的WinAPI播放聲音函數造成的...並不是電腦AI運算慢造成的= =然後我把那條放音效函數拿掉試看看,發現還真的耶...我擺完棋子跟電腦放棋子肉眼看幾乎同時出現...快很多...可是如果沒下棋音效,玩起來好像又不太好...如果再多設計一個讓使用者要不要啟用放棋子聲音,好像又有點小題大作的感覺...不知各位有什麼意見@@?

--------------------------------------------------------------------------------
遊戲下載:點我
各位也來玩看看吧~如果有啥好意見歡迎留言喔~~!!我會參考看看~

為了因應某人要求...小弟就把程式碼放出來吧!!
我自己覺得寫得亂亂的,程式高手們可別笑我呀>"<
原始碼下載
解壓密碼:http://neilchennc.blogspot.com/2009/08/neil-xd.html
--------------------------------------------------------------------------------

以下題外話...
我怎感覺寫這好像在寫給自己爽的...
怎說勒?
我寫這搞半天,微調電腦AI,盡量增強電腦難度...
修改不少我已知的bug...增加一些功能.....修改程式讓電腦跑比較順...
總算搞出比較像樣的東西出來...而且這時成就感很大的時候..........
給一些朋友玩,玩個兩三次就沒再玩過了...
而且某人還給我一句...................「懶得玩」........................................(嘆
這也不能怪他們...畢竟這種超古老遊戲...沒幾個人會想去玩...
而且重點在於他們沒興趣,沒有對於「會寫程式的那種感覺」
今天如果是給會寫一些「簡單的程式」的人玩...那人說出來的話絕對不一樣...
這意思就好像說...以下存屬虛構...
就好像說....某人很擅長剪接影片,或者很會作某樣東西(例如電腦繪圖)
不斷地作,越作越大,越作越好,自己成就感也跟著越來越大
三不五時就秀給一個沒興趣的人看
或許沒興趣的人裝出驚奇的樣子出來,給他讚美之類的話
或許沒興趣的人對於他的作品完全沒感覺,來一個「喔...」,然後不了了之
因為我很瞭解這種感覺...所以我幾乎都當前者...
可是我這次做的東西,別人幾乎都是後者...
沒辦法~只能給自己爽了...不然能怎樣...
當我開始要寫五子棋程式時,其實已經預料到了...
只是純粹寫這段來發洩一下= =...沒別的意思...

另外...
我並沒有下棋的嗜好
更沒有什麼幾級幾段的東西
而且我幾乎沒在玩棋藝類的遊戲
我會寫這程式純粹在想些題材來練程式寫作
所以這程式重點並不在電腦強不強....
所以...覺得電腦太爛的也就將就點吧...

15 則留言:

  1. 這也不能怪他們...畢竟這種超古老遊戲...沒幾個人會想去玩..??

    你這樣好像有點污辱在下五子棋的人 ..(這不是重點)

    我想問..

    請問活三的擋法

    是如何設計的?

    擋敵方最多活路的地方?

    還是 擋對我方最有利的地方?

    好好思考吧 ..



    一般會下的人,不會下輸

    回覆刪除
  2. 大哥~五子棋是五顆連在一起算贏

    你這個電腦怎麼六顆也可以贏得這麼大言不慚?

    看得我很想扁他

    回覆刪除
  3. 還不錯不過
    棋力有點弱喔
    連贏很多盤
    我剛好是會下的人
    我下過其他軟體 五子棋大師 妙手連珠
    棋力都職業的水準

    網址含有無效的字元
    ....
    我不太會用這個

    在下鳥烏
    e12421@yahoo.com.tw

    回覆刪除
  4. Re: ALBUM <7036177811110284974>
    喔~我一直在猶豫要不要放程式碼出來...
    原因可能是...怕獻醜了~哈哈
    另一個原因是剛好我這幾天有在研究網路程式設計(winsock)
    想等我把五子棋改成能連線的方式再放出來@@

    (感覺上這兩個理由有點爛...)

    回覆刪除
  5. Re: 匿名 <4378225587844504186>
    我一直在猶豫要不要理你

    我說超古老遊戲=汙辱到在下五子棋的人??
    這算啥邏輯?超古老有啥不對?你心虛了?
    然後問我活三的檔法?我不懂ㄟ,我文章寫得清清楚楚我五子棋的演算法(algorithm),而且還用全都中文說明,你是沒看到?還問我怎設計的?找碴?

    是誰要好好思考?整個口氣就是表達你很行,你很厲害?那你要不要寫出一個來看看阿?

    回覆刪除
  6. 你好:我看不到裡面的程式碼 因為它需要密碼 我想研究裡面連線的部分 可以麻煩你給我密碼嗎

    回覆刪除
  7. 很厲害哦!有 source code 的遊戲最珍貴了。

    回覆刪除
  8. 厲害,連二盤輸給程式。

    回覆刪除
  9. 作者已經移除這則留言。

    回覆刪除
  10. 能拜師嘛!!!!????
    我目前只會用小黑寫出圈圈叉叉的必平手AI
    這樣實在太猛啦~!
    是認真要拜師

    回覆刪除
  11. 基本上所有的棋都是黑棋先手

    回覆刪除
  12. 40年前,在博物館的一台古老电腦磁片中,找到一個 人與电腦对下的五子棋遊戲(沒有現在一堆禁手規則),人會常下輸,程式用Basic寫的,計算/判斷部份的程式8行之內,卻用到3次方計算式。多年過去,還是不懂為什麼?

    回覆刪除
    回覆
    1. 計算部份程式,(目測)每行長度不超過60字。电腦不會下 連6,連7..

      刪除