پرش به محتویات

بازی‌ها روی گراف‌های دلخواه

فرض کنید یک بازی توسط دو بازیکن روی یک گراف دلخواه $G$ انجام می‌شود. یعنی، وضعیت فعلی بازی یک رأس مشخص است. بازیکنان به نوبت حرکت می‌کنند و از رأس فعلی به یک رأس مجاور با استفاده از یک یال متصل‌کننده حرکت می‌کنند. بسته به بازی، شخصی که قادر به حرکت نباشد، یا بازی را می‌برد یا می‌بازد.

ما عمومی‌ترین حالت، یعنی حالت یک گراف جهت‌دار دلخواه با دور را در نظر می‌گیریم. وظیفه ما این است که با توجه به یک وضعیت اولیه، مشخص کنیم که اگر هر دو بازیکن با استراتژی‌های بهینه بازی کنند چه کسی برنده می‌شود یا تعیین کنیم که نتیجه بازی مساوی خواهد بود.

ما این مسئله را به صورت بسیار کارآمد حل خواهیم کرد. ما راه حل را برای تمام رئوس شروع ممکن گراف در زمان خطی نسبت به تعداد یال‌ها پیدا خواهیم کرد: $O(m)$.

توضیح الگوریتم

یک رأس را رأس برنده می‌نامیم، اگر بازیکنی که از این وضعیت شروع می‌کند، در صورت بازی بهینه (صرف نظر از حرکات بازیکن دیگر)، بازی را ببرد. به طور مشابه، یک رأس را رأس بازنده می‌نامیم، اگر بازیکنی که از این رأس شروع می‌کند، در صورت بازی بهینه حریف، بازی را ببازد.

برای برخی از رئوس گراف، از قبل می‌دانیم که آن‌ها رئوس برنده یا بازنده هستند: یعنی تمام رئوسی که هیچ یال خروجی ندارند.

همچنین قوانین زیر را داریم:

  • اگر یک رأس، یال خروجی‌ای داشته باشد که به یک رأس بازنده منتهی شود، آنگاه خود رأس یک رأس برنده است.
  • اگر تمام یال‌های خروجی یک رأس مشخص به رئوس برنده منتهی شوند، آنگاه خود رأس یک رأس بازنده است.
  • اگر در مرحله‌ای، هنوز رئوس تعریف‌نشده‌ای وجود داشته باشند که هیچ‌کدام از قوانین اول و دوم برایشان صدق نکند، آنگاه بازی از هر یک از این رئوس، در صورت بازی بهینه هر دو بازیکن، به تساوی ختم خواهد شد.

بنابراین، می‌توانیم فوراً الگوریتمی تعریف کنیم که در زمان $O(n m)$ اجرا می‌شود. ما تمام رئوس را پیمایش می‌کنیم و سعی می‌کنیم قانون اول یا دوم را اعمال کنیم و این کار را تکرار می‌کنیم.

با این حال، می‌توانیم این فرآیند را تسریع کرده و پیچیدگی را به $O(m)$ کاهش دهیم.

ما تمام رئوسی را که در ابتدا می‌دانیم وضعیت برنده یا بازنده دارند، پیمایش می‌کنیم. برای هر یک از آنها، یک جستجوی اول عمق (DFS) را شروع می‌کنیم. این DFS روی یال‌های معکوس به عقب حرکت خواهد کرد. اول از همه، وارد رئوسی که قبلاً به عنوان برنده یا بازنده تعریف شده‌اند، نمی‌شود. علاوه بر این، اگر جستجو از یک رأس بازنده به یک رأس تعریف‌نشده برود، آنگاه آن را به عنوان یک رأس برنده علامت‌گذاری می‌کنیم و DFS را با استفاده از این رأس جدید ادامه می‌دهیم. اگر از یک رأس برنده به یک رأس تعریف‌نشده برویم، باید بررسی کنیم که آیا تمام یال‌های خروجی از آن به رئوس برنده منتهی می‌شوند یا خیر. می‌توانیم این بررسی را با ذخیره کردن تعداد یال‌هایی که به یک رأس برنده منتهی می‌شوند برای هر رأس، در زمان $O(1)$ انجام دهیم. بنابراین اگر از یک رأس برنده به یک رأس تعریف‌نشده برویم، شمارنده را افزایش می‌دهیم و بررسی می‌کنیم که آیا این عدد برابر با تعداد یال‌های خروجی است یا خیر. اگر چنین باشد، می‌توانیم این رأس را به عنوان یک رأس بازنده علامت‌گذاری کرده و DFS را از این رأس ادامه دهیم. در غیر این صورت، هنوز نمی‌دانیم که این رأس، یک رأس برنده است یا بازنده، و بنابراین ادامه دادن DFS با استفاده از آن منطقی نیست.

