Re: [討論] ?A?B猜數字遊戲的AI
根據經驗(在python上做profile分析)
一個AI要算得快，很重要的是比較兩個四位數字結果的這個function
不出意料的話很容易在這裡花上超過90%的計算時間
如果發現自己設計的AI算得太慢 (尤其是隨機算法要跑很多圈算平均)
建議把這個function做成查表
由於每次比較的結果只有0A0B~4A0B共14種 (沒有3A1B!!!)
在建立查表的時候建議把n1A, n2B存成:
if (input1 != input2) table[input1][input2] = n1 * 5 + n2;
else table[input1][input2] = 14;
這樣可以把所有組合簡單又不重複的壓在0~15 (其中兩個沒用到)
存表格只需要4 bit
是後續算法中的分析要使用都容易
舉例來說:
某算法中需要分析一群數字{P1,...Pn}對一個固定數字X比較的結果
想知道各種結果的累積次數存在int counter[16]中 (此處16對應0~15的結果)
可以直接在迴圈中用 counter[ table[Pi][X] ] ++;
快又效率不差
在需要把這個counter排序或找第N多的組的場合，14和16個元素也差不多有效率
如果記憶體夠的話就直接開9877*9877的unsign char二維陣列最快，要100MB
想省點記憶體就開5040*5040並利用point把數字對到序號(例如0123->0, 9876->5039)
再更省可以只記錄第一個數大於等於第二個數的表格，這樣只要15MB以下
再更省可以把每個結果只用4個bit存，用pointer+bit shift讀出來，這樣只要約7MB
※ 引述《bleed1979 (十三)》之銘言：
: 不曉得這個版會不會有人參加這樣的趣味競賽。
: 如果這樣能幫到原po的忙的話...
: GuessNumberAI.h
: http://codepad.org/pPM6p5ki
: ========================================
: #pragma once
: #include <fstream>
: #include <iomanip>
: class GuessNumberAI {
: public:
: GuessNumberAI() {
: std::fstream fout("./my_guess_number_score.txt", std::ios::out);
: for(int i = 1; i <= 20; ++i) {
: guess_times[i] = 0;
: }
: for(int r = 0; r < 1000; ++r) {
: for(int i = 123; i < 10000; ++i) {
: char g[5];
: g[0] = (i / 1000) + '0';
: g[1] = ((i % 1000) / 100) + '0';
: g[2] = ((i % 100) / 10) + '0';
: g[3] = (i % 10) + '0';
: g[4] = '\0';
: if(g[0] == g[1] || g[0] == g[2] || g[0] == g[3] ||
: g[1] == g[2] || g[1] == g[3] ||
: g[2] == g[3]) {
: continue;
: }
: std::string str(g);
: int t = algorithm(str);
: if(t <= 0 || t > 20) {
: fout << "you are too weak, out!" << std::endl;
: return;
: }
: ++guess_times[t];
: }
: }
: int width = 0;
: for(int i = 1; i <= 20; ++i) {
: if(guess_times[i] > 0) {
: int tmp = guess_times[i];
: int w = 0;
: while(tmp > 0) {
: tmp /= 10;
: ++w;
: }
: width = width < w ? w : width;
: }
: }
: for(int i = 1; i <= 20; ++i) {
: fout << std::setw(width + 1) << std::right << i;
: }
: fout << std::endl;
: for(int i = 1; i <= 20; ++i) {
: fout << std::setw(width + 1) << guess_times[i];
: }
: fout << std::endl;
: fout.close();
: }
: ~GuessNumberAI() {}
: int algorithm(const std::string& guess_str);
: private:
: int guess_times[21];
: };
: GuessNumberAI.cpp
: http://codepad.org/cj6FK9Nz
: ====================================================
: #include "GuessNumberAI.h"
: int GuessNumberAI::algorithm(const std::string& guess_str) {
: }
: int main() {
: GuessNumberAI app;
: return 0;
: }
: 想玩的人可以在algorithm()裡創造自己的演算法。
: guess_str長度為4，從 0123 ~ 9876，跑1000圈。
: 編譯會錯，因為algorithm()等待你的return猜測次數。
: 只要有一次可能猜超過20次就直接out了。
: my_guess_number_score.txt就是你的成績。
: ※ 引述《SocketAM2 (AM2)》之銘言：
: : 前陣子在python版看到有人討論到這個當年煞到我的遊戲，
: : 一下子熱血舊夢又被重燃...
: : 我還算有能力把我手上的想法用C弄出來，
: : 幾個程式設計相關的板這裡也算是人氣較旺，
: : 來這裡搞搞看有沒有人願意一起來玩玩瘋瘋
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.169.168.123
※ 編輯: SocketAM2 來自: 118.169.168.123 (09/22 10:18)
推
09/22 11:24, , 1F
09/22 11:24, 1F
討論串 (同標題文章)