Chơi cờ đam bằng thuật toán di truyền: Học tập tiến hóa trong các trò chơi truyền thống

giới thiệu

Cờ đam hay còn gọi là cờ đam là một trò chơi cổ xưa được ưa chuộng từ rất lâu. Giống như các trò chơi board cổ điển khác, nó đã thu hút sự quan tâm của các nhà khoa học máy tính và nhà nghiên cứu AI để làm nền tảng cho các thí nghiệm của họ. Một phương pháp nổi bật mà họ sử dụng để huấn luyện máy tính chơi cờ đam là thuật toán di truyền, dựa trên khái niệm sinh tồn của kẻ mạnh nhất thúc đẩy quá trình tiến hóa.

Trong bài viết này, chúng ta sẽ khám phá sự giao thoa giữa cờ đam và thuật toán di truyền, chứng minh cách có thể sử dụng các kỹ thuật tính toán tiến hóa để phát triển các tác nhân chơi cờ đam thành thạo.

Trong bài viết trước, tôi nghĩ rằng tôi đã đề cập đủ chủ đề về cờ đam, tuy nhiên, chúng ta hãy nhớ các quy tắc cơ bản của trò chơi: Trò chơi cờ đam được chơi trên một bàn cờ 10x10, mỗi người chơi bắt đầu với 20 quân cờ.

Mục tiêu rất đơn giản: bắt hết quân của đối thủ hoặc bẫy chúng để chúng không thể di chuyển. Các chiến lược chính xoay quanh việc định vị, phòng thủ, tấn công và đoán trước các bước di chuyển của đối thủ.

Thuật toán di truyền (GA)

Những thứ cơ bản

GA là các thuật toán tối ưu hóa dựa trên quá trình chọn lọc tự nhiên. Các thuật toán này phản ánh quy trình tiến hóa được quan sát thấy trong tự nhiên, bao gồm chọn lọc, lai ghép (tái tổ hợp) và đột biến.

Các thành phần của mạng lưới thần kinh

Bài viết này sẽ sử dụng một mô hình đơn giản với các lớp được kết nối đầy đủ. Một lớp là một tập hợp các nơ-ron xử lý đầu vào và tạo ra đầu ra. Những đầu ra này sau đó được sử dụng làm dự đoán cuối cùng trong trường hợp lớp cuối cùng (lớp đầu ra) hoặc được chuyển làm đầu vào cho lớp tiếp theo trong mạng.

Mỗi lớp chứa:

• đầu vào : số lượng tham số đầu vào

• đầu ra : số lượng tham số đầu ra

• trọng số : Trọng số là tham số mà mạng điều chỉnh trong quá trình đào tạo để giảm thiểu lỗi dự đoán.

• thiên vị : được thêm vào tổng đầu vào trước hàm kích hoạt. Độ lệch giúp điều chỉnh đầu ra cùng với trọng số.

• chức năng kích hoạt : Mỗi nơ-ron trong một lớp, ngoại trừ lớp đầu vào, áp dụng chức năng kích hoạt cho đầu vào của nó trước khi chuyển đầu ra sang lớp tiếp theo. Điều này rất cần thiết để mạng mô hình hóa các mối quan hệ phi tuyến tính trong dữ liệu.

Các thành phần của thuật toán di truyền

• Dân số : Một tập hợp các giải pháp ứng cử viên.

• Chức năng phù hợp : Nó đánh giá hiệu suất hoặc "sự phù hợp" của một giải pháp riêng lẻ.

• Lựa chọn : Căn cứ vào tính thích hợp, một số giải pháp được lựa chọn để nhân giống.

• Crossover : Kết hợp các phần của hai giải pháp đã chọn để tạo ra con cái.

• Đột biến : Tạo ra những thay đổi nhỏ ngẫu nhiên ở thế hệ con cháu.

Áp dụng thuật toán di truyền cho cờ đam

Mã hóa vấn đề và đánh giá sự phù hợp