در مجموع، ما هر رأس برنده و هر رأس بازنده را دقیقاً یک بار بازدید می‌کنیم (رئوس تعریف‌نشده بازدید نمی‌شوند)، و هر یال را نیز حداکثر یک بار پیمایش می‌کنیم. از این رو، پیچیدگی $O(m)$ است.

پیاده‌سازی

در اینجا پیاده‌سازی چنین DFS آمده است. ما فرض می‌کنیم که متغیر adj_rev لیست مجاورت گراف را به صورت معکوس ذخیره می‌کند، یعنی به جای ذخیره یال $(i, j)$ از گراف، ما $(j, i)$ را ذخیره می‌کنیم. همچنین برای هر رأس فرض می‌کنیم که درجه خروجی آن از قبل محاسبه شده است.

vector<vector<int>> adj_rev;

vector<bool> winning;
vector<bool> losing;
vector<bool> visited;
vector<int> degree;

void dfs(int v) {
    visited[v] = true;
    for (int u : adj_rev[v]) {
        if (!visited[u]) {
            if (losing[v])
                winning[u] = true;
            else if (--degree[u] == 0)
                losing[u] = true;
            else
                continue;
            dfs(u);
        }
    }
}

مثال: «پلیس و دزد»

در اینجا یک مثال عینی از چنین بازی‌ای آورده شده است.

یک صفحه $m \times n$ وجود دارد. ورود به برخی از خانه‌ها ممکن نیست. مختصات اولیه افسر پلیس و دزد مشخص است. یکی از خانه‌ها خروجی است. اگر پلیس و دزد در هر لحظه در یک خانه قرار بگیرند، پلیس برنده می‌شود. اگر دزد در خانه خروجی باشد (بدون اینکه پلیس نیز در آن خانه باشد)، دزد برنده می‌شود. پلیس می‌تواند در هر ۸ جهت حرکت کند، دزد فقط در ۴ جهت (در امتداد محورهای مختصات). هم پلیس و هم دزد به نوبت حرکت خواهند کرد. با این حال، آنها می‌توانند در صورت تمایل یک نوبت را رد کنند. اولین حرکت توسط پلیس انجام می‌شود.

اکنون گراف را می‌سازیم. برای این کار باید قوانین بازی را رسمی‌سازی کنیم. وضعیت فعلی بازی با مختصات افسر پلیس $P$، مختصات دزد $T$ و همچنین اینکه نوبت چه کسی است، تعیین می‌شود، بیایید این متغیر را $P_{\text{turn}}$ بنامیم (که وقتی نوبت پلیس است، مقدارش true است). بنابراین یک رأس از گراف با سه‌تایی $(P, T, P_{\text{turn}})$ تعیین می‌شود. سپس گراف را می‌توان به راحتی، تنها با پیروی از قوانین بازی، ساخت.

در مرحله بعد باید تعیین کنیم که کدام رئوس در ابتدا برنده و کدام بازنده هستند. اینجا یک نکته ظریف وجود دارد. رئوس برنده/بازنده علاوه بر مختصات، به $P_{\text{turn}}$ - یعنی نوبت چه کسی است - نیز بستگی دارند. اگر نوبت پلیس باشد، آنگاه رأس یک رأس برنده است اگر مختصات پلیس و دزد منطبق باشد، و رأس یک رأس بازنده است اگر برنده نباشد و دزد در رأس خروجی باشد. اگر نوبت دزد باشد، آنگاه رأس یک رأس بازنده است اگر مختصات دو بازیکن منطبق باشد، و یک رأس برنده است اگر بازنده نباشد و دزد در رأس خروجی باشد.

