[ กลับหน้าหลัก ]

การสร้างโปรแกรมหมากรุกไทย

จาก http://board.dserver.org/c/chesssiam/00000347.html
อาจจะเป็นประโยชน์ต่อท่านที่สนใจ
- - - -- - - - - - - - - - - - - - - -

หัวข้อ : การสร้างโปรแกรมหมากรุกไทย

ข้อความ : ข้อความต่อไปนี้เป็นข้อความที่ผมกับพี่เอ ถามตอบกันเกี่ยวกับเรื่องหมากรุกคับ
ผมเห็นว่ามันมีประโยชน์ต่อคนที่สนใจการเขียนโปรแกรมหมากรุก
เลยขอออณุญาติพี่ เอ นำมาเผยแพร่กัน ถ้าใครคนไหน รู้หลักการสร้างโปรแกรมหมากรุกไทยแบบ อื่นๆ
ก็คุยกันได้นะคับ


ถามครั้งแรก

Name: เพชร

ขอโทษที่รบกวนเวลาของพี่นะคับ ผมก็เป็นคนหนึ่งซึ่งขอบหมากรุกมาก
รู้จากเพื่อนในเน็ตว่าพี่เขียนโปรแกรม หมากรุกได้ ถ้าไม่เป็นการรบกวน ผมก็อยากรู้หลัก
การเขียนโปรแกรมหมากรุกคับ ตอนนี้ผมเขียนโปรแกรมโดยใช้ เดลไฟเขียน ลองฝึกเขีนยโปรแกรมหมากรุกดู
แต่เขียนได้เพียงแค่ใช้ดูการเดินธรรมดาเท่านั้นเองคับคือผมบันทึกข้อมูลการแข่งขันหมากรุก
แล้วมันเดินให้ดู ทำได้แค่นั้นเอง
แต่ ไม่รู้หลักการ
1. ให้มันเลือกเดินได้เอง
2. หลักการที่ตำแหน่งตัวหมากแต่ละตัวสามารถเดินได้ เช่นม้าเดิน 8 ตา มันรู้ได้ไงว่าตรงไหนมันเดินได้บ้าง
แบบโปรแกรมหมาากรุกที่เขาทำกัน ถ้าไม่เป็นการรบกวน พี่แนะนำหลักการให้ผมหน่อยได้ไหมคับ
ต้องขอโทษที่รบกวนคับ ขอบคุณคับ

สวัสดีครับคุณเพชร

ขอบคุณคุณเพชรมากนะครับ ที่ให้ความสนใจ สำหรับผมแล้วมีหลายคนนะครับที่ถามเรื่องการเขียนโปรแกรม
แต่ส่วนใหญ่จะยังไม่เคยเขียนโปรแกรมเลย จึงเป็นเรื่องยากที่จะอธิบายให้เข้าใจในเวลาอันสั้น
แต่ในกรณีของคุณเพชรเคยเขียนมาแล้ว อย่างนี้ก็คุยกันสนุกครับ

วิธีการทำให้คิดได้เองนะครับ ทุกคนที่เขียนจะต้องทราบเรื่อง mini-max กับ alpha-beta ครับ
ลองหาข้อมูลเพิ่มเติมได้ใน internet นะครับ แต่ขออธิบายสั้นๆง่ายๆ คือ mini-max ก็คือการที่เราลอง
generate move ของเรา แล้วพยายามทำให้ตำแหน่งที่เราเดินมีคะแนนดีๆ
หรือไม่ก็ทำให้คะแนนฝั่งตรงข้ามมีคะแนนแย่ๆ
ลองดูตัวอย่างนะครับ เป็น ภาษาพูด

int minimax(int Depth, BOARD Board)
{
int BestScore = LOSS;

if (Depth == 0)
return Eval(Board);

NumMove = GenerateMove(Move);

for (i = 0; i < NumMove; i++)
{
Board.MakeMove(Move);

Score = -minimax(Depth-1, Board);

Board.UnMakeMove(Move);

if (Score > BestScore)
BestScore = Score;
}

return BestScore;
}

ฟังก์ชันนี้รับสองตัว คือ ความลึกนะครับ
เหมือนกับว่าจะให้คอมคิดลึกไปอีกกี่ชั้น ส่วน board
ก็เป็นสถานะของกระดานในตอนนี้
เริ่มมาก็ดูว่าถ้าคิดจนสุดแล้วก็วัดคะแนนในฟังก์ชัน Eval ถ้านับกันง่ายๆ ก็ดูแต่ material เรือ ม้า เม็ด
และอื่นๆ ถ้ายังไม่จบ ก็เดินมันทุกแบบ แล้วดูว่า เดินไหนดีสุด (ทำให้อีกฝั่งแย่ที่สุด)