Đầu tiên, chúng ta phải tìm ra cách biểu diễn một giải pháp tiềm năng, như chiến lược cờ caro, theo cách phù hợp với thuật toán di truyền. Trong trường hợp của chúng tôi, chúng tôi sẽ lấy tất cả các nước đi có thể có cho người chơi hiện tại, đánh GA về từng nước đi và sau đó chọn nước đi có trọng lượng lớn nhất.

Ngoài ra, chúng ta cần tính điểm trò chơi để chọn ra những vật phẩm tốt nhất trong quần thể. Trong trường hợp của chúng tôi, nó sẽ là:

• 250 điểm cho một chiến thắng
• 3 điểm cho mỗi quân cờ thông thường
• 7 cho Vua Cờ Vua
• -1 cho mỗi lần di chuyển

Đối với mỗi nhóm dân cư, chúng tôi sẽ tạo một giải đấu (một phiên bản đơn giản của giải đấu theo hệ thống Thụy Sĩ). Sau mỗi giải đấu, chúng tôi chọn ra 1/4 dân số để lựa chọn trong tương lai.

Nếu một đặc vụ nào đó là người chơi hàng đầu (được chọn cho thế hệ tiếp theo) trong hơn 1 giải đấu, chúng tôi chọn anh ta làm người chơi hàng đầu và sau khi tất cả các kỷ nguyên kết thúc, chúng tôi tạo một giải đấu giữa những người chơi hàng đầu và chọn ra người giỏi nhất, cái nào sẽ được lưu.

Lựa chọn, lai ghép và đột biến trong cờ đam

Điểm mấu chốt của thuật toán nằm ở việc phát triển quần thể chiến lược.

• Lựa chọn : Các chiến lược hoạt động tốt hơn trong trò chơi có cơ hội được chọn để tái tạo cao hơn.

• Crossover : Hai chiến lược "cha mẹ" có thể được kết hợp, có thể thực hiện một số bước mở đầu từ một chiến lược và chiến thuật kết thúc trận đấu từ chiến lược khác.

• Đột biến : Đôi khi, một chiến lược có thể trải qua những thay đổi ngẫu nhiên, có khả năng khám phá ra những chiến thuật mới, hiệu quả.

Những thách thức và hạn chế

Tối ưu cục bộ

Có nguy cơ thuật toán bị mắc kẹt trong mức tối ưu cục bộ, nơi nó cho rằng nó đã tìm ra chiến lược tốt nhất nhưng chỉ tối ưu trong một vùng nhỏ của không gian giải pháp.

Cường độ tính toán

Mặc dù GA có thể nhanh nhưng việc mô phỏng hàng nghìn hoặc hàng triệu trò chơi đòi hỏi nguồn lực tính toán đáng kể.

Trang bị quá mức

Có nguy cơ là chiến lược đã phát triển trở nên quá phù hợp với các tình huống huấn luyện và hoạt động kém so với các chiến lược hoặc chiến thuật chưa được nhìn thấy.

Mã hóa

Tôi sẽ sử dụng node.js.

Tại sao không phải là Python?

Tôi biết rằng Python sẽ hiệu quả hơn, nhưng với node.js, thứ mà tôi quen thuộc hơn, nó có thể dễ dàng được sử dụng ở phía máy khách và phía máy chủ.

Tại sao không phải là tensorflow.js (hoặc bất kỳ thư viện nào khác rất gần gũi với bạn) ?

Ban đầu, tôi dự định sử dụng thư viện này, nhưng sau đó tôi quyết định rằng vì dự án này chủ yếu mang tính giáo dục nên tôi có thể tự tạo ra một mạng lưới nơ-ron khả thi ở mức tối thiểu và cũng để lại không gian cho những cải tiến tiếp theo (ví dụ: sử dụng wasm để tính toán).

Mạng lưới thần kinh

Hầu hết mọi mạng thần kinh đều là một tập hợp các lớp trong đó một số dữ liệu được nhận làm đầu vào, được nhân với một tập hợp các chỉ mục và một số dữ liệu được trả về.

