Tôi bắt máy tính làm nô lệ chơi Sokoban Pt1
Shiki
Shiki
September 22nd, 2026

Nếu bạn đã từng chơi các tựa game offline tuyến tính hay phi tuyến tính như Minecraft, Fall out 3, Factorio, ... thì bạn có bao giờ tự hỏi: "Mấy con bot ngu l*n của tụi nó hoạt động kiểu gì vậy nhỉ" chưa? Nếu chưa thì bây giờ mình sẽ hướng dẫn các bạn cách bóc lột một chiếc máy tính chơi một tựa game rất đơn giản là Sokoban để xem nó hoạt động kiểu gì nhé!

Sokoban là cái đéo gì?

Nếu bạn đã từng sở hữu những cỗ máy siêu khủng thời bấy giờ là cục gạch Nokia 1280, Nokia cái gì đấy idk,... thì chắc ít nhiều bạn cũng mò ra được cái trò đẩy thùng nhỉ, đó chính là Sokoban. Luật chơi rất đơn giản, bạn sẽ bị nhốt vào 1 cái mê cung với một vài cái thùng cực nặng (chắc chắn đựng mẹ bạn) và một số cái ô có chấm đỏ với số lượng tương ứng số thùng, nhiệm vụ của bạn là phải đẩy mọi cái thùng vào mọi ô có chấm đỏ, bạn chỉ được đẩy thùng khi hướng bạn đẩy cái thùng không đụng tường hay dính một cái thùng khác.

Luật chơi đơn giản mà nhỉ! Bây giờ chúng ta phải làm gì với mớ thông tin này? Ta sẽ dùng nó để bóc lột con Legion 5 Y7000P i7 14th, 16gb RAM và 4070 mobile của mình.

AI là cái đéo gì?

A.I hay Artifical Intelligent không chỉ bao gồm "Hãy tạo cho tui một hình gái alimi dú to đít bự" và nó tạo ra cho bạn một tấm ảnh, đó là một phần thuộc A.I tạo sinh, trong thực tế A.I rộng hơn như vậy rất nhiều.

Vậy Shiki, thế A.I là cái chó gì? \

Theo cách hiểu của mình thì A.I là cách bạn lập trình cho một chương trình để nó biết cách suy nghĩ như một kỹ sư, giải quyết một vấn đề bất kỳ nào đó.

Nhưng Shiki, cái đó là định nghĩa của thuật toán mà?

Chuẩn, A.I là thuật toán, vậy thui.

Vậy nếu chúng nó chỉ là thuật toán, chúng nó làm cách nào để chúng biết cách chơi cờ vua? làm thế nào để chúng nó biết cách giải toán, bla bla bla. Câu trả lời là không, chúng nó ngu bỏ mẹ. Chúng nó không biết cách giải, chính bạn phải dạy nó cách để giải hoặc cho nó tự bơi hàng chục triệu lần. Qua đâu? qua thuật toán. Nếu các bạn đã và đang học môn Trí tuệ nhân tạo ở đại học, bạn cũng biết lũ này chúng nó chạy theo ngữ cảnh và trạng thái. Vậy ngữ cảnh là cái đéo gì và trạng là cái đéo gì?

Trạng thái đơn giản chỉ là một bức ảnh chứa thông tin toàn bộ hoàn cảnh của bài toán ngay tại thời điểm đó. Ví dụ trên bàn cơ vua "Trở lại ván cờ thực tế 🗣️🔥🔥. Sau bước hậu B6 tấn công tượng, trắng nên đẩy tốt A4 bảo vệ tượng..." đây là một trạng thái, nó chỉ ra tại thời điểm này quân hậu đang nằm ở B6 và lăm le húp em tượng múp rụp.

Ngữ cảnh là những dữ liệu lịch sử hoặc thông tin môi trường đi kèm để A.I hiểu cái trạng thái hiện tại có ý nghĩa như thế nào, như ví dụ ở trên, ngữ cảnh chính là toàn bộ bạn cờ tại trạng thái đó.

