Có thể hiểu đơn giản các bài toán dạng này như dạng đồ thị :

Cho đồ thị có hướng G=(V,E) (Đồ thị G có tập đỉnh V, tập cạnh là E). Với mỗi đỉnh

Một trò chơi hai người được định nghĩa là một đồ thị có hướng G = (V, E) trong đó mỗi trạng thái chơi tương ứng với một đỉnh của đồ thị, hàm E(v) là qui tẵc chơi tức là E(v) chứa các đỉnh hay trạng thái chơi mà từ v có thể đi đến. Hai người luân phiên nhau đi , ở thế chơi u người chơi chỉ có thể đi sao cho nước v nhận được thoả mãn . Trò chơi kết thúc khi đến lượt đấu mà không thể đi tiếp được nữa. (Thông thường thì người không thể đi tiếp là người thua cuộc).

Và cách xử lý những bài dạng này cũng trở nên đơn giản hơn. Chúng ta cùng xét một ví dụ cụ thể như sau:

Bài toán: Hai người luân phiên nhau điều khiển một con tốt theo một số con cho trước. Một người có thể di chuyển con tốt từ vị trí u đến v nếu có một đường nối trực tiếp có hướng từ u đến v. Trò chơi kết thúc không thể tiếp tục di chuyển. Người không thể tiếp tục đi là người thua cuộc. Hỏi nếu cho trước vị trí ban đầu và danh sách các đường nối hỏi người đi trước thắng hay người đi sau thắng hay cả hai hoà? Giả sử rằng hai người này rất thông minh các bước đi của họ là tối ưu (tức cả hai người không bao giờ đi các nước không có lợi cho mình).

Input:

- Dòng đầu ghi số N là số vị trí con tốt có thể đừng, và số M là số đường đi (có hướng) mà con tốt có thể đi (1≤ N ≤ 200, 1 ≤ M ≤ N*(N-1)).
- Dòng thứ hai ghi u là trạng thái bắt đầu.
- M dòng tiếp theo mỗi dòng ghi hai số u, v mô tả một đường đi từ u đến v.

Output:

- Ghi một số duy nhất 1, 2, hoặc 0. 1 nghĩa là người 1 thắng, 2 là người hai thắng, 0 là hoà.

Nhận xét:
- Những vị trí không có đường ra thì chắc chắn sẽ thua.
- Những vị trí nào có một đường ra nối với vị trí chắc chắn thua thì chắc chắn thắng.
- Những vị trí nào tất đường ra nối với các vị trí chắc chắn thắng thì chắc chắn thua.
- Những vị trí nào mà trạng thái thắng thua không thể xác định thì là vị trí hoà.

- Bài toán có trạng thái hoà: VD: có các đường nối 1 → 2, 2 → 3, 3 → 1, 1 → 4, 4 → 5.Các vị trí 1,2,3 sẽ hòa, 5 thua, 4 thắng.

Thuật toán:
- Lúc đầu coi tất cả các vị trí v đều hoà gán giá trị đỉnh F[v] = 0. Tìm các vị trí không có đường ra thì gán lại F[v] = 2 (tức là nếu người chơi ở vị trí này sẽ thua).

- Khi thay trạng thái một vị trí từ hoà sang thắng hoặc thua thì kiểm tra các vị trí có đường đi đến nó: Những vị trí u nào có một đường ra nối với vị trí v chắc chắn thua (F[v] = 2) sẽ thì chắc chắn thắng (thay F = 1); Những vị trí u nào tất đường ra nối với các vị trí v (F[v] = 1) chắc chắn thắng thì chắc chắn thua (thay F = 2).
- Quá trình này ngừng khi không có sự chuyển trạng nào nữa.

Chương trình mô tả thuật toán:

procedure gan_nhan (u: byte);

var td, v : byte;

begin

td := 0;

if t then td := 1 else // t là trạng thái người chơi ở vị trí chắc thắng

if (vị trí không có đường ra, hoặc chắc chắn thua) then td := 2;

F := td;

if td <> 0 then

for v := 1 to N do

if F[v] = 0 then

if C[v, u] then gan_nhan (td);

End;

procedure Main;

var u : Integer;

Begin

Fillchar (F, sizeof (F), 0);

for u := 1 to N do

if Khong_Co_Canh_Ra (u) then Gan_nhan(u);

end;

School@net