Để rõ ràng hơn, hãy tưởng tượng rằng bạn đang tìm kiếm một ngôi nhà mới trong mơ của mình và bây giờ bạn đã tìm thấy nó, và bây giờ bạn hỏi bạn bè của mình xem họ nghĩ gì về ngôi nhà này và họ đưa ra câu trả lời theo thang điểm 10 chẳng hạn. .

Bạn tin tưởng ý kiến của từng người bạn ở một mức độ nhất định, nhưng bạn phải hỏi tất cả mọi người, ngay cả những người bạn không đặc biệt tin tưởng, để không bị xúc phạm. Và thế là bạn ngồi cùng nhóm với bạn bè với đồ uống yêu thích của mình và ngắm nhìn những ngôi nhà khác nhau, và mọi người đều nói rằng họ thích nó đến mức nào.

Kết quả là bạn biết bạn bè mình nghĩ gì về từng ngôi nhà và dựa vào kết quả cuối cùng mà bạn quyết định.

Mạng lưới thần kinh chỉ bao gồm những “người bạn” như vậy, nhưng số lượng nhóm bạn có thể khá lớn và mọi người đều dựa vào ý kiến của nhóm trước đó.

Sơ đồ trình bày của mạng lưới thần kinh:

Lớp cho mạng thần kinh:

 import {createEmpty, createNew} from "./genetic"; export enum Activation { Sigmoid, Relu, } class Layer { weights: Float32Array; biases: Float32Array; inputCount: number; outputCount: number; size: number; activation: Activation; /** * Create a new layer * @param inputCount * @param outputCount * @param activation */ constructor( inputCount: number, outputCount: number, activation: Activation = Activation.Relu ) { this.inputCount = inputCount; this.outputCount = outputCount; this.weights = createNew(inputCount * outputCount, 2); this.biases = createNew(outputCount, 2); this.activation = activation; this.size = inputCount * outputCount + outputCount; switch (activation) { case Activation.Sigmoid: this.activate = this.activateSigmoid.bind(this); break; case Activation.Relu: this.activate = this.activationRelu.bind(this); break; } } /** * Activation function (identity) * @param val */ activate(val: Float32Array) { return val; } /** * Activation function (sigmoid) * @param val */ activateSigmoid(val: Float32Array) { return val.map((v) => 1 / (1 + Math.exp(-v))); } /** * Activation function (relu) * @param val */ activationRelu(val: Float32Array) { return val.map((v) => Math.max(0, v)); } /** * Predict an output * @param inputs */ predict(inputs: Float32Array) { let result = createEmpty(this.outputCount); for (let i = 0; i < this.outputCount; i++) { for (let j = 0; j < this.inputCount; j++) { result[i] += inputs[j] * this.weights[i * this.inputCount + j]; } result[i] += this.biases[i]; } return this.activate(result); } /** * Get the weights of the layer */ getWeights() { return Float32Array.from([...this.weights, ...this.biases]); } /** * Gst current layer topology */ getTopology() { return new Float32Array([ this.inputCount, this.activation, this.outputCount, ]); } /** * Set the weights of the layer * @param weights */ setWeights(weights: Float32Array) { this.weights = weights.slice(0, this.weights.length); this.biases = weights.slice(this.weights.length); } }

