Penerapan angka nyata untuk gim

11

Ada konstruksi yang sangat bagus oleh Conway angka surealis. Mereka adalah "angka" yang berisi bilangan real dan tata cara, benar-benar dipesan, dan memiliki semua properti bidang (kecuali mereka tidak membentuk himpunan tetapi kelas).

Lihat misalnya pdf atau Wikipedia ini untuk pengantar.

Mereka bahkan dapat digeneralisasikan dengan apa yang disebut "permainan", yang awalnya diperkenalkan untuk mempelajari permainan kombinatorial. Motivasi asli Conway adalah untuk menganalisis permainan Go , khususnya endgame yang sangat cocok untuk dimodelkan dengan "permainan surealis".

Pertanyaan saya adalah: apakah Anda tahu ada orang yang telah menerapkan pendekatan ini dalam AI (yaitu pemain komputer) untuk meningkatkan levelnya dalam sebuah game? Saya terutama tertarik pada kasus Go, tetapi yang lain juga. Jika tidak, apakah ada kendala atau alasan mengapa itu bukan ide yang bagus?

reference-request gt.game-theory implementation board-games combinatorial-game-theory Denis
sumber
1
Menurut buku "Mathematical Go", tampaknya dulu ada program pendamping oleh Raymond Chen untuk memecahkan masalah endgame dalam buku itu, tetapi saya tidak tahu di mana itu dapat ditemukan. Saya juga memiliki ingatan samar tentang Berlekamp yang merujuk pada "Go explorer", yang dapat disebutkan dalam makalah "Papan permainan pintar dan go explorer: studi dalam perangkat lunak dan rekayasa pengetahuan". Saya tidak berpikir teori permainan kombinatorial benar-benar digunakan dalam program Main Go saat ini.
Mark S.
3
Jika saya ingat dengan benar (mungkin tidak seperti dulu), menurut David Wolfe (rekan penulis Matematika Go), orang dapat menyusun posisi akhir permainan Go di mana pemain profesional top cenderung bermain tidak optimal sebanyak sebagai titik, sedangkan pendekatan game-teori Conway / Berlekamp / Wolfe memungkinkan seseorang untuk menghitung optimal relatif mudah. Namun, posisi seperti itu dibuat-buat. Fenomena ini jarang terjadi pada game yang muncul dalam permainan nyata.
Neal Young

Jawaban:

8

Saya tidak punya jawaban untuk pertanyaan Anda apakah teori game Conway telah digunakan dalam membangun program bermain game, tetapi Anda mungkin masih tertarik dengan Combinatorial Game Suite , "sebuah program open-source untuk membantu penelitian dalam kombinatorial teori permainan "(yang saya pelajari pertama kali di sini ). Ini mencakup implementasi berbagai operasi standar pada game Conway dalam bentuk kanonik, serta bahasa scripting untuk menggambarkan game baru.

Noam Zeilberger
sumber
3

pada beberapa pencarian tampaknya tidak banyak implementasi umum dari angka-angka surealis. Inilah implementasi angka nyata dalam coq .

  • Nomor nyata dalam coq / Mamane, TYPES'04 Prosiding konferensi internasional 2004 tentang Jenis untuk Bukti dan Program

    Surreal Numbers membentuk bidang (komutatif) yang benar-benar dipesan, berisi salinan real dan (semua) ordinals. Saya telah mengkodekan sebagian besar struktur Ring dari angka-angka surealis dalam Coq. Pengkodean ini bergantung pada pengkodean teori set Aczel dalam teori tipe.

    Makalah ini membahas secara khusus poin-poin definisi atau pembuktian di mana saya harus menyimpang dari cara Conway atau yang paling alami, seperti pemisahan rekursi induksi-rekursi menjadi dua induksi, mentransformasikan definisi ordo menjadi definisi induktif yang saling induktif “paling banyak” dan "setidaknya" dan menyesuaikan skema induksi / rekursi yang agak rumit ke dalam teori tipe Coq.

ada beberapa bagian-implementasi aritmatika surealis untuk permainan yang disebut hackenbush (Davis) yang dipopulerkan oleh Conway, Berlekamp, ​​dan Guy yang ada beberapa referensi.

Go memang merupakan salah satu bidang penelitian AI permainan terdepan (dianggap jauh lebih sulit daripada catur yang diduduki AI selama beberapa dekade), tetapi tampaknya ada sedikit penelitian yang secara khusus menggunakan bilangan surealis untuk memodelkan / memainkannya. Go dianggap sebagai perbatasan untuk pembelajaran mesin / algoritma AI karena ia juga memiliki status / perbedaan yang relatif unik karena algoritma berbasis perangkat lunak terbaik ("masih / saat ini") tidak mengungguli pemain terbaik.

lihat referensi ini The Mystery of Go, Game Kuno bahwa Komputer Masih Tidak Dapat Menang (Wired mag) untuk survei kasar yang layak tentang teknik / peneliti / petunjuk Go AI saat ini.

vzn
sumber