ลองศึกษาดูคร่าวๆ จากตัวอย่างนะครับ แล้วไปหาข้อมูลเพิ่มเติมในเวป ทางที่ดีควรมีตัวอย่าง source code
มาศึกษา เอาที่มันง่าย ๆ ถ้าอยากได้ก็เมลล์คุยกันอีกทีได้ครับ

คำถามที่สองเรื่องการ generate move ต้องคุยก่อนว่าจะเก็บกระดานเป็นแบบไหน ง่าย ๆ ก็เก็บเป็น array ขนาด
64 ช่อง ถ้าจะเช็ดเรื่องม้า ก็แยกออกมาเป็น แถว กับ คอลัมน์ แล้วก็ ลองเดิน เข่น row+2, col+1
ดูว่าตำแหน่งนั้นมีตัวอยู่รึเปล่าครับ ก็ไล่ไปในหลายๆกรณี แต่วิธีที่โปรแกรมชั้นนำใช้กัน
ในการเก็บกระดานเรียกว่า bitboard ครับ ไว้ถ้าสนใจคราวหน้าจะเล่าให้ฟัง

จาก : เพชรกะพี่เอ - - rhapsody@.mail.hunsa.com - 14/10/2002 00:09


ข้อความ 1 : ถามครั้งที่2
สวัสดีครับ น้องเพชร

> ขอบคุณคับพี่เอที่ช่วยตอบคำถามของผม ที่พี่พูดเรื่องเกี่ยวกับ
>generate move จากตัวอย่างของพี่ผมพอเข้าใจว่า คอมต้องคิดเป็นชั้นๆ เรื่อยๆ
จนกว่าจะหาตำแหน่งที่ดีที่สุด ไม่ทราบว่าผมเข้าใจถูกต้องไหมคับ

ครับ ถูกต้องครับ แต่คิดไปคิดมา ยังไงก็ต้องหยุดนะครับ เช่น
คิดได้ความลึกตามที่กำหนด หรือไม่ก็ ตามเวลาที่ตั้งไว้

>ถ้าจะเปรียบเทียบว่าแบบไหนดีที่สุด
>1. จำนวนที่กิน ใครกินได้มากกว่า
>2. ค่าหมากที่กินดูว่าเขาเสียตัวใหญ่มากกว่าเรา เช่น เราเอาโคนกินเรือได้
>เราก็ได้เปรียบ
>ถ้าผมกำหนดแบบนี้ จะดีไหมคับ
>เรือ ให้มีค่า 5
>ม้า ให้มีค่า 4
>โคน ให้มีค่า 3
>เม็ด ให้มีค่า 2
>เบี้ย ให้มีค่า 1

ค่านี้ดูแล้วยังไม่ดีนะครับ ถ้ามองแบบหมารุกสากล เรือ 5 ม้าจะ 3 เบี้ย 1
หมากรุกไทยก็คล้ายกัน โดยทั่วไป เรือ 5 ม้า 3 โคน 2.5 เม็ด ไม่แน่ใจนะครับ
1.5 หรือ 2 เบี้ย ก็ 1 ครับ อันนี้เป็นมาตรฐานเลย
ทีนี้ก็ขอเสริม เกล็ดเล็กเกร็ดน้อยในการเขียนโปรแกรม คือ
ถ้าโปรแกรมหมากรุกต้องเร็วมากๆๆ การใช้ตัวแปร double คำนวณค่าพวก 2.5 หรือ 1.5 ของโคนหรือเม็ดจะช้าหน่อย
(ใน function ย่อยๆ เวลานับความเร็ว ดูเป็น clock
cycle ของ cpu ก็ได้นะครับ) ฉะนั้น ถ้าคำนวณก็ควรคูณร้อย คือ เรือ 500 โคน 250
.... ก็จะทำให้ใช้ตัวแปร integer ในการคำนวณได้ ซึ่งจะเร็วขึ้น

>การกำหนดแบบนี้จะให้คอมมันรู้ว่าควรใช้ตัวไหนแลก จะเป็นวิธีที่ถูกต้องไหมคับ
>ยังมีหลักการอื่นอีกหรือเปล่าคับ เกี่ยวกับการคิดเป็นชั้นๆนี่
>ที่พี่เล่าว่ามีส่วนตัวอย่าง source code มาศึกษา ผมอยากได้คับ
>ถ้าไม่เป้นการรบกวนพี่นาคับ