Mạng lưới thần kinh:

 export class Network { network: Layer[] = []; inputs: any; outputs: any; /** * Create a new network * @param inputs * @param outputs * @param layer */ constructor(inputs: number, outputs: number, layer: (number[] | Layer)[]) { this.inputs = inputs; this.outputs = outputs; for (const layerSize of layer) { const l = layerSize instanceof Layer ? layerSize : new Layer(layerSize[0], layerSize[2], layerSize[1]); this.network.push(l); } } /** * Predict an output * @param input */ predict(input: Float32Array) { return this.network.reduce((acc, layer) => layer.predict(acc), input); } /** * Get topology for whole network */ getTopology() { return new Float32Array( [ this.inputs, this.outputs, this.network.length, ...this.network.map((layer) => [...layer.getTopology()]), ].flat() ); } /** * Get the weights of the network */ getWeights() { return this.network.reduce((acc, layer) => { return new Float32Array([...acc, ...layer.getWeights()]); }, new Float32Array([])); } /** * Set the weights of the network * @param weights */ setWeights(weights: Float32Array) { let offset = 0; for (const layer of this.network) { layer.setWeights(weights.slice(offset, offset + layer.size)); offset += layer.size; } } /** * Get the size of the network */ size() { return this.network.reduce((acc, layer) => acc + layer.size, 0); } /** * Serialize the network */ toBinary() { const topology = this.getTopology(); const weights = new Float32Array(topology.length + this.size()); weights.set(this.getTopology()); weights.set(this.getWeights(), topology.length); return Buffer.from(weights.buffer); } /** * Create a network from a binary * @param json * @param weights */ static fromBinary(buffer: Float32Array) { const inputs = buffer[0]; const outputs = buffer[1]; const length = buffer[2]; const layers = Array.from({ length }).map((_, i) => { const start = 3 + i * 3; const end = start + 3; const topology = buffer.subarray(start, end); return new Layer(topology[0], topology[2], topology[1]); }); const network = new Network(inputs, outputs, layers); network.setWeights(buffer.subarray(3 + length * 3)); return network; } }

Đại lý

agent là một thực thể nào đó quyết định phải làm gì tiếp theo và nhận phần thưởng hoặc tiền phạt cho các hoạt động của mình. Nói cách khác, người đại diện là một người bình thường đưa ra quyết định trong công việc và nhận phần thưởng cho việc đó.

Là một phần nhiệm vụ của chúng tôi, tác nhân chứa một mạng lưới thần kinh và chọn giải pháp tốt nhất theo quan điểm của mạng lưới thần kinh.

Ngoài ra, đại lý của chúng tôi, giống như bất kỳ nhân viên giỏi nào, ghi nhớ kết quả công việc của mình và báo cáo cấp trên (thuật toán di truyền) về giá trị trung bình, dựa vào đó đưa ra quyết định cuối cùng về nhân viên này.

 import { Keccak } from "sha3"; import { Network, Agent, createEmpty, getMoves, FEN } from "shared"; export class AgentTrainer implements Agent { historySize: number; history: Float32Array; id: string; private _games: Set<string> = new Set(); games: number = 0; wins: number = 0; score: number = 0; minScore = +Infinity; maxScore = -Infinity; age: number = 0; network: Network; taken: boolean = false; _player: "B" | "W" = "W"; /** * Create a new agent * @param historySize * @param modelPath * @param weights */ constructor(historySize: number, buf: Float32Array) { this.historySize = historySize; this.network = Network.fromBinary(buf); this.id = new Keccak(256).update(Buffer.from(buf.buffer)).digest("hex"); this.history = createEmpty(this.historySize); } /** * Create a new epoch */ onNewEpoch() { this.age += 1; this.score = 0; this.games = 0; this._games = new Set(); this.maxScore = -Infinity; this.minScore = +Infinity; this.wins = 0; this.reset(); } /** * Check if the player has played against the opponent * @param player */ hasPlayedBefore(player: AgentTrainer) { if (this.id === player.id) { return false; } return this._games.has(player.id); } /** * Set the result of a match * @param score * @param opponent */ setResult(score: number, opponent: AgentTrainer) { this._games.add(opponent.id); this.games += 1; this.score += score; this.minScore = Math.min(this.minScore, score); this.maxScore = Math.max(this.maxScore, score); if (score > 0) { this.wins += 1; } } /** * Calculate the average score * @returns number */ getAverageScore() { return this.score / this.games; } /** * Get the weights of the network */ getWeights() { return this.network.getWeights(); } getTopology() { return this.network.getTopology(); } /** * Serialize the weights of the network */ serialize() { return this.network.toBinary(); } /** * Reset history */ reset() { this.history = new Float32Array(this.historySize); this.taken = false; } toString() { return `${this.id} with ${String(this.score).padStart( 6, " " )} points min: ${String(this.minScore).padStart(6, " ")} max: ${String( this.maxScore ).padStart(6, " ")} avg: ${String( this.getAverageScore().toFixed(2) ).padStart(9, " ")} ${((this.wins / this.games) * 100) .toFixed(2) .padStart(6, " ")}%`; } setPlayer(player: "B" | "W") { this._player = player; } /** * Calculate moves and return the best one * @param gameState * @returns */ getMove(gameState: FEN): string { const board = new Float32Array(50); const wMul = this._player === "W" ? 1 : -1; for (let i = 0; i < gameState.white.length; i++) { let isKing = gameState.white[i].startsWith("K"); let pos = isKing ? parseInt(gameState.white[i].slice(1), 10) : parseInt(gameState.white[i], 10); board[pos] = wMul * (isKing ? 2 : 1); } for (let i = 0; i < gameState.black.length; i++) { let isKing = gameState.black[i].startsWith("K"); let pos = isKing ? parseInt(gameState.black[i].slice(1), 10) : parseInt(gameState.black[i], 10); board[pos] = -1 * wMul * (isKing ? 2 : 1); } this.history = new Float32Array([...board, ...this.history.slice(50)]); const value = new Float32Array(this.network.inputs); value.set(new Float32Array(50)); value.set(this.history, 50); let pos = 0; let posVal = -Infinity; const moves = getMoves(gameState); for (let i = 0; i < moves.length; i += 1) { /** * Create a new value for move */ const move = moves[i]; const val = value.slice(); val[move.from - 1] = -1; val[move.to - 1] = 1; const result = this.network.predict(val); /** * If the result is better than the previous one, save it */ if (result[0] > posVal) { pos = moves.indexOf(move); posVal = result[0]; } } /** * Return the best move in the format from-to */ return `${moves[pos].from}-${moves[pos].to}`; } }

