5arbga(predict best move).ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "7794d858",
   "metadata": {},
   "outputs": [],
   "source": [
    "#this function store the possible moves for each rock\n",
    "def possible_moves(i,j):\n",
    "    from collections import defaultdict\n",
    "    d=defaultdict(list)\n",
    "    if(i==0 and j==0):\n",
    "        d[0].append(0)\n",
    "        d[0].append(1)\n",
    "        d[1].append(1)\n",
    "        d[1].append(0)\n",
    "        d[2].append(1)\n",
    "        d[2].append(1)\n",
    "    elif(i==0 and j==2):\n",
    "        d[0].append(0)\n",
    "        d[0].append(1)\n",
    "        d[1].append(1)\n",
    "        d[1].append(2)\n",
    "        d[2].append(1)\n",
    "        d[2].append(1)\n",
    "    elif(i==2 and j==0):\n",
    "        d[0].append(1)\n",
    "        d[0].append(0)\n",
    "        d[1].append(2)\n",
    "        d[1].append(1)\n",
    "        d[2].append(1)\n",
    "        d[2].append(1)\n",
    "    elif(i==2 and j==2):\n",
    "        d[0].append(1)\n",
    "        d[0].append(2)\n",
    "        d[1].append(2)\n",
    "        d[1].append(1)\n",
    "        d[2].append(1)\n",
    "        d[2].append(1)\n",
    "    elif(i==0 and j==1):\n",
    "        d[0].append(0)\n",
    "        d[0].append(0)\n",
    "        d[1].append(0)\n",
    "        d[1].append(2)\n",
    "        d[2].append(1)\n",
    "        d[2].append(1)\n",
    "    elif(i==2 and j==1):\n",
    "        d[0].append(2)\n",
    "        d[0].append(0)\n",
    "        d[1].append(2)\n",
    "        d[1].append(2)\n",
    "        d[2].append(1)\n",
    "        d[2].append(1)\n",
    "    elif(i==1 and j==0):\n",
    "        d[0].append(0)\n",
    "        d[0].append(0)\n",
    "        d[1].append(2)\n",
    "        d[1].append(0)\n",
    "        d[2].append(1)\n",
    "        d[2].append(1)\n",
    "    elif(i==1 and j==2):\n",
    "        d[0].append(0)\n",
    "        d[0].append(2)\n",
    "        d[1].append(2)\n",
    "        d[1].append(2)\n",
    "        d[2].append(1)\n",
    "        d[2].append(1)\n",
    "    return d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "ebe9e7b1",
   "metadata": {},
   "outputs": [],
   "source": [
    "# if we have 3 rocks in the same line that mean the game is over \n",
    "# The value -10 means that the player beat the computer \n",
    "# The value 10 means that the player lost to the computer \n",
    "def evaluate(b,pc,op) :\n",
    "   \n",
    "    for row in range(3) :    \n",
    "        if (b[row][0] == b[row][1] and b[row][1] == b[row][2]) :       \n",
    "            if (b[row][0] == pc) :\n",
    "                return 10\n",
    "            elif (b[row][0] == op) :\n",
    "                return -10\n",
    " \n",
    "   \n",
    "    for col in range(3) :\n",
    "      \n",
    "        if (b[0][col] == b[1][col] and b[1][col] == b[2][col]) :\n",
    "         \n",
    "            if (b[0][col] == pc) :\n",
    "                return 10\n",
    "            elif (b[0][col] == op) :\n",
    "                return -10\n",
    " \n",
    "    if (b[0][0] == b[1][1] and b[1][1] == b[2][2]) :\n",
    "     \n",
    "        if (b[0][0] == pc) :\n",
    "            return 10\n",
    "        elif (b[0][0] == op) :\n",
    "            return -10\n",
    " \n",
    "    if (b[0][2] == b[1][1] and b[1][1] == b[2][0]) :\n",
    "     \n",
    "        if (b[0][2] == pc) :\n",
    "            return 10\n",
    "        elif (b[0][2] == op) :\n",
    "            return -10\n",
    " \n",
    "   \n",
    "    return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "3c7de104",
   "metadata": {},
   "outputs": [],
   "source": [
    "def minimax(damma, depth, Max,alpha,beta,pc,op):\n",
    "\n",
    "    score = evaluate(damma,pc,op)\n",
    "\n",
    "    if (score == 10): \n",
    "        return score,depth\n",
    "\n",
    "    if (score == -10):    \n",
    "        return score,depth\n",
    "    \n",
    "    \n",
    "    if (depth == 5):\n",
    "        return 0,depth\n",
    "\n",
    "    if (Max):\n",
    "        dep=10\n",
    "        best = -1000\n",
    "        for i in range(2,-1,-1):\n",
    "        \n",
    "            for j in range(2,-1,-1):\n",
    "            \n",
    "                \n",
    "                if (damma[i][j]==pc and ((i==1) and (j==1))==False):\n",
    "                    v=possible_moves(i,j)\n",
    "                    for x in range(3):\n",
    "\n",
    "                        y=v[x][0]\n",
    "                        z=v[x][1]\n",
    "                        if (damma[y][z]=='_'):\n",
    "                            damma[i][j] = '_'\n",
    "                            damma[y][z] = pc\n",
    "                            val_best,val_dep=minimax(damma, depth+1,not(Max),alpha,beta,pc,op)\n",
    "                          \n",
    "                            if(best==val_best):\n",
    "                                    dep=min(dep,val_dep)\n",
    "                            elif(best<val_best):\n",
    "                                    dep=val_dep\n",
    "                            best = max(best,val_best)\n",
    "                            alpha = max(alpha, best)\n",
    "                        \n",
    "\n",
    "                            damma[i][j] = pc\n",
    "                            damma[y][z] = '_'\n",
    "                  \n",
    "\n",
    "                \n",
    "                elif(damma[i][j]==pc and ((i==1) and (j==1))==True):\n",
    "                    for s in range(3):\n",
    "        \n",
    "                        for k in range(3):\n",
    "            \n",
    "                          if (damma[s][k]=='_' and ((s==1) and (k==1))==False):\n",
    "                                damma[1][1] = '_'\n",
    "                                damma[s][k] = pc\n",
    "                                val_best,val_dep=minimax(damma, depth+1,not(Max),alpha,beta,pc,op)\n",
    "                             \n",
    "                                if(best==val_best):\n",
    "                                    dep=min(dep,val_dep)\n",
    "                                elif(best<val_best):\n",
    "                                     dep=val_dep\n",
    "                                best = max(best,val_best)\n",
    "                                alpha = max(alpha,best)\n",
    "                                damma[1][1] = pc\n",
    "                                damma[s][k] = '_'\n",
    "                             \n",
    "\n",
    "                \n",
    "            \n",
    "        \n",
    "        return best,dep\n",
    "        \n",
    "    \n",
    "\n",
    "   \n",
    "    else:\n",
    "    \n",
    "        best = 1000\n",
    "        dep=10\n",
    "      \n",
    "        for i in range(2,-1,-1):\n",
    "        \n",
    "            for j in range(2,-1,-1):\n",
    "            \n",
    "               \n",
    "                if (damma[i][j]==op and ((i==1) and (j==1))==False):\n",
    "                    v=possible_moves(i,j)\n",
    "                    for x in range(3):\n",
    "                        y=v[x][0]\n",
    "                        z=v[x][1]\n",
    "                      \n",
    "                        if (damma[y][z]=='_'):\n",
    "                            damma[i][j] = '_'\n",
    "                            damma[y][z] =op\n",
    "                         \n",
    "                            val_best,val_dep=minimax(damma, depth+1,not(Max),alpha,beta,pc,op)\n",
    "                          \n",
    "                            if(best==val_best):\n",
    "                                    dep=min(dep,val_dep)\n",
    "                            elif(best>val_best):\n",
    "                                    dep=val_dep                           \n",
    "\n",
    "                            best = min(best,val_best)\n",
    "                            beta = min(beta,best)\n",
    "                   \n",
    "                            damma[i][j] = op\n",
    "                            damma[y][z] = '_'\n",
    "                     \n",
    "                \n",
    "                elif (damma[i][j]==op and ((i==1) and (j==1))==True):\n",
    "                    for s in range(3):\n",
    "        \n",
    "                       for k in range(3):\n",
    "            \n",
    "                            if (damma[s][k]=='_' and ((s==1) and (k==1))==False):\n",
    "                                damma[1][1] = '_'\n",
    "                                damma[s][k] = op\n",
    "                                val_best,val_dep=minimax(damma, depth+1,not(Max),alpha,beta,pc,op)\n",
    "                              \n",
    "                                if(best==val_best):\n",
    "                                    dep=min(dep,val_dep)\n",
    "                                elif(best>val_best):\n",
    "                                    dep=val_dep\n",
    "                                else:\n",
    "                                    dep=dep\n",
    "                            \n",
    "                                best = min(best,val_best)\n",
    "                                beta = min(beta,best)\n",
    "                                damma[1][1] = op\n",
    "                                damma[s][k] = '_'\n",
    "                                                         \n",
    "\n",
    "        return best,dep\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "8770a958",
   "metadata": {},
   "outputs": [],
   "source": [
    "def findBestMove(damma,pc,op):\n",
    "\n",
    "    bestVal = -1000\n",
    "    bestdepth=1000\n",
    "    bestMove_rowy = -1\n",
    "    bestMove_colz = -1\n",
    "    bestMove_rowi = -1\n",
    "    bestMove_colj = -1\n",
    "    \n",
    "\n",
    "   \n",
    "    for i in range(3):\n",
    "    \n",
    "        for j in range(3):\n",
    "        \n",
    "           \n",
    "            if ((damma[i][j]==pc) and ((i==1) and (j==1))==False):\n",
    "                v = possible_moves(i,j)\n",
    "                for x in range(3):\n",
    "\n",
    "                    y=v[x][0]\n",
    "                    z=v[x][1]\n",
    "                    if (damma[y][z]=='_'):\n",
    "                        damma[i][j] = '_'\n",
    "                        damma[y][z] = pc\n",
    "                        moveVal_best,moveVal_dep = minimax(damma, 0, False,-1000,1000,pc,op)\n",
    "                        print(\"moveVal_best   \",moveVal_best)\n",
    "                        print(\"moveVal_dep   \",moveVal_dep)\n",
    "                        damma[i][j] = pc\n",
    "                        damma[y][z] = '_'\n",
    "                        print(\"  \")\n",
    "                        print(i,\"   \",j)\n",
    "                        print(y,\"   \",z)\n",
    "                        print(\"  \")\n",
    "\n",
    "                        if((moveVal_best==10) and (moveVal_dep < bestdepth)):\n",
    "                                bestMove_rowy = y\n",
    "                           \n",
    "                                bestMove_colz = z\n",
    "                           \n",
    "                                bestMove_rowi = i\n",
    "                            \n",
    "                                bestMove_colj = j\n",
    "                                \n",
    "                                bestVal = moveVal_best\n",
    "                                print(\"bestVal   \",bestVal)\n",
    "                                bestdepth=moveVal_dep\n",
    "                                print(\"bestdepth   \",bestdepth)\n",
    "                    \n",
    "\n",
    "                \n",
    "                        if (moveVal_best > bestVal ):\n",
    "                                bestMove_rowy = y\n",
    "                            \n",
    "                                bestMove_colz = z\n",
    "                           \n",
    "                                bestMove_rowi = i\n",
    "                            \n",
    "                                bestMove_colj = j\n",
    "                            \n",
    "                                bestVal = moveVal_best\n",
    "                                print(\"bestVal   \",bestVal)\n",
    "                print(\"*************\")     \n",
    "                \n",
    "\n",
    "            elif(damma[i][j]==pc and ((i==1) and(j==1))==True):\n",
    "                for i1 in range(3):\n",
    "        \n",
    "                      for j1 in range(3):\n",
    "            \n",
    "                           if(damma[i1][j1]=='_'and ((i1==1) and (j1==1))==False):\n",
    "                            damma[1][1] = '_'\n",
    "                            damma[i1][j1] = pc\n",
    "                            moveVal_best,moveVal_dep = minimax(damma, 0, False,-1000,1000,pc,op)\n",
    "                            print(\"moveVal_best   \",moveVal_best)\n",
    "                            print(\"moveVal_dep   \",moveVal_dep)\n",
    "                            damma[1][1] = pc\n",
    "                            damma[i1][j1] ='_'\n",
    "                            print(\"1\",\"   \",\"1\")\n",
    "                            print(i1,\"   \",j1)\n",
    "                            \n",
    "                            if(moveVal_best==10 and (moveVal_dep < bestdepth)):\n",
    "                                    bestMove_rowy = i1\n",
    "                                    \n",
    "                                    bestMove_colz = j1\n",
    "                                   \n",
    "                                    bestMove_rowi = 1\n",
    "                                    \n",
    "                                    bestMove_colj = 1\n",
    "                                   \n",
    "                                    bestVal = moveVal_best\n",
    "                                    print(\"bestVal   \",bestVal)\n",
    "                                    bestdepth=moveVal_dep\n",
    "                                    print(\"bestdepth   \",bestdepth)\n",
    "\n",
    "                                    \n",
    "                \n",
    "                            if (moveVal_best > bestVal ):\n",
    "                                    bestMove_rowy = i1\n",
    "                                    \n",
    "                                    bestMove_colz = j1\n",
    "                                    \n",
    "                                    bestMove_rowi = 1\n",
    "                                    \n",
    "                                    bestMove_colj = 1\n",
    "                                    \n",
    "                                    bestVal = moveVal_best\n",
    "                                    print(\"bestVal   \",bestVal)\n",
    "                print(\"*************\")    \n",
    "    print(\"The value of the best Move is : \",bestVal)\n",
    "\n",
    "    return  bestMove_rowy ,bestMove_colz ,bestMove_rowi ,bestMove_colj ,bestdepth,bestVal\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "2453d597",
   "metadata": {},
   "outputs": [],
   "source": [
    "def damma(p,o):\n",
    "    pc=p\n",
    "    op=o\n",
    "    damma = [\n",
    "        ['x', '_', 'x'],\n",
    "        ['x', 'o', 'o'],              \n",
    "        ['o', '_', '_']\n",
    "         ]\n",
    "    bestMove_rowy ,bestMove_colz ,bestMove_rowi ,bestMove_colj,d,b = findBestMove(damma,op,pc)\n",
    " \n",
    "    print(\"move the x from the position  :\")\n",
    "    print(\"ROW : \",bestMove_rowi, \"COL :\",bestMove_colj)\n",
    "    print(\"to  :\")\n",
    "    print(\"ROW : \",bestMove_rowy, \"COL :\",bestMove_colz)\n",
    "                           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "1e8975bf",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "moveVal_best    0\n",
      "moveVal_dep    5\n",
      "1     1\n",
      "0     1\n",
      "bestVal    0\n",
      "moveVal_best    10\n",
      "moveVal_dep    2\n",
      "1     1\n",
      "2     1\n",
      "bestVal    10\n",
      "bestdepth    2\n",
      "moveVal_best    -10\n",
      "moveVal_dep    3\n",
      "1     1\n",
      "2     2\n",
      "*************\n",
      "moveVal_best    10\n",
      "moveVal_dep    2\n",
      "  \n",
      "1     2\n",
      "2     2\n",
      "  \n",
      "*************\n",
      "moveVal_best    0\n",
      "moveVal_dep    5\n",
      "  \n",
      "2     0\n",
      "2     1\n",
      "  \n",
      "*************\n",
      "The value of the best Move is :  10\n",
      "move the x from the position  :\n",
      "ROW :  1 COL : 1\n",
      "to  :\n",
      "ROW :  2 COL : 1\n"
     ]
    }
   ],
   "source": [
    "damma('x','o')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "12289975",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "bc0d249125ea1ef0473b6565651d6365923b4488bb4418e637ce37ecb211d5fe"
  },
  "kernelspec": {
   "display_name": "Python 3.8.10 64-bit (windows store)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}