GKTTNT.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/trucni2005/ECom/blob/master/GKTTNT.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "HEvB2JxfhiKt",
        "outputId": "37434ed5-24e3-4123-a3db-dcb85064d3b8"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "+ 0 1 2 3 4 5 6 7 +\n",
            "0 _ _ _ \u001b[34mP\u001b[0m _ \u001b[31mb\u001b[0m _ _ 0\n",
            "1 _ _ _ _ _ \u001b[31mk\u001b[0m _ _ 1\n",
            "2 \u001b[31mr\u001b[0m _ \u001b[31mn\u001b[0m \u001b[34mN\u001b[0m _ _ _ _ 2\n",
            "3 \u001b[31mp\u001b[0m _ \u001b[31mp\u001b[0m _ _ _ _ _ 3\n",
            "4 _ _ _ _ _ _ \u001b[34mR\u001b[0m _ 4\n",
            "5 _ _ _ _ _ \u001b[34mN\u001b[0m _ _ 5\n",
            "6 \u001b[34mP\u001b[0m \u001b[34mP\u001b[0m \u001b[34mP\u001b[0m \u001b[34mP\u001b[0m \u001b[34mP\u001b[0m \u001b[34mP\u001b[0m \u001b[34mP\u001b[0m _ 6\n",
            "7 \u001b[34mR\u001b[0m _ \u001b[34mB\u001b[0m \u001b[34mQ\u001b[0m \u001b[34mK\u001b[0m \u001b[34mB\u001b[0m _ _ 7\n",
            "+ 0 1 2 3 4 5 6 7 +\n",
            "\n",
            "---- False turn ----\n",
            "2 3 1 5\n",
            "+ 0 1 2 3 4 5 6 7 +\n",
            "0 _ _ _ \u001b[34mP\u001b[0m _ \u001b[31mb\u001b[0m _ _ 0\n",
            "1 _ _ _ _ _ \u001b[34mN\u001b[0m _ _ 1\n",
            "2 \u001b[31mr\u001b[0m _ \u001b[31mn\u001b[0m _ _ _ _ _ 2\n",
            "3 \u001b[31mp\u001b[0m _ \u001b[31mp\u001b[0m _ _ _ _ _ 3\n",
            "4 _ _ _ _ _ _ \u001b[34mR\u001b[0m _ 4\n",
            "5 _ _ _ _ _ \u001b[34mN\u001b[0m _ _ 5\n",
            "6 \u001b[34mP\u001b[0m \u001b[34mP\u001b[0m \u001b[34mP\u001b[0m \u001b[34mP\u001b[0m \u001b[34mP\u001b[0m \u001b[34mP\u001b[0m \u001b[34mP\u001b[0m _ 6\n",
            "7 \u001b[34mR\u001b[0m _ \u001b[34mB\u001b[0m \u001b[34mQ\u001b[0m \u001b[34mK\u001b[0m \u001b[34mB\u001b[0m _ _ 7\n",
            "+ 0 1 2 3 4 5 6 7 +\n",
            "\n",
            "Minimax Won\n"
          ]
        }
      ],
      "source": [
        "#minimax với random\n",
        "from typing import MutableMapping\n",
        "import random\n",
        "from termcolor import colored\n",
        "from IPython.display import clear_output\n",
        "import time\n",
        "# K, k: Vua\n",
        "# Q, q: Hậu\n",
        "# R, r: Xe\n",
        "# B, b: Tượng\n",
        "# N, n: Mã\n",
        "# P, p: Tốt\n",
        "liR = [(1,0),(2,0),(3,0),(4,0),(5,0),(6,0),(7,0)]\n",
        "liL = [(-1,0),(-2,0),(-3,0),(-4,0),(-5,0),(-6,0),(-7,0)]\n",
        "liD = [(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(0,7)]\n",
        "liU = [(0,-1),(0,-2),(0,-3),(0,-4),(0,-5),(0,-6),(0,-7)]\n",
        "liRD = [(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(7,7)]\n",
        "liLU = [(-1,-1),(-2,-2),(-3,-3),(-4,-4),(-5,-5),(-6,-6),(-7,-7)]\n",
        "liRU = [(1,-1),(2,-2),(3,-3),(4,-4),(5,-5),(6,-6),(7,-7)]\n",
        "liLD = [(-1,1),(-2,2),(-3,3),(-4,4),(-5,5),(-6,6),(-7,7)]\n",
        "liN = [(1,2),(-1,2),(1,-2),(-1,-2),(2,1),(-2,1),(2,-1),(-2,-1)]\n",
        "liK = [(0,1),(1,0),(0,-1),(-1,0),(1,1),(-1,1),(1,-1),(-1,-1)]\n",
        "\n",
        "board = [['r','n','b','q','k','b','n','r'],\n",
        "         ['p','p','p','p','p','p','p','p'],\n",
        "         ['_','_','_','_','_','_','_','_'],\n",
        "         ['_','_','_','_','_','_','_','_'],\n",
        "         ['_','_','_','_','_','_','_','_'],\n",
        "         ['_','_','_','_','_','_','_','_'],\n",
        "         ['P','P','P','P','P','P','P','P'],\n",
        "         ['R','N','B','Q','K','B','N','R']]\n",
        "\n",
        "# kiểm tra có thể đi được hay không (Xe, Tượng, Hậu)\n",
        "def Go(x,y,l,isContinue=False,canFight=True,needFight=False):\n",
        "  li = []\n",
        "  for dx,dy in l:\n",
        "    x1 = x+dx\n",
        "    y1 = y+dy\n",
        "    if x1<0 or x1>=8 or y1<0 or y1>=8: \n",
        "      if not isContinue: \n",
        "        break \n",
        "      else: \n",
        "        continue\n",
        "    if board[y1][x1] != '_':\n",
        "      if canFight and board[y][x].islower() != board[y1][x1].islower():\n",
        "        li.append((x1,y1))\n",
        "      if not isContinue: break \n",
        "      else: continue\n",
        "    if not needFight:\n",
        "      li.append((x1,y1))\n",
        "  return li\n",
        "\n",
        "\n",
        "# các nước có thể đi của quân Xe\n",
        "def Rr(x,y):\n",
        "  return Go(x,y,liR) + Go(x,y,liL) + Go(x,y,liU) + Go(x,y,liD)\n",
        "\n",
        "# các nước có thể đi của quân Tượng\n",
        "def Bb(x,y):\n",
        "  return Go(x,y,liRD) + Go(x,y,liLU) + Go(x,y,liRU) + Go(x,y,liLD)\n",
        "\n",
        "# các nước có thể đi của quân Hậu\n",
        "def Qq(x,y):\n",
        "  return Rr(x,y) + Bb(x,y)\n",
        "\n",
        "# các nước có thể đi của quân Mã\n",
        "def Nn(x,y):\n",
        "  return Go(x,y,liN,isContinue=True)\n",
        "\n",
        "# các nước có thể đi của quân Vua\n",
        "def Kk(x,y):\n",
        "  return Go(x,y,liK,isContinue=True)\n",
        "\n",
        "# các nước có thể đi của quân Tốt\n",
        "def Pp(x,y):\n",
        "  li = []\n",
        "  dx = 1\n",
        "  if not board[y][x].islower():\n",
        "    dx = -1\n",
        "  # nước có thể đi\n",
        "  if y==1 or y==6:\n",
        "    li = li + Go(x,y,[(0,dx),(0,2*dx)],canFight=False)\n",
        "  else:\n",
        "    li = li + Go(x,y,[(0,dx)], canFight=False)\n",
        "  # nước có thể ăn (tốt ăn chéo)\n",
        "  li = li + Go(x,y,[(-1,dx),(1,dx)],needFight=True)\n",
        "  return li\n",
        "\n",
        "# x, y là tọa độ quân cờ\n",
        "# islower lượt của quân thường (True) hay quân hoa (False)\n",
        "# return danh sách tọa độ các nước có thể di chuyển tới\n",
        "def CanGo(x,y,islower):\n",
        "  if board[y][x].islower() != islower:\n",
        "    return []\n",
        "  if (board[y][x] in \"Rr\"):\n",
        "    return Rr(x,y)\n",
        "  if (board[y][x] in \"Nn\"):\n",
        "   return Nn(x,y)\n",
        "  if (board[y][x] in \"Bb\"):\n",
        "    return Bb(x,y)\n",
        "  if (board[y][x] in \"Qq\"):\n",
        "    return Qq(x,y)\n",
        "  if (board[y][x] in \"Kk\"):\n",
        "    return Kk(x,y)\n",
        "  if (board[y][x] in \"Pp\"):\n",
        "    return Pp(x,y)\n",
        "  return []\n",
        "\n",
        "\n",
        "def isFinish(board):\n",
        "  U = False\n",
        "  L = False\n",
        "  for _ in board:\n",
        "    U = U or ('K' in _)\n",
        "    L = L or ('k' in _)\n",
        "  return not (U and L)\n",
        "\n",
        "# return tất cả các nước có thể di chuyển (y,x) -> (y1,x1)\n",
        "def CanGoList(board,islower):\n",
        "  li = []\n",
        "  for y in range(8):\n",
        "    for x in range(8):\n",
        "      l = CanGo(x,y,islower)\n",
        "      for x1,y1 in l:\n",
        "        li = li + [(y,x,y1,x1)]\n",
        "  return li\n",
        "\n",
        "def CPURandomTurn(board,islower):\n",
        "  #######################################################\n",
        "  #  Có thể bỏ time.sleep(1) để xem kết quả nhanh hơn   #\n",
        "  ####################################################### \n",
        "  li = CanGoList(board,islower)\n",
        "  return random.choice(li)\n",
        "\n",
        "#minimax root\n",
        "def CPUMiniMaxTurn(board,islower,depth = 2):\n",
        "  #######################################################\n",
        "  #  Nên dùng Minimax với độ sâu từ 2 đến 4             #\n",
        "  #######################################################\n",
        "  #li là list có thể đi của lượt\n",
        "  li = CanGoList(board,islower)\n",
        "  Max = -1000\n",
        "  for y,x,y1,x1 in CanGoList(board,islower):\n",
        "    child = [_[:] for _ in board]\n",
        "    #di chuyển quân cờ tọa độ y,x đến tọa độ y1,x1\n",
        "    child[y1][x1] = child[y][x]\n",
        "    child[y][x] = '_'\n",
        "    vl = Minimax(child,depth-1,islower,not islower,-1000,1000)\n",
        "    #nếu max < value hoặc max = value nhưng random choice = 0 thì thay max = value, r = tọa độ khác, return r\n",
        "    if Max < vl or (Max == vl and random.choice([0,1])==0):\n",
        "      Max = vl\n",
        "      r = (y,x,y1,x1)\n",
        "  return r\n",
        "\n",
        "\n",
        "# Board: Bàn cờ hiện tại\n",
        "# islower: lượt của quân viết thường (True) hay quân viết hoa (False)\n",
        "# return: giá trị của bàn cờ đối với quân viết thường\n",
        "\n",
        "# K, k: Vua\n",
        "# Q, q: Hậu\n",
        "# R, r: Xe\n",
        "# B, b: Tượng\n",
        "# N, n: Mã\n",
        "# P, p: Tốt\n",
        "\n",
        "def Check(g):\n",
        "  if (g==\"_\"):\n",
        "    return 0;\n",
        "  if (g==\"k\"):\n",
        "    return -99\n",
        "  if (g==\"q\"):\n",
        "    return -15\n",
        "  if (g==\"b\"):\n",
        "    return -6\n",
        "  if (g==\"n\"):\n",
        "    return -3\n",
        "  if (g==\"r\"):\n",
        "    return -9\n",
        "  if (g==\"p\"):\n",
        "    return -1\n",
        "  if (g==\"K\"):\n",
        "    return 99\n",
        "  if (g==\"Q\"):\n",
        "    return 15\n",
        "  if (g==\"B\"):\n",
        "    return 6\n",
        "  if (g==\"N\"):\n",
        "    return 3\n",
        "  if (g==\"R\"):\n",
        "    return 9\n",
        "  if (g==\"P\"):\n",
        "    return 1\n",
        "  \n",
        "#evaluateBoard\n",
        "def value(board,islower):\n",
        "  vl = 0\n",
        "  ######################################################\n",
        "  #  Cần định nghĩa lại hàm value                      #\n",
        "  #  Gợi ý:                                            #\n",
        "  #       1. Hiệu số quân cờ 2 bên                     #\n",
        "  #       2. Vị trí quân cờ trên bàn cờ                #\n",
        "  #       3. Tùy suy nghĩ của các em                   #\n",
        "  ######################################################\n",
        "  for i in range(8):\n",
        "    for j in range(8):\n",
        "      vl = vl + Check(board[i][j])\n",
        "  return vl;\n",
        "\n",
        "\n",
        "# node là thế cờ hiện tại\n",
        "# depth là độ sâu\n",
        "# Pmax là player cần tìm Max\n",
        "# Pnow là player hiện tại\n",
        "\n",
        "#minimax\n",
        "def Minimax(node,depth,Pmax,Pnow,alpha,beta):\n",
        "  if isFinish(node) or depth ==0:\n",
        "    return value(node,Pmax)\n",
        "  #islower == not islower\n",
        "  if Pmax == Pnow:\n",
        "    Max = -1000\n",
        "    for y,x,y1,x1 in CanGoList(node,Pnow):\n",
        "      child = [_[:] for _ in node]\n",
        "      child[y1][x1] = child[y][x]\n",
        "      child[y][x] = '_'\n",
        "      Max = max(Max,Minimax(child,depth-1,Pmax,not Pnow,alpha,beta))\n",
        "      alpha = max(alpha, Max);\n",
        "      if (beta <= alpha):\n",
        "        return Max;\n",
        "    return Max\n",
        "  else:\n",
        "    Min = 1000\n",
        "    for y,x,y1,x1 in CanGoList(node,Pnow):\n",
        "      child = [_[:] for _ in node]\n",
        "      child[y1][x1] = child[y][x]\n",
        "      child[y][x] = '_'\n",
        "      Min = min(Min,Minimax(child,depth-1,Pmax,not Pnow,alpha,beta))\n",
        "      beta = min(beta, Min);\n",
        "      if (beta <= alpha):\n",
        "        return Min;\n",
        "    return Min\n",
        "\n",
        "#in bàn cờ\n",
        "#quân thường đi trước\n",
        "def printBoard(board):\n",
        "  print(\"+\",*range(8),\"+\")\n",
        "\n",
        "  for i in range(8):\n",
        "    print(i,end=\" \")\n",
        "    for j in range(8):\n",
        "      if board[i][j] == '_':\n",
        "        print(board[i][j],end=\" \")\n",
        "      elif board[i][j].islower():\n",
        "        print(colored(board[i][j],'red'),end=\" \")\n",
        "      else:\n",
        "        print(colored(board[i][j],'blue'),end=\" \")\n",
        "    print(i,) \n",
        "\n",
        "  print(\"+\",*range(8),\"+\")\n",
        "  print()\n",
        "\n",
        "Random = True\n",
        "MiniMax = False\n",
        "Now = Random\n",
        "\n",
        "while not isFinish(board):\n",
        "  clear_output()\n",
        "  printBoard(board)\n",
        "  #now = random\n",
        "  print(\"----\",Now,\"turn\",\"----\")\n",
        "  #nếu now = minimax = false\n",
        "  if Now == MiniMax:\n",
        "    #tính theo minimax turn\n",
        "    y,x,y1,x1 = CPUMiniMaxTurn(board,MiniMax)\n",
        "    board[y1][x1] = board[y][x]\n",
        "    board[y][x] = '_'\n",
        "    #set now = random\n",
        "    Now = Random\n",
        "    #in thay đổi\n",
        "    print(y,x,y1,x1)\n",
        "  else:\n",
        "    #tính theo random turn = true\n",
        "    y,x,y1,x1 = CPURandomTurn(board,Random)\n",
        "    board[y1][x1] = board[y][x]\n",
        "    board[y][x] = '_'\n",
        "    #in thay đổi\n",
        "    print(y,x,y1,x1)\n",
        "    #set now = mini max turn\n",
        "    Now = MiniMax\n",
        "\n",
        "printBoard(board)\n",
        "if Now:\n",
        "  print(\"Minimax Won\")\n",
        "else:\n",
        "  print(\"Random Won\")"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "G1bE6sAVSfku",
        "outputId": "1a1d9aed-2b43-4091-c9ef-68dcf57d3f7d"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "+ 0 1 2 3 4 5 6 7 +\n",
            "0 _ \u001b[31mn\u001b[0m \u001b[31mb\u001b[0m _ _ _ _ _ 0\n",
            "1 _ _ _ _ _ _ _ \u001b[31mk\u001b[0m 1\n",
            "2 _ \u001b[34mP\u001b[0m _ _ _ _ \u001b[34mK\u001b[0m _ 2\n",
            "3 _ _ _ _ _ _ _ _ 3\n",
            "4 \u001b[34mP\u001b[0m _ _ _ _ _ _ _ 4\n",
            "5 _ _ _ _ _ _ _ _ 5\n",
            "6 _ _ _ _ _ _ _ _ 6\n",
            "7 _ \u001b[34mR\u001b[0m _ _ _ _ _ _ 7\n",
            "+ 0 1 2 3 4 5 6 7 +\n",
            "\n",
            "---- False turn ----\n",
            "2 6 1 7\n",
            "+ 0 1 2 3 4 5 6 7 +\n",
            "0 _ \u001b[31mn\u001b[0m \u001b[31mb\u001b[0m _ _ _ _ _ 0\n",
            "1 _ _ _ _ _ _ _ \u001b[34mK\u001b[0m 1\n",
            "2 _ \u001b[34mP\u001b[0m _ _ _ _ _ _ 2\n",
            "3 _ _ _ _ _ _ _ _ 3\n",
            "4 \u001b[34mP\u001b[0m _ _ _ _ _ _ _ 4\n",
            "5 _ _ _ _ _ _ _ _ 5\n",
            "6 _ _ _ _ _ _ _ _ 6\n",
            "7 _ \u001b[34mR\u001b[0m _ _ _ _ _ _ 7\n",
            "+ 0 1 2 3 4 5 6 7 +\n",
            "\n",
            "Minimax Won\n"
          ]
        }
      ],
      "source": [
        "\n",
        "from typing import MutableMapping\n",
        "import random\n",
        "from termcolor import colored\n",
        "from IPython.display import clear_output\n",
        "import time\n",
        "# K, k: Vua\n",
        "# Q, q: Hậu\n",
        "# R, r: Xe\n",
        "# B, b: Tượng\n",
        "# N, n: Mã\n",
        "# P, p: Tốt\n",
        "liR = [(1,0),(2,0),(3,0),(4,0),(5,0),(6,0),(7,0)]\n",
        "liL = [(-1,0),(-2,0),(-3,0),(-4,0),(-5,0),(-6,0),(-7,0)]\n",
        "liD = [(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(0,7)]\n",
        "liU = [(0,-1),(0,-2),(0,-3),(0,-4),(0,-5),(0,-6),(0,-7)]\n",
        "liRD = [(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(7,7)]\n",
        "liLU = [(-1,-1),(-2,-2),(-3,-3),(-4,-4),(-5,-5),(-6,-6),(-7,-7)]\n",
        "liRU = [(1,-1),(2,-2),(3,-3),(4,-4),(5,-5),(6,-6),(7,-7)]\n",
        "liLD = [(-1,1),(-2,2),(-3,3),(-4,4),(-5,5),(-6,6),(-7,7)]\n",
        "liN = [(1,2),(-1,2),(1,-2),(-1,-2),(2,1),(-2,1),(2,-1),(-2,-1)]\n",
        "liK = [(0,1),(1,0),(0,-1),(-1,0),(1,1),(-1,1),(1,-1),(-1,-1)]\n",
        "\n",
        "board = [['r','n','b','q','k','b','n','r'],\n",
        "         ['p','p','p','p','p','p','p','p'],\n",
        "         ['_','_','_','_','_','_','_','_'],\n",
        "         ['_','_','_','_','_','_','_','_'],\n",
        "         ['_','_','_','_','_','_','_','_'],\n",
        "         ['_','_','_','_','_','_','_','_'],\n",
        "         ['P','P','P','P','P','P','P','P'],\n",
        "         ['R','N','B','Q','K','B','N','R']]\n",
        "\n",
        "# kiểm tra có thể đi được hay không (Xe, Tượng, Hậu)\n",
        "def Go(x,y,l,isContinue=False,canFight=True,needFight=False):\n",
        "  li = []\n",
        "  for dx,dy in l:\n",
        "    x1 = x+dx\n",
        "    y1 = y+dy\n",
        "    if x1<0 or x1>=8 or y1<0 or y1>=8: \n",
        "      if not isContinue: \n",
        "        break \n",
        "      else: \n",
        "        continue\n",
        "    if board[y1][x1] != '_':\n",
        "      if canFight and board[y][x].islower() != board[y1][x1].islower():\n",
        "        li.append((x1,y1))\n",
        "      if not isContinue: break \n",
        "      else: continue\n",
        "    if not needFight:\n",
        "      li.append((x1,y1))\n",
        "  return li\n",
        "\n",
        "\n",
        "# các nước có thể đi của quân Xe\n",
        "def Rr(x,y):\n",
        "  return Go(x,y,liR) + Go(x,y,liL) + Go(x,y,liU) + Go(x,y,liD)\n",
        "\n",
        "# các nước có thể đi của quân Tượng\n",
        "def Bb(x,y):\n",
        "  return Go(x,y,liRD) + Go(x,y,liLU) + Go(x,y,liRU) + Go(x,y,liLD)\n",
        "\n",
        "# các nước có thể đi của quân Hậu\n",
        "def Qq(x,y):\n",
        "  return Rr(x,y) + Bb(x,y)\n",
        "\n",
        "# các nước có thể đi của quân Mã\n",
        "def Nn(x,y):\n",
        "  return Go(x,y,liN,isContinue=True)\n",
        "\n",
        "# các nước có thể đi của quân Vua\n",
        "def Kk(x,y):\n",
        "  return Go(x,y,liK,isContinue=True)\n",
        "\n",
        "# các nước có thể đi của quân Tốt\n",
        "def Pp(x,y):\n",
        "  li = []\n",
        "  dx = 1\n",
        "  if not board[y][x].islower():\n",
        "    dx = -1\n",
        "  # nước có thể đi\n",
        "  if y==1 or y==6:\n",
        "    li = li + Go(x,y,[(0,dx),(0,2*dx)],canFight=False)\n",
        "  else:\n",
        "    li = li + Go(x,y,[(0,dx)], canFight=False)\n",
        "  # nước có thể ăn (tốt ăn chéo)\n",
        "  li = li + Go(x,y,[(-1,dx),(1,dx)],needFight=True)\n",
        "  return li\n",
        "\n",
        "# x, y là tọa độ quân cờ\n",
        "# islower lượt của quân thường (True) hay quân hoa (False)\n",
        "# return danh sách tọa độ các nước có thể di chuyển tới\n",
        "def CanGo(x,y,islower):\n",
        "  if board[y][x].islower() != islower:\n",
        "    return []\n",
        "  if (board[y][x] in \"Rr\"):\n",
        "    return Rr(x,y)\n",
        "  if (board[y][x] in \"Nn\"):\n",
        "   return Nn(x,y)\n",
        "  if (board[y][x] in \"Bb\"):\n",
        "    return Bb(x,y)\n",
        "  if (board[y][x] in \"Qq\"):\n",
        "    return Qq(x,y)\n",
        "  if (board[y][x] in \"Kk\"):\n",
        "    return Kk(x,y)\n",
        "  if (board[y][x] in \"Pp\"):\n",
        "    return Pp(x,y)\n",
        "  return []\n",
        "\n",
        "\n",
        "def isFinish(board):\n",
        "  U = False\n",
        "  L = False\n",
        "  for _ in board:\n",
        "    U = U or ('K' in _)\n",
        "    L = L or ('k' in _)\n",
        "  return not (U and L)\n",
        "\n",
        "# return tất cả các nước có thể di chuyển (y,x) -> (y1,x1)\n",
        "def CanGoList(board,islower):\n",
        "  li = []\n",
        "  for y in range(8):\n",
        "    for x in range(8):\n",
        "      l = CanGo(x,y,islower)\n",
        "      for x1,y1 in l:\n",
        "        li = li + [(y,x,y1,x1)]\n",
        "  return li\n",
        "\n",
        "def CPURandomTurn(board,islower,depth = 3):\n",
        "  #######################################################\n",
        "  #  Có thể bỏ time.sleep(1) để xem kết quả nhanh hơn   #\n",
        "  ####################################################### \n",
        "  li = CanGoList(board,islower)\n",
        "  Max = -1000\n",
        "  for y,x,y1,x1 in CanGoList(board,islower):\n",
        "    child = [_[:] for _ in board]\n",
        "    #di chuyển quân cờ tọa độ y,x đến tọa độ y1,x1\n",
        "    child[y1][x1] = child[y][x]\n",
        "    child[y][x] = '_'\n",
        "    vl = Minimax(child,depth-1,islower,not islower,0,0)\n",
        "    #nếu max < value hoặc max = value nhưng random choice = 0 thì thay max = value, r = tọa độ khác, return r\n",
        "    if Max < vl or (Max == vl and random.choice([0,1])==0):\n",
        "      Max = vl\n",
        "      r = (y,x,y1,x1)\n",
        "  return r\n",
        "\n",
        "#minimax root\n",
        "def CPUMiniMaxTurn(board,islower,depth = 3):\n",
        "  #######################################################\n",
        "  #  Nên dùng Minimax với độ sâu từ 2 đến 4             #\n",
        "  #######################################################\n",
        "  #li là list có thể đi của lượt\n",
        "  li = CanGoList(board,islower)\n",
        "  Max = -1000\n",
        "  for y,x,y1,x1 in CanGoList(board,islower):\n",
        "    child = [_[:] for _ in board]\n",
        "    #di chuyển quân cờ tọa độ y,x đến tọa độ y1,x1\n",
        "    child[y1][x1] = child[y][x]\n",
        "    child[y][x] = '_'\n",
        "    vl = Minimax(child,depth-1,islower,not islower,-1000, 1000)\n",
        "    #nếu max < value hoặc max = value nhưng random choice = 0 thì thay max = value, r = tọa độ khác, return r\n",
        "    if Max < vl or (Max == vl and random.choice([0,1])==0):\n",
        "      Max = vl\n",
        "      r = (y,x,y1,x1)\n",
        "  return r\n",
        "\n",
        "\n",
        "# Board: Bàn cờ hiện tại\n",
        "# islower: lượt của quân viết thường (True) hay quân viết hoa (False)\n",
        "# return: giá trị của bàn cờ đối với quân viết thường\n",
        "\n",
        "# K, k: Vua\n",
        "# Q, q: Hậu\n",
        "# R, r: Xe\n",
        "# B, b: Tượng\n",
        "# N, n: Mã\n",
        "# P, p: Tốt\n",
        "\n",
        "def Check1(g):\n",
        "  if (g==\"_\"):\n",
        "    return 0;\n",
        "  if (g==\"k\"):\n",
        "    return 99\n",
        "  if (g==\"q\"):\n",
        "    return 15\n",
        "  if (g==\"b\"):\n",
        "    return 3\n",
        "  if (g==\"n\"):\n",
        "    return 3\n",
        "  if (g==\"r\"):\n",
        "    return 5\n",
        "  if (g==\"p\"):\n",
        "    return 1\n",
        "  if (g==\"K\"):\n",
        "    return -99\n",
        "  if (g==\"Q\"):\n",
        "    return -9\n",
        "  if (g==\"B\"):\n",
        "    return -3\n",
        "  if (g==\"N\"):\n",
        "    return -3\n",
        "  if (g==\"R\"):\n",
        "    return -5\n",
        "  if (g==\"P\"):\n",
        "    return -1\n",
        "\n",
        "def Check(g):\n",
        "  if (g==\"_\"):\n",
        "    return 0;\n",
        "  if (g==\"k\"):\n",
        "    return -99\n",
        "  if (g==\"q\"):\n",
        "    return -15\n",
        "  if (g==\"b\"):\n",
        "    return -6\n",
        "  if (g==\"n\"):\n",
        "    return -3\n",
        "  if (g==\"r\"):\n",
        "    return -9\n",
        "  if (g==\"p\"):\n",
        "    return -1\n",
        "  if (g==\"K\"):\n",
        "    return 99\n",
        "  if (g==\"Q\"):\n",
        "    return 15\n",
        "  if (g==\"B\"):\n",
        "    return 6\n",
        "  if (g==\"N\"):\n",
        "    return 3\n",
        "  if (g==\"R\"):\n",
        "    return 9\n",
        "  if (g==\"P\"):\n",
        "    return 1\n",
        "\n",
        "#evaluateBoard\n",
        "def value(board,islower):\n",
        "  vl = 0\n",
        "  ######################################################\n",
        "  #  Cần định nghĩa lại hàm value                      #\n",
        "  #  Gợi ý:                                            #\n",
        "  #       1. Hiệu số quân cờ 2 bên                     #\n",
        "  #       2. Vị trí quân cờ trên bàn cờ                #\n",
        "  #       3. Tùy suy nghĩ của các em                   #\n",
        "  ######################################################\n",
        "  if (islower==False):\n",
        "    for i in range(8):\n",
        "      for j in range(8):\n",
        "        vl = vl + Check(board[i][j])\n",
        "  else:\n",
        "   for i in range(8):\n",
        "      for j in range(8):\n",
        "        vl = vl + Check1(board[i][j])\n",
        "  return vl;\n",
        "\n",
        "\n",
        "# node là thế cờ hiện tại\n",
        "# depth là độ sâu\n",
        "# Pmax là player cần tìm Max\n",
        "# Pnow là player hiện tại\n",
        "\n",
        "#minimax\n",
        "def Minimax(node,depth,Pmax,Pnow,alpha,beta):\n",
        "  if isFinish(node) or depth ==0:\n",
        "    return value(node,Pmax)\n",
        "  #islower == not islower\n",
        "  if Pmax == Pnow:\n",
        "    Max = -1000\n",
        "    for y,x,y1,x1 in CanGoList(node,Pnow):\n",
        "      child = [_[:] for _ in node]\n",
        "      child[y1][x1] = child[y][x]\n",
        "      child[y][x] = '_'\n",
        "      Max = max(Max,Minimax(child,depth-1,Pmax,not Pnow,alpha,beta))\n",
        "      alpha = max(alpha, Max);\n",
        "      if (beta <= alpha):\n",
        "        return Max;\n",
        "    return Max\n",
        "  else:\n",
        "    Min = 1000\n",
        "    for y,x,y1,x1 in CanGoList(node,Pnow):\n",
        "      child = [_[:] for _ in node]\n",
        "      child[y1][x1] = child[y][x]\n",
        "      child[y][x] = '_'\n",
        "      Min = min(Min,Minimax(child,depth-1,Pmax,not Pnow,alpha,beta))\n",
        "      beta = min(beta, Min);\n",
        "      if (beta <= alpha):\n",
        "        return Min;\n",
        "    return Min\n",
        "\n",
        "#in bàn cờ\n",
        "#quân thường đi trước\n",
        "def printBoard(board):\n",
        "  print(\"+\",*range(8),\"+\")\n",
        "\n",
        "  for i in range(8):\n",
        "    print(i,end=\" \")\n",
        "    for j in range(8):\n",
        "      if board[i][j] == '_':\n",
        "        print(board[i][j],end=\" \")\n",
        "      elif board[i][j].islower():\n",
        "        print(colored(board[i][j],'red'),end=\" \")\n",
        "      else:\n",
        "        print(colored(board[i][j],'blue'),end=\" \")\n",
        "    print(i,) \n",
        "\n",
        "  print(\"+\",*range(8),\"+\")\n",
        "  print()\n",
        "\n",
        "Random = True\n",
        "MiniMax = False\n",
        "Now = Random\n",
        "\n",
        "while not isFinish(board):\n",
        "  clear_output()\n",
        "  printBoard(board)\n",
        "  #now = random\n",
        "  print(\"----\",Now,\"turn\",\"----\")\n",
        "  #nếu now = minimax = false\n",
        "  if Now == MiniMax:\n",
        "    #tính theo minimax turn\n",
        "    y,x,y1,x1 = CPUMiniMaxTurn(board,MiniMax)\n",
        "    board[y1][x1] = board[y][x]\n",
        "    board[y][x] = '_'\n",
        "    #set now = random\n",
        "    Now = Random\n",
        "    #in thay đổi\n",
        "    print(y,x,y1,x1)\n",
        "  else:\n",
        "    #tính theo random turn = true\n",
        "    y,x,y1,x1 = CPURandomTurn(board,Random)\n",
        "    board[y1][x1] = board[y][x]\n",
        "    board[y][x] = '_'\n",
        "    #in thay đổi\n",
        "    print(y,x,y1,x1)\n",
        "    #set now = mini max turn\n",
        "    Now = MiniMax\n",
        "\n",
        "printBoard(board)\n",
        "if Now:\n",
        "  print(\"Minimax Won\")\n",
        "else:\n",
        "  print(\"Random Won\")"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "z279-T2e5Unq"
      },
      "outputs": [],
      "source": []
    }
  ],
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyO9nqLOK+kTdrSf8FsXzO8q",
      "include_colab_link": true
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}