Chơi một trận đấu giữa các đại lý.

Để có được kết quả của công việc, ta cần so sánh hai tác nhân sao cho chúng ở điều kiện như nhau; mỗi người trong số họ sẽ chơi cho từng màu và kết quả cuối cùng sẽ được tổng hợp.

Để không làm mạng lưới bị quá tải với những thông tin không cần thiết, mỗi đại lý xem bàn cờ như thể mình đang chơi cờ trắng.

 import { Draughts } from "@jortvl/draughts"; import { Player, Position, getFen } from "shared"; import { AgentTrainer } from "./agent"; export function playMatch(white: AgentTrainer, black: AgentTrainer) { const draughts = new Draughts(); white.setPlayer(Player.White); black.setPlayer(Player.Black); while (!draughts.gameOver()) { /** * Get current player */ const player = draughts.turn() === Player.White ? white : black; /** * Get the move from the player */ const move = player.getMove(getFen(draughts.fen())); draughts.move(move); } /** * Calculate the score */ const [winner, ...left] = draughts.position().split(""); const score = 250 + left.reduce((acc: number, val: string) => { switch (val) { case Position.Black: case Position.White: return acc + 3; case Position.BlackKing: case Position.WhiteKing: return acc + 7; default: return acc; } }, 0) - draughts.history().length; /** * Set the result, if white won, the score is positive; if black won, the score is negative */ return winner === Player.White ? score : score * -1; }

Chơi giải đấu

Ở mỗi thời kỳ đào tạo (kiểm tra công việc) của các đặc vụ, chúng ta có một tập hợp các đặc vụ thử nghiệm mà chúng ta sẽ đấu với nhau. Nhưng vì việc kiểm tra từng đại lý với nhau sẽ rất lâu và không hiệu quả nên chúng ta sẽ sử dụng thuật toán giải cờ vua đơn giản hóa.