Nói chung là code ngu thì nó chạy chậm hoặc treo mẹ máy, code thuật khôn khôn tý là nó chạy cái vèo.

Dạy một con A.I chơi Sokoban

Ok, giờ mới tới phần chính sau mớ lý thuyết giới thiệu khô khan ở trên nè, ta sẽ tạo ra một con A.I và dạy nó cách để giải Sokoban với tiêu chí tốn ít bước đi nhất có thể nhen, gét gâu

Thiết lập trạng thái

Để quen thuộc với bản thân mình cũng như viết ngắn hơn thì mình sẽ gọi Trạng thái là StateState nhé. Để hành xác con máy của mình và cho nó chơi Sokoban, mình sẽ dùng State-space search để thực hiện. State-space search là gì? Nó là một kỹ thuật để từ StateState bạn sẽ sinh ra một loạt các StateState con có thể có StateState và cách di chuyển của nó. Ví dụ ở State(A)State(A) con hậu đang ở B6 và lăm le húp em tượng múp rụp thì ở StateState con của nó sẽ có một StateState là con hậu húp em tượng múp rụp.

Giờ chúng ta sẽ đi xác định State space cho nó. Chúng ta sẽ mô hình hoá bài toán bao gồm các tác nhân và hành vi của chúng.

  • Initial State (S0)(S_0): StateState được thể hiện bằng một lưới toạ độ, các thành phần của trạng thái (như vị trí của Player, vị trí mấy cái hộp, ...) có thể được truy cập một cách trực tiếp và được thể hiện bằng một cặp toạ độ (x,y)(x, y) vao gồm.
    • Vị trí ban đầu của Player: (x,y)(x, y)
    • Vị trí của mấy cái hộp: vector<(x, y)>
  • Goal State (Sn)(S_n): là StateState mà vị trí của mấy cái hộp là một tập hơn con của tập hợp vị trí các cái đích. Thứ tự của mấy cái thùng không quan trọng vì cứ đẩy vào điểm đích hết là thắng mà.
  • Actions (A)(A): Là những cách mà con Agent có thể hành động trong một trạng thái. Trong ngữ cảnh Sokoban thì Agent có thể đi lên, đi xuống, sang trái, sang phải: Move(Up),Move(Down),Move(Left),Move(Right)Move(Up), Move(Down), Move(Left), Move(Right)
  • Transition Model: Cái này dùng để miêu tả sự thay đổi về ngữ cảnh, môi trường này sang ngữ cảnh, môi trường khác khi Agent thực hiện một hành động, ta sẽ lấy Sokoban đang làm để ví dụ nhé:
    • Cho trạng thái SS và một hành động a∈Aa \in A, hàm thay đổi RESULT(S,aS, a) trả về một trạng thái S′S' dựa trên luật chơi đã có. Cho PP là vị trí của con agent trong state hiện tại và P′P' là vị trí lân cận trong lưới toạ độ cùng hướng với aa (Ví dụ nếu S=(1,2)S = (1, 2) và a=Move(Up)a = Move(Up) thì P′=(1,1)P' = (1, 1)):
      • Case 1 (Ô trống hoặc là đích): Nếu P′P' là một ô trống không có vật cản thì con agent cứ thế mà đi. Vị trí agent trong S′S' sẽ được cập nhật theo P′P'. Các ô còn lại không thay đổi.
      • Case 2 (Đụng tường): Nếu P′P' là tường thì agent không được đi. Giữ nguyên trạng thái hiện tại hay S′=SS' = S.
      • Case 3 (Đụng thùng) cái này mới là phần vui nè, ta sẽ gọi P′′P'' là vị trí thùng sau khi bị đẩy theo hướng aa:
        • Subcase 3-1 (Ô trống hoặc đích): Nếu P′′P'' là một ô trống hoặc đích thì tương tự Case 1, ta sẽ cập nhật vị trí của agent vào S′S' theo P′P' và cập nhật vị trí của cái thùng bị đẩy theo P′′P''.
        • Subcase 3-2 (Đụng tường): Nếu P′′P'' là tường thì cái thùng không thể bị đẩy, cho nên agent sẽ không làm gì cả, giữ nguyên trạng thái S′=SS' = S.
  • Path Cost: đây là chi phí để bạn thực hiện một bước di chuyển, do mỗi trạng thái bạn chỉ được di chuyển một lần nên cost=1cost = 1 hay cụ thể hơn là c(s,a,s′)=1c(s,a,s') = 1 (chi phí để di chuyển trạng thái SS theo hướng aa tới S′S' bằng 11)

Xây dựng mẫu dữ liệu

Để có thể mô phỏng bàn cờ như sau:

Map(Bản đồ Sokoban)

Sang dạng dữ liệu máy tính có thể xử lý được, mình sẽ convert nó sang dạng chuỗi theo quy luật sau:

  %%%%%
%%%   %
%DAB  %
%%% BD%
%D%%B %
% % D %%
%B CBBD%
% D    %
%%%%%%%%
  • %: tường.
  • A: vị trí của agent.
  • B: vị trí của thùng.
  • C: cũng vị trí cái thùng nhưng cũng vừa là đích (là nó tự ở đích luôn rồi á).
  • D: vị trí của đích.

Hiện thực mô hình

Sau khi nói lý thuyết chán chê rồi ta sẽ bắt đầu thực hành! Chúng ta sẽ cài đặt lớp StateState

state.hpp
struct Coord {
	int x;
	int y;
 
	bool operator==(const Coord& other) const {
		return x == other.x && y == other.y;
	}
};
 
class State {
private:
	Coord player_position;
	vector<Coord> box_positions;
	vector<Coord> walls;
	vector<Coord> goal_positions;
public:
	void add_wall(const Coord& pos) { 
		this->walls.push_back(pos); 
	};
 
	void add_box(const Coord& pos) {
		this->box_positions.push_back(pos);
	};
	
	void add_goal(const Coord& pos) {
		this->goal_positions.push_back(pos);
	};
 
	void set_player_position(const Coord& position) {
		this->player_position = position;
	};
}

Tiếp theo mình sẽ viết một lớp Map để có thể parse map và quẳng vào cho State

map.hpp
class Map {
public:
	static State parse_map(const std::string filenames);
};

Ở đây Map sẽ đóng vai trò như một parser, đọc input từ file và đưa dữ liệu vào State

map.cpp
State Map::parse_map(const std::string filenames) {
	std::ifstream map(filenames);
	State state;
 
	if (!map.is_open()) {
		throw std::runtime_error("Could not open map file: " + filenames);
	}
 
	std::string line;
	int deepness = 0;
 
	while(std::getline(map, line)) {
		for (size_t i = 0; i < line.size(); ++i) {
			char c = line[i];
			Coord curr_coord(i, deepness);
			switch (c) {
			case '%':
				state.add_wall(curr_coord);
				break;
			case 'A':
				state.set_player_position(curr_coord);
				break;
			case 'B':
				state.add_box(curr_coord);
				break;
			case 'C':
				state.add_box(curr_coord);
				state.add_goal(curr_coord);
				break;
			case 'D':
				state.add_goal(curr_coord);
				break;
			default:
				break;
			}
		}
		deepness++;
	}
 
	return state;
}

Như vậy là ta đã cài đặt xong lớp State và Map.

Tìm kiếm

Nh-nh-nhưng Shiki, mày chỉ mới cài các lớp bình thường thôi mà! nó có làm cái chó gì đâu!

Đúng là vậy, để cho A.I giải Sokoban thì thứ ta cần chính là thuật toán. Hiện tại có nhiều kỹ thuật để giải nhưng lần này mình sẽ dùng Search để phù hợp với State space Search nhé.

Trước khi mình nói sâu vào Search thì mình sẽ tạo trước một lớp cha là SearchStrategy, chi tý biết kkkkkk.

search_strategy.hpp
struct GoalState {
	int cost;
	vector<string> path;
};
 
class SearchStrategy {
public:
	// Return cost and path to goal state
	virtual GoalState search(const State& initial_state) {
		return {0, vector<std::string>()};
	}
 
	virtual ~SearchStrategy() = default;
};

Oke, vậy search hoạt động như thế nào trong bài toán này? Mục đích rất đơn giản, đó là tìm Goal State.

Nhưng tìm bằng cách nào? Nếu bạn còn nhớ ở phần mô hình hoá, mình có nói về Actions. Nếu bạn đoán ra mình sắp làm gì thì chúc mừng bạn! Bạn khá nhạy bén đấy, còn nếu không thì việc mình sắp làm đó chính là sinh ra toàn bộ những khả năng mà một trạng thái có thể có, đi vào từng trạng thái một và lại tiếp tục sinh ra toàn bộ những khả năng mà trạng thái đó có dựa vào hàm Actions cho đến khi tìm ra Goal State.

Đơn giản đúng chứ? bây giờ ta sẽ thực hiện hàm sinh các trạng thái con nhen.

state.hpp
struct Successor;
 
class State {
public:
    //...
    static vector<Successor> get_successor(const State& current_state);
}
 
struct Successor {
    string action;
    State state;
    int cost;
};
state.cpp
vector<Successor> State::get_successors(const State& current_state) {
	vector<pair<string, Coord>> directions = {
		{"Down", {0, 1}},
		{"Right", {1, 0}},
		{"Up", {0, -1}},
		{"Left", {-1, 0}}
	};
	vector <Successor> successors;
 
	for (const auto& [action, delta] : directions) {
		// P'
		Coord new_player_pos(current_state.player_position.x + delta.x, current_state.player_position.y + delta.y);
		State new_state = current_state;
 
		// Hitting wall
		auto wall_it = std::find(current_state.walls.begin(), current_state.walls.end(), new_player_pos);
		if (wall_it != current_state.walls.end()) {
			continue;
		}
 
		// Hitting box
		auto box_it = std::find(current_state.box_positions.begin(), current_state.box_positions.end(), new_player_pos);
		if (box_it != current_state.box_positions.end()) {
			// P''
			Coord new_box_pos(new_player_pos.x + delta.x, new_player_pos.y + delta.y);
 
			// Hitting wall or box
			auto wall_it2 = std::find(current_state.walls.begin(), current_state.walls.end(), new_box_pos);
			if (wall_it2 != current_state.walls.end()) {
				continue;
			}
			auto box_it2 = std::find(current_state.box_positions.begin(), current_state.box_positions.end(), new_box_pos);
			if (box_it2 != current_state.box_positions.end()) {
				continue;
			}
 
			auto index = std::distance(current_state.box_positions.begin(), box_it);
 
			// Update box position
			new_state.box_positions[index] = new_box_pos;
		}
 
		// Update player position
		new_state.player_position = new_player_pos;
		successors.push_back(Successor(action, new_state, 1));
	}
	return successors;
}

Như đã nói, hàm ở phía trên sẽ sinh một mảng các trạng thái S′S' có thể có của một trạng thái bất kỳ. Đây là một hàm tiên quyết để các thuật toán Search của chúng ta có thể hoạt động hiệu quả. Vậy câu hỏi đặt ra ở đây là, ta dùng thuật toán tìm kiếm nào?

Mình nói thẳng luôn thằng cu này là Dijkstra nhưng được đổi tên. Nếu bạn đã quen thuộc với Dijkstra thì mình nghĩ bạn sẽ nhanh chóng học được về Uniformed Cost Search hay UCS thôi vì hai thằng này là một mà xD

Thuật toán UCS hay Dijkstra đè tem là thuật giúp bạn tìm con được với chi phí là nhỏ nhất trên một đồ thị có trọng số đi từ A đến B. Thằng này sẽ luôn ưu tiên đi tìm vào thằng có trọng số nhỏ nhất trước rồi mới đến những thằng khác cho nên trong thuật toán này, Heap sẽ là bạn thân của bạn với khả năng bóc minheap trong O(1)O(1) đấy.

Nhưng, với Sokoban hoặc các bài toán khác có trọng số bằng 11, thuật toán UCSUCS sẽ thoái hoá về lại BFS nên thay vì dùng Priority Queue thì ta chỉ cần dùng Queue thôi

UCS.cpp
struct Node {
	State state;
	vector<string> path;
};
 
GoalState UCS::search(const State& initial_state) {
	std::queue <Node> frontier;
	frontier.push({ initial_state, {} });
	std::set<State> explored;
 
	int nodeExplored = 0;
	int nodeGenerated = 1;
 
	while (!frontier.empty()) {
		Node curr_node = frontier.front();
		frontier.pop();
 
		nodeExplored++;
 
		// Check if current state is goal state
		bool is_goal = true;
		const auto& box_positions = curr_node.state.get_box_positions();
		const auto& goal_positions = curr_node.state.get_goal_positions();
 
		explored.insert(curr_node.state);
 
		for (const auto& box : box_positions) {
			if (std::find(goal_positions.begin(), goal_positions.end(), box) == goal_positions.end()) {
				is_goal = false;
				break;
			}
		}
 
		if (is_goal) {
			return { static_cast<int>(curr_node.path.size()), curr_node.path, nodeExplored, nodeGenerated};
		}
 
		for (const auto& successor : State::get_successors(curr_node.state)) {
			if (explored.find(successor.state) == explored.end()) {
				nodeGenerated++;
				explored.insert(successor.state);
				vector<string> new_path = curr_node.path;
				new_path.push_back(successor.action);
				frontier.push({ successor.state, new_path});
			}
		}
	}
 
	return { -1, vector<string>(), nodeExplored, nodeGenerated };
}

Vậy là ta build xong thuật toán UCS rồi! Chạy thử xem nó như thế nào và tốn bao nhiêu thời gian nhé.

-----------------------------------------------------
Benchmark           Time             CPU   Iterations
-----------------------------------------------------
BM_UCS          66835 ms        59344 ms            1

Hah?

Sao nó chậm dữ z ta.... Thật tế, nếu bạn để ý kỹ thì bạn đếm xem spam ta đã spam std::find() bao nhiêu lần nhé. Ta sẽ nhìn lại mã nguồn một chút

state.cpp
vector<Successor> State::get_successors(const State& current_state) {
    // ...
 
	for (const auto& [action, delta] : directions) {
        // ...
 
		auto wall_it = std::find(current_state.walls.begin(), current_state.walls.end(), new_player_pos);
 
		auto box_it = std::find(current_state.box_positions.begin(), current_state.box_positions.end(), new_player_pos);
		if (box_it != current_state.box_positions.end()) {
            //...
			auto wall_it2 = std::find(current_state.walls.begin(), current_state.walls.end(), new_box_pos);
            
            //...
			auto box_it2 = std::find(current_state.box_positions.begin(), current_state.box_positions.end(), new_box_pos);
  
            //...
		}
 
        //...
	}
	return successors;
}

Chỉ riêng get_successors() thì ta đã gọi std::find() tới tận 4 lần, trong đó nhân vật có thể di chuyển theo 4 hướng khác nhau, làm phép tính nho nhỏ thì chỉ riêng get_successors() đã gọi std::find() ít nhất 4∗4=164 * 4 = 16 lần với một hàm có độ phức tạp là O(N)O(N), khá là.... đắt đỏ nhỉ. Vậy có cách nào để khắc phục đều này hay không?

Câu trả lời là có, bạn hãy nhìn lại mớ dữ liệu ban đầu và trả lời cho mình câu hỏi này nhé. Dữ liệu nào là dữ liệu động, luôn thay đổi trong suốt vòng đời của chương trình và dữ liệu nào là dữ liệu tĩnh, không thay đổi trong suốt quá trình chạy?

| Dữ liệu động | Dữ liệu tĩnh | |--------------|--------------| | agent_position | walls | | box_positions | goal_positions |

Như bảng trên đã thể hiện, walls và goal_positions là hai dữ liệu tĩnh không thấy đổi trong suốt quá trình chương trình chạy. Thay vì ta lưu toạ độ cụ thể của nó như ban đầu

state.hpp
class State {
private:
	Coord player_position;
	vector<Coord> box_positions;
	vector<Coord> walls;
	vector<Coord> goal_positions;
    // ...
}

Thì ta có thể biểu diễn walls và goal_positions dưới dạng một lưới toạ độ 2D kiểu boolean. Như vậy thay vì ta phải gọi std::find() với O(N)O(N) thì ta chỉ cần kiểm tra bằng goal_positions[curr_node.pos.x][curr_node.pos.y] với O(1)O(1)!

state.hpp
struct MapInfo {
    vector<vector<bool>> walls;
    vector<vector<bool>> goal_positions;
}

Chỉnh sửa lại cách map đọc input

map.hpp
pair<State, MapInfo> Map::parse_map(const std::string filenames) {
    // ...
 
	std::string line;
	int y = 0;
 
	while(std::getline(mapInput, line)) {
		vector<bool> wall_row(line.size(), false);
		vector<bool> goal_row(line.size(), false);
 
		for (size_t x = 0; x < line.size(); ++x) {
			char c = line[x];
			Coord curr_coord(x, y);
			switch (c) {
			case '%':
				wall_row[x] = true;
				break;
			case 'A':
				state.set_player_position(curr_coord);
				break;
			case 'B':
				state.add_box(curr_coord);
				break;
			case 'C':
				state.add_box(curr_coord);
				goal_row[x] = true;
				break;
			case 'D':
				goal_row[x] = true;
				break;
			default:
				break;
			}
		}
 
		map.goal_positions.push_back(goal_row);
		map.walls.push_back(wall_row);
		y++;
	}
 
	return { state, map };

Bây giờ ta chỉ cần thay thế std::find() trong các hàm chức năng khác. Tuy nhiên, để đạt được hiệu xuất cao hơn nữa, mình muốn tối ưu thêm một chút ở get_successors().

Cụ thể hơn, khi sinh trạng thái, đôi khi sẽ có những nhánh mà những cái thùng hoặc người chơi ở trạng thái gọi là trạng thái chết, tức là trạng thái không thể thắng dù có tìm sâu như thế nào đi nữa. Khi đó nếu không có một hàm bắt cái này thì UCS của bạn sẽ đi sâu vào những nhánh không cần thiết này và vô hình chung tăng thời gian chạy của con bot của bạn. Cho nên ta sẽ viết thêm một hàm kiểm tra như sau:

state.cpp
bool State::is_deadlock(const Coord& box_pos, const MapInfo& map) {
	// Check if the box is in a corner (not on a goal position)
	if (!map.goal_positions.at(box_pos.y).at(box_pos.x)) {
		bool up_wall = map.walls.at(box_pos.y - 1).at(box_pos.x);
		bool down_wall = map.walls.at(box_pos.y + 1).at(box_pos.x);
		bool left_wall = map.walls.at(box_pos.y).at(box_pos.x - 1);
		bool right_wall = map.walls.at(box_pos.y).at(box_pos.x + 1);
		if ((up_wall && left_wall) || (up_wall && right_wall) || (down_wall && left_wall) || (down_wall && right_wall)) {
			return true;
		}
	}
	return false;
}

Và đây là kết quả khi chạy thử:

--------------------------------------------------------------
Benchmark                    Time             CPU   Iterations
--------------------------------------------------------------
BM_UCS/iterations:1       4622 ms         4594 ms            1

Cũng tương đối đúng chứ dù không quá nhanh, tuy nhiên nó đã giải xong một màn Sokoban với mức thời gian tạm chấp nhận được là 5s.

Tổng kết

Như vậy bạn đã có một con agent có thể chơi Sokoban rồi đó! Dù không nhanh lắm do mình viết C++ như dái. Tuy nhiên thuật toán ta đang dùng là UCS aka một giải thuật tìm kiếm không thông tin cho nên nó phải đi sâu vào từng nhánh để tìm.

Ở bài sau chúng ta sẽ có một thuật toán khác mà thay vì phải tự mò đường thì sẽ có một người khác dẫn đường cho đó. Chúc bạn lập trình vui vẻ.

Back to Home