เทคนิคในการคิดเป็นชั้น ๆ มีอีกมากมายครับ หลักการคือว่า
1. ทำให้จำนวนตำแหน่งในการคิดน้อยๆ ในความลึกที่เรากำหนด
2. ความเร็วในการคิดต่อหนึ่งตำแหน่งเร็ว ๆ เช่น คิดได้
ห้าแสนตำแหน่งต่อวินาที
3. move ที่เลือกยังได้ดีอยู่เหมือนวิธีการพื้นฐานที่เคยบอกไป
ถึงแม้จะเพิ่มเติม ส่วนของ ข้อ 1 และ ข้อ 2
สำหรับเทคนิคพวกนี้ลองไปหาอ่านใน net ก่อนนะครับ มีหลายที่เลย
แนะนำให้ก็ที่นี่เลย ดีมาก ๆๆ
http://www.gamedev.net/reference/programming/features/chess1/
มีทั้งคำอธิบาย แล้วก็มีตัวอย่างโปรแกรมครับ เขียนดีมากๆ
อ่านแล้วลองทำดูก่อนนะครับ ได้ผลยังไงค่อยคุยกันอีกที

>ส่วนอีกคำถาม ผมสงสัยมานานๆ มากละคับ ในกรณี สมมุติเริ่มต้น ผมเดินก่อนตาแรก
>ผมเดิน
>เบี้ย ตัวที่ 3 นับจากทางซ้าย คอมมันจะเลือกเดินตัวไหนละคับ
>เพราะมันยังเป็นต้นกระดานอยู่
>คอมมันจะเลิอกตัวใดละคับ เพราะยังไม่มีการกินกันเลย
>คอมจะหาทางได้เปรียบยังไงละคับ
>หรือเราจะต้องสอนคอมให้เลือกเดินตาแรก ๆ ด้วยคับ

นอกจากนับศักดิ์หมากแล้ว (นับจำนวนตัว) ต้องดูตำแหน่งด้วยครับ
อันนี้ก็ต้องให้เป็นคะแนน เช่น เบี้ยกลางกระดานดีกว่าขอบกระดาน
ม้าควรอยู่กลางกระดาน ถ้าเรือยึดคลองได้จะดี พวกนี้ถ้าจะให้คะแนนดี ๆ
ควรเข้าใจในการเล่นหมากรุกไทยให้มาก ๆ แล้วก็นำมาให้คะแนนทดสอบดู

ถ้าถามมา ก็จะพยายามตอบให้เข้าใจและนำไปใช้ได้ครับ จะไม่ตอบแบบขอไปที แต่ถ้าตรงไหนไม่เข้าใจ
ก็ถามมาเพิ่มอีกได้ครับ
ยังไงขอให้ตั้งใจทำให้สำเร็จนะครับ เริ่มแรกลองเก็บกระดานบน array 64 ช่องดูก่อน แล้วก็ generate move
ให้ได้ครับ แล้วก็ใช้ minimax เอาเท่านี้ก่อนครับ เรียกว่าทำให้เดินได้ ต่อไปก็มีกำลังใจทำต่อ

ขอขอบคุณพี่เอมากๆนะคับ และถ้าใครจะแนะนำผม หรือท่านใดจะเสริมก็คุยกันได้นะคับ

จาก : เพชรกะพี่เอ 2 - 14/10/2002 00:18

โดย : จอมขวัญใจ Member [ 26/08/2006, 08:12:07 ]

1

ปัญหาสำคัญของการสร้างโปรแกรมหมากรุก คือ
1. การคิดทุกทางเลือกล่วงหน้าทำให้การคำนวณช้า สมมติง่ายๆว่า แต่ละฝ่ายแต่ละตามีทางเลือกเป็นไปได้ 30
ทางเลือก ต้องการคำนวณหาคะแนนการได้เปรียบเสียเปรียบไปล่วงหน้าฝ่ายละ 10 ตาเดิน
จำนวนครั้งการคำนวณก็จะเป็น
30 ยกกำลัง 20 = 3.48678*10ยกกำลัง29
ถ้า เครื่องคอมพ์มี ความเร็ว 10 จิกะเฮิร์ท คือ คำนวนได้ 10ยกกำลัง10 ครั้ง ต่อวินาที
ก็จะใช้เวลาคำนวณทั้งหมด 10 ยกกำลัง 19 วินาที
ใน 1 วัน มี 86400 วินาที คิดเป็น 10ยกกำลัง5
ก็จะใช้เวลาคำนวณทั้งหมด 10ยกกำลัง14 วัน หรือ 10ยกกำลัง11ปี