Ở mỗi giai đoạn, chúng tôi có danh sách người chơi được sắp xếp theo điểm và phân bổ như sau: người đầu tiên chơi với đối thủ đầu tiên từ giữa bảng. Nếu anh ấy đã chơi với anh ấy rồi, chúng tôi sẽ chọn người tiếp theo.

 import {Agent} from "./agent"; import {playMatch} from "./play-match"; export function playTournament(playerList: Agent[]) { let d = Math.floor(playerList.length / 2); /** * Count rounds */ let rounds = Math.ceil(Math.log2(playerList.length)) + 2; for (let i = 0; i < rounds; i += 1) { for (let j = 0; j < d; j += 1) { let dj = d; /** * Find the next opponent */ let found = false; while (dj < playerList.length && !found) { if (playerList[dj].hasPlayedBefore(playerList[j]) || playerList[dj].games > i) { dj += 1; } else { found = true; } } if (found) { let score = 0; /** * Play the match */ score += playMatch(playerList[j], playerList[dj]); /** * Play the reverse match */ score += playMatch(playerList[dj], playerList[j]) * -1; playerList[j].setResult(score, playerList[dj]); playerList[dj].setResult(-1 * score, playerList[j]); } } playerList.sort((player1, player2) => player2.score - player1.score); console.log('round', i, playerList[0].id, playerList[0].score.toFixed(1).padStart(6, ' ')); } return playerList; }

Giải đấu

Đây là nơi tất cả sự kỳ diệu của thuật toán di truyền xảy ra. Các mô hình hiện có được tải và các mô hình mới được tạo.

Từ những mô hình này, chúng tôi có được bộ gen với các tác nhân sẽ được sử dụng trong trò chơi của chúng tôi. Bộ gen này sẽ thay đổi khi tiến trình đào tạo, các đặc vụ có điểm thấp nhất sẽ bị loại bỏ và các đặc vụ có điểm cao nhất sẽ truyền gen của họ cho các thế hệ mới và sẽ được so sánh với chúng.

Tạo bộ gen mới:

Một bộ gen mới được tạo ra trong một khoảng số nhất định, không có vấn đề di truyền hay những thứ tương tự, và đây là nơi mọi thứ sẽ bắt đầu.

 export function createNew(size: number, delta = 4): Float32Array { return new Float32Array(size).map(() => Math.random() * delta - (delta / 2)); }

chéo:

Cơ chế khá đơn giản; chúng tôi lấy hai bộ gen (trọng số) từ tác nhân và tùy theo xác suất, chúng tôi lấy gen từ tác nhân thứ nhất hoặc tác nhân thứ hai, do đó, các gen được trộn lẫn và thu được một mạng mới với một số kiến thức từ tác nhân thứ nhất và thứ hai đại lý.

Đây chính xác là cách mọi thứ hoạt động trong tự nhiên; mỗi chúng ta đều có gen từ cha mẹ của mình.

 export function crossover(first: Float32Array, second: Float32Array, prob = 0.25): Float32Array { return new Float32Array(first.map((w, i) => Math.random() < prob ? second[i] : w)) }

Đột biến:

Hàm đột biến hoạt động như sau: chúng ta lấy một tập hợp gen và với một mức độ xác suất nào đó, thêm một chút hỗn loạn vào đó. Một lần nữa, trong cuộc sống thực, mọi thứ đều hoạt động theo cùng một cách và mỗi chúng ta đều có những gen không có ở cha mẹ, nếu không, sẽ không có bệnh tật và các quá trình khó hiểu khác trong cơ thể chúng ta.

 export function mutate(master: Float32Array, prob = 0.25, delta = 0.5): Float32Array { return new Float32Array(master.map(w => Math.random() < prob ? w + (Math.random() * delta - (delta / 2)) : w)) }

Kết quả của mỗi giải đấu là chúng ta có một số đặc vụ may mắn hơn những người khác một chút (Trong thuật toán di truyền, mọi thứ đều được xây dựng trên cuộc sống của chúng ta, và một số may mắn hơn, một số thì kém hơn).

Và cuối cùng, chúng ta lấy danh sách những người rất may mắn này và so sánh chúng với nhau để tìm ra bộ gen tốt nhất cho trò chơi của mình và để dữ liệu không bị biến mất thì chúng ta phải nhớ lưu lại bộ gen này.