تنها نکته قبل از پیاده‌سازی این است که باید تصمیم بگیرید که آیا می‌خواهید گراف را به صراحت بسازید یا آن را در لحظه (on the fly) ایجاد کنید. از یک طرف، ساختن صریح گراف بسیار آسان‌تر است و احتمال اشتباه کمتر است. از طرف دیگر، این کار میزان کد را افزایش می‌دهد و زمان اجرا کندتر از زمانی خواهد بود که گراف را در لحظه بسازید.

پیاده‌سازی زیر گراف را به صراحت می‌سازد:

struct State {
    int P, T;
    bool Pstep;
};

// [موقعیت پلیس][موقعیت دزد][نوبت پلیس]
vector<State> adj_rev[100][100][2]; 
bool winning[100][100][2];
bool losing[100][100][2];
bool visited[100][100][2];
int degree[100][100][2];

void dfs(State v) {
    visited[v.P][v.T][v.Pstep] = true;
    for (State u : adj_rev[v.P][v.T][v.Pstep]) {
        if (!visited[u.P][u.T][u.Pstep]) {
            if (losing[v.P][v.T][v.Pstep])
                winning[u.P][u.T][u.Pstep] = true;
            else if (--degree[u.P][u.T][u.Pstep] == 0)
                losing[u.P][u.T][u.Pstep] = true;
            else
                continue;
            dfs(u);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<string> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];

    for (int P = 0; P < n*m; P++) {
        for (int T = 0; T < n*m; T++) {
            for (int Pstep = 0; Pstep <= 1; Pstep++) {
                int Px = P/m, Py = P%m, Tx = T/m, Ty = T%m;
                if (a[Px][Py]=='*' || a[Tx][Ty]=='*')
                    continue;

                bool& win = winning[P][T][Pstep];
                bool& lose = losing[P][T][Pstep];
                if (Pstep) {
                    win = Px==Tx && Py==Ty;
                    lose = !win && a[Tx][Ty] == 'E';
                } else {
                    lose = Px==Tx && Py==Ty;
                    win = !lose && a[Tx][Ty] == 'E';
                }
                if (win || lose)
                    continue;

                State st = {P,T,!Pstep};
                adj_rev[P][T][Pstep].push_back(st);
                st.Pstep = Pstep;
                degree[P][T][Pstep]++;

                const int dx[] = {-1, 0, 1, 0, -1, -1, 1, 1};
                const int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
                for (int d = 0; d < (Pstep ? 8 : 4); d++) {
                    int PPx = Px, PPy = Py, TTx = Tx, TTy = Ty;
                    if (Pstep) {
                        PPx += dx[d];
                        PPy += dy[d];
                    } else {
                        TTx += dx[d];
                        TTy += dy[d];
                    }

                    if (PPx >= 0 && PPx < n && PPy >= 0 && PPy < m && a[PPx][PPy] != '*' &&
                        TTx >= 0 && TTx < n && TTy >= 0 && TTy < m && a[TTx][TTy] != '*')
                    {
                        adj_rev[PPx*m+PPy][TTx*m+TTy][!Pstep].push_back(st);
                        ++degree[P][T][Pstep];
                    }
                }
            }
        }
    }

    for (int P = 0; P < n*m; P++) {
        for (int T = 0; T < n*m; T++) {
            for (int Pstep = 0; Pstep <= 1; Pstep++) {
                if ((winning[P][T][Pstep] || losing[P][T][Pstep]) && !visited[P][T][Pstep])
                    dfs({P, T, (bool)Pstep});
            }
        }
    }

    int P_st, T_st;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i][j] == 'P')
                P_st = i*m+j;
            else if (a[i][j] == 'T')
                T_st = i*m+j;
        }
    }

    if (winning[P_st][T_st][true]) {
        cout << "پلیس دزد را می‌گیرد"  << endl;
    } else if (losing[P_st][T_st][true]) {
        cout << "دزد فرار می‌کند" << endl;
    } else {
        cout << "مساوی" << endl;
    }
}