2.เมื่อคิดทุกทางเลือกไม่ได้ จากข้อ1 ก็ต้องสร้างกฎขึ้นมาช่วยในการตัเสินใจ วิธีการอัลฟ่าเบต้า
ก็เป็นวิธียอดนิยม แต่ผลของมันในปัจจุบันยังไม่เป็นที่น่าพอใจเท่าไหร่
โปรแกรมหมากรุกก็ยังมีโอกาสเล่นแพ้คนที่เล่นเก่งอยู่ดี

ในอดีตหมากรุกสากล มีการว่าจ้างอดีตแชมป์โลก M. Botvinik (เป็นอาจารย์ของ Gary Kasparov)
มาเป็นทีมที่ปรึกษาในการวิจัยคิดค้นกฎในโปรแกรมหมากรุกขึ้นมา นำไปสู่การสร้างเครื่อง DeepBlue
เพื่อท้าประลองกับ Kasparov
การประลองครั้งแรก Kasparov ชนะ
ต่อมาเมื่อได้มีการปรับปรุงการหาคำตอบของเครื่อง DeepBlue
ใหม่
การประลองครั้งที่สอง Kasparov แพ้ แต่ Kasparov อ้างว่า
ในระหว่างการแข่งขัน ทีมที่ปรึกษาได้มีส่วนร่วมในการเดินหมากรุก
ที่เขาต้องพ่ายแพ้ ไม่ใด้พ่ายแพ้แก่ เครื่อง DeepBlue โดยตรง แต่พ่ายแพ้ให้กับ การทำงานร่วมกันระหว่าง
DeepBlue กับ ทีมที่ปรึกษา Kasparov เสนอให้แก้มือกันใหม่ โดยมีเงื่อนไขไม่ให้
ทีมที่ปรึกษาเข้าควบคุม DeepBlue ให้เป็นการสู้กันระหว่างเขากับ DeepBlue โดยตรงเท่านั้น
แต่ทางผู้ผลิตปฎิเสธ และทำการโละเครื่อง DeepBlue เข้าพิพิธภัณฑ์โดยไม่บอกเหตุผล
ก็เลยยังพิสูจน์ไม่ได้จนถึงปัจจุบันนี้ว่า โปรแกรมหมากรุกชนะคนเล่นเก่งได้ทุกคนจริงหรือไม่

ถ้าจะทำโปรแกรมหมากรุกไทยให้เล่นชนะคนเก่งจริงๆ
คงจะมุ่งไปที่การคิดค้นกฎที่สอดคล้องกับการคิดของเซียนหมากรุกให้มากที่สุด ขึ้นมาให้ได้
เรื่องส่วนของหน้าจอแสดงผล หรือโชว์ภาพนี่ ผมเสนอว่า ให้อ้างอิงพี่เอ หรือ ขอลอกพี่เอเขาโดยตรงก็ได้ครับ
ไม่ต้องเสียเวลาตรงจุดนี้

โดย : เทวดาจร Member   [ 26/08/2006, 12:21:25 ]

2

พอดีอ่านความเห้นของ คุณเรียว ใน สยามบอร์ด ว่า สนใจจะทำ
หุ่นยนต์เล่นหมากรุก ขอแนะนำว่า ดูตัวอย่างได้จากพวกเครื่องวาง
อูปกรณ์แผงวงจรแบบเซอร์เฟสเมาท์ ที่หยิบ IC จากตำแหน่งหนึ่งไปวางอีกตำแหน่งหนึ่ง
การควบคุมจะใช้ระบบนิวแมติก
และใช้การเชื่อมกับเครื่องคอมพ์แล้วเอาคำตอบจากโปรแกรมหมากรุกในเครื่องคอมพ์ส่งผ่านมา น่าจะประหยัดกว่า
และได้ผลดีกว่าการติดตั้งหน่วยประมวลผลในตัวหุ่นยนต์เอง

โดย : เทวดาจร Member   [ 26/08/2006, 12:28:30 ]

3

ขอบคุณมากครับ

โดย : webmaster Member   [ 27/08/2006, 01:56:32 ]
 
  E-mail: webmaster@thaibg.com Copyright 2002-2024@www.ThaiBG.com (Thailand), All Rights Reserved  
 
  Sponsors