Khi có đủ số lượng bộ gen như vậy, chúng ta có thể xây dựng quần thể tác nhân dựa trên chúng. Tuy nhiên, mỗi bộ gen đều đã có một số hiểu biết về những gì nó cần làm.

 import * as fs from "fs"; import { playTournament } from "./play-tournament"; import { Network, createNew, crossover, mutate } from "shared"; import { playBattle } from "./play-battle"; import { AgentTrainer } from "./agent"; export async function tournaments( historySize: number, layers: number[] = [], epoch = 64, population = 32, best = false ) { const modelName = `${(historySize + 1) * 50}_${layers.join("_")}`; const modelPath = `../models/${modelName}`; /** * Create the model if it does not exist */ if (!fs.existsSync(modelPath)) { fs.mkdirSync(modelPath, { recursive: true }); } let topPlayerList = []; const topPlayerIds = new Set(); const bestModels = new Set(); let playerList: AgentTrainer[] = []; const baseLayers = []; let inp = historySize * 50 + 50; for (let i = 0; i < layers.length; i++) { baseLayers.push([inp, 1, layers[i]]); inp = layers[i]; } const baseNet = new Network(historySize * 50 + 50, 1, baseLayers); const topologySize = baseNet.getTopology().length; const size = baseNet.size() + topologySize; /** * Load the best models */ if (best) { const weights = fs .readdirSync(modelPath) .filter((file) => file.endsWith(".bin")); for (const weight of weights) { const buf = fs.readFileSync(`${modelPath}/${weight}`); const weights = new Float32Array(buf.buffer); const agent = new AgentTrainer(historySize * 50, weights); agent.age = 1; bestModels.add(agent.id); playerList.push(agent); topPlayerList.push(agent); topPlayerIds.add(agent.id); } const d = playerList.length; let ind = 0; /** * Create new players by crossover and mutation from the best models. * For the zero population, we need to ensure the greatest genetic diversity, than next populations. * This way we will get a larger number of potentially viable models, from which subsequent generations will be built in the future */ if (d > 1) { while (playerList.length < Math.max(population, d * 2)) { const playerA = playerList[ind]; const playerB = playerList[Math.floor(Math.random() * d)]; if (playerA && playerB && playerA.id !== playerB.id) { const newWeights = mutate( crossover(playerA.getWeights(), playerB.getWeights()) ); const weights = new Float32Array(size); weights.set(baseNet.getTopology()); weights.set(newWeights, topologySize); const agent = new AgentTrainer(historySize * 50, weights); playerList.push(agent); ind += 1; ind = ind % d; } } } } /** * Create the initial population */ while (playerList.length < population) { const w = createNew(baseNet.size(), 2); const weights = new Float32Array(size); weights.set(baseNet.getTopology()); weights.set(w, topologySize); const agent = new AgentTrainer(historySize * 50, weights); playerList.push(agent); } /** * Run the initial championship */ playerList = await playTournament(playerList); console.log( `0 ${playerList[0].id} (${playerList[0].age}) with ${playerList[0].score} points` ); let currentEpoch = 0; while (currentEpoch <= epoch) { /** * Keep the best 25% of the population */ playerList = playerList.slice(0, Math.floor(population / 4)); for (const player of playerList) { player.onNewEpoch(); /** * if the player is in the top 25% and has played at least one tournament, add it to the top players */ if (player.age > 1 && !topPlayerIds.has(player.id)) { topPlayerIds.add(player.id); topPlayerList.push(player); console.log("add top player", player.id, topPlayerList.length); } } const d = playerList.length; /** * Create new players by crossover and mutation */ let ind = 0; while (playerList.length < population) { const playerA = playerList[ind]; const playerB = playerList[Math.floor(Math.random() * d)]; if (playerA && playerB && playerA.id !== playerB.id) { const newWeights = mutate( crossover(playerA.getWeights(), playerB.getWeights()) ); const weights = new Float32Array(size); weights.set(baseNet.getTopology()); weights.set(newWeights, topologySize); const agent = new AgentTrainer(historySize * 50, weights); playerList.push(agent); ind += 1; ind = ind % d; } } /** * Run the championship */ playerList = await playTournament(playerList); currentEpoch += 1; console.log( `${currentEpoch} ${playerList[0].id} (${playerList[0].age}) with ${playerList[0].score} points` ); } /** * Add the top players to the list from championship */ for (const player of playerList) { if (player.age > 1 && !topPlayerIds.has(player.id)) { topPlayerIds.add(player.id); topPlayerList.push(player); console.log("add top player", player.id, topPlayerList.length); } } console.log("-----"); console.log(topPlayerList.length); console.log("-----"); /** * Reset agents */ for (const player of topPlayerList) { player.onNewEpoch(); } /** * Run the final championship */ topPlayerList = await playBattle(topPlayerList); let index = 1; for (const player of topPlayerList) { const code = bestModels.has(player.id) ? "\x1b[32m" : "\x1b[36m"; const reset = "\x1b[m"; console.log( `${code}${String(index).padStart(4, " ")} ${player.toString()}${reset}` ); index += 1; } /** * Save the best player */ while (topPlayerList[0] && bestModels.has(topPlayerList[0].id)) { /** * Remove the best player if it is already in the best models */ console.log("remove", topPlayerList[0].id); topPlayerList.shift(); } if (topPlayerList[0]) { let player = topPlayerList[0]; console.log(`${player.score} ${player.id}`); const weights = player.serialize(); console.log(weights.length, weights.length / 4); fs.writeFileSync(`${modelPath}/${player.id}.bin`, weights); } }

