目錄
三子棋
強(qiáng)化學(xué)習(xí)
狀態(tài)
行動(dòng)
分?jǐn)?shù)
獎(jiǎng)勵(lì)
完整代碼
寫個(gè)三子棋的強(qiáng)化學(xué)習(xí)AI玩玩。寫這玩意只需要有一點(diǎn)C語言基礎(chǔ)就可以了，至于AI部分，也是很好理解的。
三子棋
在3*3的棋盤中，先手方畫O，后手方畫X，連成3個(gè)就贏了。事實(shí)上，只需要很簡單的試驗(yàn)，你就會(huì)明白，如果雙方都走最優(yōu)解，最后一定是和棋。
讓電腦隨機(jī)下棋顯然沒有什么意思，那能不能讓電腦聰明點(diǎn)呢？
強(qiáng)化學(xué)習(xí)
強(qiáng)化學(xué)習(xí)的描述如下，看不太明白沒關(guān)系，我會(huì)舉例子的。
強(qiáng)化學(xué)習(xí)是機(jī)器學(xué)習(xí)的一個(gè)分支，它著重于如何讓智能系統(tǒng)（稱為代理）通過與環(huán)境的交互來學(xué)習(xí)做出最優(yōu)的決策或者行動(dòng)。在強(qiáng)化學(xué)習(xí)中，代理試圖通過執(zhí)行行動(dòng)并接收環(huán)境反饋（通常是獎(jiǎng)勵(lì)）來最大化其累計(jì)獲得的總獎(jiǎng)勵(lì)。這一過程涉及到學(xué)習(xí)行動(dòng)的策略，即在給定的狀態(tài)下應(yīng)采取什么行動(dòng)。
強(qiáng)化學(xué)習(xí)的核心組成部分包括：
- 代理（Agent）：執(zhí)行行動(dòng)的實(shí)體，其目標(biāo)是學(xué)習(xí)最佳行動(dòng)序列（策略）以最大化獎(jiǎng)勵(lì)。
- 環(huán)境（Environment）：代理所處并與之交互的系統(tǒng)或問題域。環(huán)境根據(jù)代理的當(dāng)前狀態(tài)和執(zhí)行的行動(dòng)，反饋新的狀態(tài)和獎(jiǎng)勵(lì)。
- 狀態(tài)（State）：環(huán)境的一個(gè)描述，代理根據(jù)狀態(tài)做出決策。
- 行動(dòng)（Action）：代理可以執(zhí)行的操作。
- 獎(jiǎng)勵(lì)（Reward）：環(huán)境對代理執(zhí)行行動(dòng)的即時(shí)反饋，指導(dǎo)學(xué)習(xí)過程。
強(qiáng)化學(xué)習(xí)的學(xué)習(xí)過程通常涉及探索（嘗試新行動(dòng)以了解它們的效果）和利用（使用已知的信息來獲得最大獎(jiǎng)勵(lì)）之間的平衡。這一平衡的目標(biāo)是發(fā)現(xiàn)最優(yōu)策略，即一個(gè)從狀態(tài)到行動(dòng)的映射，使得累積獎(jiǎng)勵(lì)最大化。
強(qiáng)化學(xué)習(xí)在多個(gè)領(lǐng)域有廣泛的應(yīng)用，如自動(dòng)駕駛汽車、游戲、機(jī)器人導(dǎo)航和控制、推薦系統(tǒng)等。與其他類型的機(jī)器學(xué)習(xí)不同，強(qiáng)化學(xué)習(xí)不是直接從數(shù)據(jù)集學(xué)習(xí)，而是通過試錯(cuò)和適應(yīng)環(huán)境的反饋來學(xué)習(xí)。
下面我來談?wù)勛詈唵蔚膹?qiáng)化學(xué)習(xí)，在三子棋中的應(yīng)用。雖然有點(diǎn)殺雞用牛刀的嫌疑，但這是個(gè)很好的例子。
電腦是很笨的，它只知道游戲規(guī)則：只有空位才能下棋、一人一步、連成3個(gè)獲勝……如果你不告訴它下棋的思路，它就只會(huì)隨機(jī)下。
狀態(tài)
棋局在某個(gè)時(shí)刻，會(huì)有一個(gè)狀態(tài)：
我們可以用3*3的二維數(shù)組來描述，即：
0 0 1
0 1 0
2 1 2其中0表示空位，1表示先手方的O，2表示后手方的X。
如果我把這個(gè)二維數(shù)組從右向左、從下到上排成一排，得到212010100，這是一個(gè)只由012組成的數(shù)字，可以看作三進(jìn)制，即，再轉(zhuǎn)換為十進(jìn)制int即可。如果要從這個(gè)整數(shù)還原棋局的狀態(tài)，只需要重新轉(zhuǎn)換成三進(jìn)制，再填到二維數(shù)組中。
這樣，我們成功地用int來描述棋局的狀態(tài)。棋局所有可能的狀態(tài)，不超過種，實(shí)際還要更少，因?yàn)橛幸恍┣闆r是達(dá)不到的。
int GetState(int board[3][3])
{
int state = 0;
// 轉(zhuǎn)換為3進(jìn)制數(shù)
for (int i = 2; i >= 0; --i)
{
for (int j = 2; j >= 0; --j)
{
state = state * 3 + board[i][j];
}
}
return state;
}
void StateToBoard(int state, int board[3][3])
{
// 還原三進(jìn)制整數(shù)
for (int i = 0; i < 3; ++i)
{
for (int j = 0; j < 3; ++j)
{
board[i][j] = state % 3;
state /= 3;
}
}
}行動(dòng)
在某個(gè)狀態(tài)下，比如：
此時(shí)輪到X走，假設(shè)棋盤的9個(gè)位置分別是：
0 1 2
3 4 5
6 7 8顯然二維數(shù)組的第x行第y列（x、y從0開始）表示數(shù)字n=x*3+y，而x=n/3，y=n%3。
那么對于上圖中的棋局狀態(tài)，X所有可能的走法就是：0,1,3,5。這樣，我們就用一個(gè)整數(shù)表示了某個(gè)狀態(tài)下的行動(dòng)。
分?jǐn)?shù)
某個(gè)狀態(tài)下的某個(gè)行動(dòng)都可以賦一個(gè)得分，這個(gè)分?jǐn)?shù)越高，表示這個(gè)行動(dòng)是越有利的。那么如何準(zhǔn)確得到每個(gè)狀態(tài)下的每個(gè)行動(dòng)的分?jǐn)?shù)呢？
我們可以這樣初始化分?jǐn)?shù)：
- 如果這步棋走完后能直接獲勝，分?jǐn)?shù)為1
- 如果這步棋走完后和棋，或者棋局未結(jié)束，分?jǐn)?shù)為0.5
- 如果這步棋不能走（位置已被占用），分?jǐn)?shù)為-1
static void _InitValue(value_t value)
{
for (int state = 0; state < STATES_CNT; ++state)
{
// 把狀態(tài)轉(zhuǎn)換為棋盤
int board[3][3] = { 0 };
StateToBoard(state, board);
// 根據(jù)走棋后的狀態(tài)，初始化分?jǐn)?shù)
for (int point = 0; point < 9; ++point)
{
int tmpBoard[3][3] = { 0 };
memcpy(tmpBoard, board, 9 * sizeof(int));
if (Move(tmpBoard, point / 3, point % 3))
{
int res = IsWin(tmpBoard);
// 贏 - 1
// 和棋 - 0.5
// 棋局未結(jié)束 - 0.5
if (res == 1 || res == 2)
value[state][point] = 1;
else
value[state][point] = 0.5;
}
else
{
// 該位置非法
value[state][point] = -1;
}
}
}
}你可能會(huì)問，那如果這步棋走完后輸了呢？emmm，這種可能不存在！注意這里只表示走一步棋的分?jǐn)?shù)。如果這步棋走完后幾步真的會(huì)輸，那么分?jǐn)?shù)應(yīng)該為0，這點(diǎn)后面會(huì)講。這樣，如果這個(gè)位置沒有違反規(guī)則，分?jǐn)?shù)就在[0,1]的范圍內(nèi)。
我們可以用一個(gè)二維數(shù)組來存儲(chǔ)所有狀態(tài)下的所有行動(dòng)的得分。二維數(shù)組的行標(biāo)表示棋局狀態(tài)（前面已經(jīng)用整數(shù)描述狀態(tài)了，為0~-1），列標(biāo)（0~8）表示行動(dòng)，二維數(shù)組內(nèi)存儲(chǔ)分?jǐn)?shù)。
顯然，這個(gè)分?jǐn)?shù)是不準(zhǔn)確的，有可能這步棋很爛，但分?jǐn)?shù)卻是0.5，這就需要讓AI強(qiáng)化學(xué)習(xí)了。
獎(jiǎng)勵(lì)
我們讓電腦自己和自己下棋，每一步都選擇當(dāng)前狀態(tài)下分?jǐn)?shù)最高的位置，如果分?jǐn)?shù)相同（比如一開始的9個(gè)位置分?jǐn)?shù)都是0.5），就隨機(jī)選擇一個(gè)位置。
int BestMove(int board[3][3], value_t value)
{
// 選擇value最大的走法
// 找到最大的value
int state = GetState(board);
double maxVal = -1;
int point = 0;
for (int i = 0; i < 9; ++i)
{
if (value[state][i] > maxVal)
maxVal = value[state][i];
}
// 有可能的最優(yōu)走法
bool moves[9] = { 0 };
// 找到所有和最大value接近的value
for (int i = 0; i < 9; ++i)
{
if (value[state][i] > maxVal - 0.01)
moves[i] = true;
}
// 在moves里隨機(jī)選擇一個(gè)最優(yōu)走法
while (true)
{
int point = rand() % 9;
if (moves[point])
return point;
}
}最終，會(huì)產(chǎn)生一個(gè)結(jié)果。有可能是先手方O贏了，也有可能是后手方X贏了，還有可能是和棋。
讓電腦吸取經(jīng)驗(yàn)教訓(xùn)，也就是給獎(jiǎng)勵(lì)，也可以是懲罰。
具體的做法是，從最后一步往前推，更新每一步的分?jǐn)?shù)。我們規(guī)定：
- 如果是某一方贏了，那么最后一步棋的得分就是1（這點(diǎn)和前面分?jǐn)?shù)的初始化保持一致），而倒數(shù)第二步棋是輸?shù)哪欠较碌?，這步棋的得分設(shè)置成0，因?yàn)槭沁@步棋直接導(dǎo)致了輸棋。
- 如果是和棋，那么最后一步棋的得分就是0.5（這點(diǎn)和前面分?jǐn)?shù)的初始化保持一致），而倒數(shù)第二步棋是另一方下的，這步棋的得分設(shè)置成0.5，因?yàn)槭沁@步棋直接導(dǎo)致了和棋。
那么倒數(shù)第三步和倒數(shù)第一步是同一方下的。倒數(shù)第三步的新的分?jǐn)?shù)=倒數(shù)第三步的舊的分?jǐn)?shù)+0.1*(倒數(shù)第一步的新的分?jǐn)?shù)-倒數(shù)第三步舊的分?jǐn)?shù))。
同理，倒數(shù)第四步和倒數(shù)第二步是同一方下的。倒數(shù)第四步的新的分?jǐn)?shù)=倒數(shù)第四步的舊的分?jǐn)?shù)+0.1*(倒數(shù)第二步的新的分?jǐn)?shù)-倒數(shù)第四步舊的分?jǐn)?shù))。
接下來是倒數(shù)第五步、倒數(shù)第六步……一直到正數(shù)第一步。這樣，這盤棋出現(xiàn)的狀態(tài)中，對于走過的行為，就有了新的分?jǐn)?shù)，這就是強(qiáng)化學(xué)習(xí)！
根據(jù)前面的計(jì)算方式，很容易知道，如果這步棋是合法的，那么分?jǐn)?shù)就在[0,1]之間。如果某一方贏了，該方最后一步的得分為1，那么前面的每一步分?jǐn)?shù)都會(huì)增加，因?yàn)樵摲胶笠徊降姆忠欢ū惹耙徊礁?，這就是獎(jiǎng)勵(lì)。而如果某一方輸了，該方最后一步的得分為0，那么前面的每一步分?jǐn)?shù)都會(huì)減少，因?yàn)樵摲胶笠徊降姆忠欢ū惹耙徊降?，這就是懲罰。
注意到更新的分?jǐn)?shù)乘了0.1，這樣越往前的分?jǐn)?shù)，變動(dòng)的幅度就越小，這也是合理的，因?yàn)樵浇咏寰珠_始，走棋的影響就越小。
經(jīng)過大量的對局后，所有狀態(tài)下的行為的得分就會(huì)更加準(zhǔn)確，無限趨近于理論值。然而，為了防止出現(xiàn)局部最優(yōu)，也就是AI自我感覺良好，最好讓AI有一定的概率隨機(jī)走棋，而不是每次都選擇最優(yōu)走法。
以下是一次強(qiáng)化學(xué)習(xí)：
void QLearning(value_t value)
{
// 棋盤
int board[3][3] = { 0 };
// 下棋的狀態(tài)數(shù)組
int states[9] = { 0 };
// 下棋的位置數(shù)組
int points[9] = { 0 };
// states和point數(shù)組記錄的狀態(tài)數(shù)量
int size = 0;
// 記錄state
int state = 0;
// 記錄勝負(fù)和
// 0 - 未分勝負(fù)
// 1 - 先手方獲勝
// 2 - 后手方獲勝
// 3 - 和棋
int res = 0;
// 下一盤棋
while (true)
{
// 計(jì)算并保存新的狀態(tài)
state = GetState(board);
states[size] = state;
// 一定概率隨機(jī)走棋
// 否則選擇value最大的走法
if (rand() % 10 < 3)
{
while (true)
{
// 隨機(jī)走棋
int x = rand() % 3;
int y = rand() % 3;
if (Move(board, x, y))
{
// 保存當(dāng)前point
points[size++] = x * 3 + y;
break;
}
}
}
else
{
// 選擇value最大的走法
// 找到最大的value和對應(yīng)的point
int point = BestMove(board, value);
// 在point位置下棋
Move(board, point / 3, point % 3);
// 保存point
points[size++] = point;
}
// 棋局是否結(jié)束
if (res = IsWin(board))
break;
}
// 根據(jù)這盤棋的信息，總結(jié)經(jīng)驗(yàn)
// 不考慮最后一步
--size;
// 倒數(shù)第二步直接導(dǎo)致輸棋或和棋
// 輸棋分?jǐn)?shù)設(shè)為0
// 和棋分?jǐn)?shù)設(shè)為0.5
value[states[size - 1]][points[size - 1]]
= (res == 3 ? 0.5 : 0);
--size;
// 從倒數(shù)第三步開始，每一步的分?jǐn)?shù)更新為
// 原來的分?jǐn)?shù) + 0.1 * (后兩步的分?jǐn)?shù)-原來的分?jǐn)?shù))
while (size > 0)
{
value[states[size - 1]][points[size - 1]]
= value[states[size - 1]][points[size - 1]]
+ 0.1 * (value[states[size + 1]][points[size + 1]]
- value[states[size - 1]][points[size - 1]]);
--size;
}
}這里舉個(gè)實(shí)際的例子，比如下面的對局（這里是我跟電腦的對局，實(shí)際強(qiáng)化學(xué)習(xí)時(shí)可以是電腦自己和自己下，也可以是人類和電腦下）：
這盤棋總共下了7步，就分出了勝負(fù)。假設(shè)這場對局之前，除了最后一步棋的分?jǐn)?shù)是1之外，其余的走法分?jǐn)?shù)都是0.5。那么，value數(shù)組中，這7步的得分一開始是：
0.5 0.5 0.5 0.5 0.5 0.5 1倒數(shù)第二步棋直接導(dǎo)致輸棋，分?jǐn)?shù)更新為0。
0.5 0.5 0.5 0.5 0.5 0 1接著更新倒數(shù)第三步棋的分?jǐn)?shù)，要加上倒數(shù)第一步棋的分?jǐn)?shù)（1）和自己（0.5）的差的0.1倍，即0.05，更新后的分?jǐn)?shù)為0.55。
0.5 0.5 0.5 0.5 0.55 0 1接著更新倒數(shù)第四步棋的分?jǐn)?shù)，要加上倒數(shù)第二步棋的分?jǐn)?shù)（0）和自己（0.5）的差的0.1倍，即-0.05，更新后的分?jǐn)?shù)為0.45。
0.5 0.5 0.5 0.45 0.55 0 1接著更新倒數(shù)第五步棋的分?jǐn)?shù)，要加上倒數(shù)第三步棋的分?jǐn)?shù)（0.55）和自己（0.5）的差的0.1倍，即0.005，更新后的分?jǐn)?shù)為0.505。?
0.5 0.5 0.505 0.45 0.55 0 1同理更新前2步的分?jǐn)?shù)：
0.5005 0.495 0.505 0.45 0.55 0 1這就是一次強(qiáng)化學(xué)習(xí)。最終訓(xùn)練的結(jié)果，也就是value數(shù)組只需要保存到文件中，需要對局時(shí)再從文件中讀取數(shù)據(jù)，這樣就不用每次都重新訓(xùn)練了。文章來源：http://www.zghlxwxcb.cn/news/detail-843927.html
void SaveValue(value_t value)
{
FILE* fin = fopen("value.dat", "wb");
if (fin == NULL)
{
perror("fopen");
exit(2);
}
// 保存value
fwrite(value, sizeof(double), 177147, fin);
fclose(fin);
fin = NULL;
}
bool LoadValue(value_t value)
{
FILE* fout = fopen("value.dat", "rb");
// 沒有這個(gè)文件
if (fout == NULL)
return false;
// 加載value
fread(value, sizeof(double), 177147, fout);
fclose(fout);
fout = NULL;
return true;
}完整代碼
已上傳至gitee鏈接文章來源地址http://www.zghlxwxcb.cn/news/detail-843927.html
到了這里，關(guān)于三子棋大師：用C語言打造無敵強(qiáng)化學(xué)習(xí)AI的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