Kết quả

Để có được kết quả, tôi đã sử dụng những mẫu mới nhất và đây là kết quả:

Khi so sánh 2 mô hình mạng nơ-ron với nhau, chúng cho kết quả khá tốt mặc dù thực hiện những hành động phi logic.

Khi chơi giữa mạng nơ-ron và tìm kiếm alpha beta với độ sâu tìm kiếm là 1 bước, mạng nơ-ron có cơ hội chiến thắng khá cao.

Trong một trò chơi giữa mạng nơ-ron và tìm kiếm alpha beta với độ sâu tìm kiếm là 2 bước, mạng nơ-ron không có cơ hội và thua tất cả các trò chơi.

Tôi chưa nhìn sâu hơn vì nó vô nghĩa. Có thể sau nhiều trò chơi hơn, nó sẽ có thể tạo ra kết quả dễ chấp nhận hơn hoặc nếu bạn dạy mạng thần kinh chơi không phải với cùng một mạng mà với tác nhân tìm kiếm alpha-beta

Phần kết luận

Việc áp dụng các thuật toán di truyền vào trò chơi cờ đam cho thấy tiềm năng biến đổi của tính toán lấy cảm hứng từ sinh học. Trong khi các thuật toán chơi trò chơi truyền thống như Minimax và các biến thể của nó đã được chứng minh là có hiệu quả thì bản chất tiến hóa và thích ứng của GA mang đến một góc nhìn mới mẻ.

Cũng như tiến hóa sinh học, các chiến lược được phát triển thông qua phương pháp này có thể không phải lúc nào cũng phù hợp nhất. Tuy nhiên, nếu có đủ thời gian và điều kiện thích hợp, chúng có thể tiến hóa thành những đối thủ đáng gờm, thể hiện sức mạnh tính toán lấy cảm hứng từ thiên nhiên.

Cho dù bạn là người đam mê cờ đam, nhà nghiên cứu AI hay chỉ là người bị mê hoặc bởi sự hội tụ giữa cái cũ và cái mới, thì không thể phủ nhận rằng sự kết hợp của trò chơi lâu đời này với các thuật toán tiên tiến là một biên giới thú vị trong trí tuệ nhân tạo. .

Như thường lệ, tất cả mã được cung cấp trên GitHub