%define FALSE 0 %define TRUE 1 %define PLAYER 0 %define COMP 1 %define UNOCCUPIED 2 %define ONGOING 0 %define DRAWN 1 %define PLAYER_WON 2 %define COMP_WON 3 %define NL 10 %define TAB 9 segment .data ; strings m_title db "Tic Tac Toe!", NL, 0 segment .text global main ; FUNCTION int main(int argc, char **argv) ; entry point for the CRT ; PARAMETERS argc ([ebp+8]) - number of command line arguments ; argv ([ebp+12]) - the arguments ; RETURN 0 for success main: ; prolog push ebp mov ebp, esp push m_title call printf pop ecx call prompt_difficulty mov esi, eax ; difficulty call clear_screen xor ebx, ebx ; num_games = 0 m_game_loop: mov ecx, ebx and ecx, 0x1 ; %= 2 push esi push ecx call play_game add esp, 8 add ebx, 1 jmp m_game_loop ; should never be reached, but for the sake of completeness... xor eax, eax pop ebp ret segment .data ; strings pd_str1 db "Select a difficulty -", NL, 0 pd_str2 db TAB, "1. God. The computer plays perfect games. ", NL, TAB, " You have no mathematical chance of winning.", NL, 0 pd_str3 db TAB, "2. Devil. Thought God mode was too hard? Now try to lose :).", NL, 0 pd_str4 db "? ", 0 pd_str5 db "Enter a number between 1 and 2 inclusive.", NL, "? ", 0 pd_scanf_format_str db "%d", 0 segment .text global prompt_difficulty extern printf, scanf, getchar ; FUNCTION int prompt_difficulty() ; prompts the difficulty level from the user. ; PARAMETERS none ; RETURN 1 (god mode) or 2 (devil mode) %define pd_rtn [ebp-4] prompt_difficulty: ; prolog push ebp mov ebp, esp sub esp, 4 ; print out the lines push pd_str1 call printf push pd_str2 call printf push pd_str3 call printf push pd_str4 call printf add esp, 16 ; delayed pop optimization ; get the choice from the user pd_scanf_loop: lea eax, pd_rtn push eax push pd_scanf_format_str call scanf add esp, 8 cmp eax, 1 je pd_check_range jmp pd_flush_stdin pd_check_range: ; has to be 1 or 2 cmp dword pd_rtn, 1 je pd_out_of_scanf_loop cmp dword pd_rtn, 2 je pd_out_of_scanf_loop push pd_str5 call printf pop ecx jmp pd_scanf_loop pd_flush_stdin: call getchar cmp eax, NL jne pd_flush_stdin push pd_str5 call printf pop ecx jmp pd_scanf_loop pd_out_of_scanf_loop: mov eax, pd_rtn ; epilog add esp, 4 pop ebp ret segment .data ; strings pg_str1 db "The game was drawn.", NL, 0 pg_str2 db "Computer won :(", NL, 0 pg_str3 db "Congratulations! You won!", NL, 0 segment .text global play_game ; FUNCTION void play_game(int first, int difficulty) ; play a game with the user. ; PARAMETERS first ([ebp+8]) - who should go first ; difficulty ([ebp+12]) - difficulty level (1 or 2) ; RETURN none %define pg_first [ebp+8] %define pg_difficulty [ebp+12] ; stack variables ; ebp-36 to ebp-4 %define pg_board_array [ebp-36] %define pg_turn [ebp-40] %define pg_state [ebp-44] %define pg_player_symbol [ebp-48] %define pg_comp_symbol [ebp-52] %define pg_i [ebp-56] %define pg_move [ebp-60] play_game: ; prolog push ebp mov ebp, esp sub esp, 60 push ebx push edi mov eax, pg_first mov dword pg_turn, eax mov dword pg_state, ONGOING lea ebx, pg_board_array cmp dword pg_first, PLAYER je pg_player_first mov dword pg_player_symbol, 'X' mov dword pg_comp_symbol, 'O' jmp pg_symbols_choosing_end pg_player_first: mov dword pg_player_symbol, 'O' mov dword pg_comp_symbol, 'X' pg_symbols_choosing_end: ; initialize the board cld mov edi, ebx mov ecx, 9 mov eax, UNOCCUPIED rep stosd pg_game_loop: push ebx call game_state pop ecx mov pg_state, eax cmp eax, ONGOING jne pg_game_loop_end cmp dword pg_turn, PLAYER jne pg_game_loop_comp_turn ; it's the player's turn push dword pg_comp_symbol push dword pg_player_symbol push ebx call prompt_move add esp, 12 mov dword [ebx + eax*4], PLAYER call clear_screen jmp pg_game_loop_endif pg_game_loop_comp_turn: push dword pg_difficulty push ebx call comp_move add esp, 8 mov dword [ebx + eax*4], COMP pg_game_loop_endif: xor dword pg_turn, 1 jmp pg_game_loop pg_game_loop_end: call clear_screen push dword FALSE push dword pg_comp_symbol push dword pg_player_symbol push ebx call print_board add esp, 16 cmp dword pg_state, COMP_WON jne pg_declare_result_check2 push pg_str2 call printf pop ecx jmp pg_declare_result_end pg_declare_result_check2: cmp dword pg_state, PLAYER_WON jne pg_declare_result_draw push pg_str3 call printf pop ecx jmp pg_declare_result_end pg_declare_result_draw: push pg_str1 call printf pop ecx pg_declare_result_end: ; epilog pop edi pop ebx add esp, 60 pop ebp ret segment .data ; { 0, 1, 2 }, { 3, 4, 5 }, { 6, 7, 8 }, /* horizontal */ ; { 0, 3, 6 }, { 1, 4, 7 }, { 2, 5, 8 }, /* vertical */ ; { 0, 4, 8 }, { 2, 4, 6 } /* diagonals */ gs_groups dd 0, 1, 2, 3, 4, 5, 6, 7, 8, 0, 3, 6, 1, 4, 7, 2, 5, 8, 0, 4, 8, 2, 4, 6 segment .text global game_state ; FUNCTION int game_state(int *board) ; determines the state of the game (PLAYER_WON, COMP_WON, or DRAWN) ; PARAMETERS board ([ebp+8]) - the current board ; RETURN the state of the game %define gs_board [ebp+8] game_state: ; prolog push ebp mov ebp, esp push edi push esi mov edi, gs_board mov esi, gs_groups mov ecx, 8 gs_combo_loop: mov edx, [esi] mov eax, [edi + edx*4] cmp eax, UNOCCUPIED je gs_combo_loop_continue mov edx, [esi+4] cmp [edi + edx*4], eax jne gs_combo_loop_continue mov edx, [esi+8] cmp [edi + edx*4], eax jne gs_combo_loop_continue ; we have a winner! cmp eax, PLAYER jne gs_determine_winner_comp mov eax, PLAYER_WON jmp gs_epilog gs_determine_winner_comp: mov eax, COMP_WON jmp gs_epilog gs_combo_loop_continue: add esi, 12 loop gs_combo_loop ; drawn or ongoing cld mov eax, UNOCCUPIED mov ecx, 9 repne scasd jne gs_not_found mov eax, ONGOING jmp gs_epilog gs_not_found: mov eax, DRAWN gs_epilog: pop esi pop edi pop ebp ret segment .data pm_prompt db "Your move: ", 0 pm_prompt_err db "Enter the number of an empty square.", NL, 0 pm_format db "%d", 0 segment .text global prompt_move ; FUNCTION int prompt_move(int *board, int player_symbol, int comp_symbol) ; prompt a legal move (for the board) from the user ; PARAMETERS board ([ebp+8]) - the current board ; player_symbol ([ebp+12]) - symbol for the player ; comp_symbol ([ebp+16]) - symbol for the comp ; RETURN the move entered %define pm_board [ebp+8] %define pm_player_symbol [ebp+12] %define pm_comp_symbol [ebp+16] %define pm_move [ebp-4] prompt_move: ; prolog push ebp mov ebp, esp sub esp, 4 ; print out the board first push dword TRUE push dword pm_comp_symbol push dword pm_player_symbol push dword pm_board call print_board add esp, 16 jmp pm_input_loop pm_input_loop_err: push pm_prompt_err call printf pop ecx pm_input_loop: push pm_prompt call printf pop ecx lea eax, pm_move push eax push pm_format call scanf add esp, 8 cmp eax, 1 je pm_input_loop_check_range jmp pm_input_loop_cleanup pm_input_loop_check_range: cmp dword pm_move, 9 jg pm_input_loop_err cmp dword pm_move, 1 jl pm_input_loop_err mov eax, pm_move mov edx, pm_board sub eax, 1 cmp dword [edx + eax*4], UNOCCUPIED jne pm_input_loop_err jmp pm_input_loop_out pm_input_loop_cleanup: call getchar cmp eax, NL jne pm_input_loop_cleanup jmp pm_input_loop_err pm_input_loop_out: mov eax, pm_move sub eax, 1 ; epilog add esp, 4 pop ebp ret segment .text global comp_move ; FUNCTION int comp_move(int *board, int difficulty) ; generate a move for the computer player, for difficulty level specified ; PARAMETERS board ([ebp+8]) - the current board ; difficulty ([ebp+12]) - the difficulty level (1 or 2) ; RETURN the move to be made %define cm_board [ebp+8] %define cm_difficulty [ebp+12] %define cm_best_score [ebp-4] %define cm_best_move [ebp-8] comp_move: ; prolog push ebp mov ebp, esp sub esp, 8 ; we need to preserve ebx push ebx mov ebx, cm_board ; initialize the variables mov dword cm_best_score, -999 mov ecx, 9 xor edx, edx cm_loop: cmp dword [ebx + edx*4], UNOCCUPIED jne cm_loop_continue mov dword [ebx + edx*4], COMP push ecx push edx push dword cm_difficulty push dword PLAYER push ebx call minimax add esp, 12 pop edx pop ecx neg eax mov dword [ebx + edx*4], UNOCCUPIED cmp eax, cm_best_score jle cm_loop_continue mov cm_best_score, eax mov cm_best_move, edx cm_loop_continue: add edx, 1 loop cm_loop mov eax, cm_best_move jmp cm_epilog cm_epilog: pop ebx add esp, 8 pop ebp ret segment .data ; memory jump table!! =D mm_jump_table dd mm_ongoing, mm_drawn, mm_player_won, mm_comp_won segment .text global minimax ; FUNCTION int minimax(int *board, int stm, int difficulty) ; evaluate the current board in stm's perspective ; 0 means draw ; 10 means win on board ; 9 means win in 1 ; ... ; -10 means loss on board ; -9 means loss in 1 ; ... ; PARAMETERS board ([ebp+8]) - the current board ; stm ([ebp+12]) - side to move ; difficulty ([ebp+16]) - difficulty level (1 or 2) ; RETURN the score %define mm_board [ebp+8] %define mm_stm [ebp+12] %define mm_difficulty [ebp+16] %define mm_bestmove [ebp-4] %define mm_bestscore [ebp-8] minimax: ; prolog push ebp mov ebp, esp sub esp, 8 ; we need to preserve ebx push ebx mov ebx, mm_board mov dword mm_bestscore, -999 ; call game_state push ebx call game_state pop ecx jmp [mm_jump_table + eax*4] mm_ongoing: mov ecx, 9 xor edx, edx mm_recurse_loop: cmp dword [ebx + edx*4], UNOCCUPIED jne mm_recurse_loop_continue push ecx push edx mov eax, mm_stm mov dword [ebx + edx*4], eax push dword mm_difficulty xor dword mm_stm, 1 push dword mm_stm xor dword mm_stm, 1 push ebx call minimax add esp, 12 pop edx pop ecx neg eax mov dword [ebx + edx*4], UNOCCUPIED cmp eax, mm_bestscore jle mm_recurse_loop_continue mov mm_bestscore, eax mov mm_bestmove, edx mm_recurse_loop_continue: add edx, 1 loop mm_recurse_loop cmp dword mm_bestscore, 0 jle mm_ongoing_le sub dword mm_bestscore, 1 jmp mm_ongoing_end mm_ongoing_le: cmp dword mm_bestscore, 0 je mm_ongoing_end add dword mm_bestscore, 1 mm_ongoing_end: mov eax, mm_bestscore jmp mm_epilog mm_drawn: xor eax, eax jmp mm_epilog mm_player_won: ; if the sum of stm and difficulty is odd, return 10, else -10 mov eax, dword mm_stm add eax, mm_difficulty test eax, 0x1 jnz mm_return_10 jmp mm_return_n10 mm_comp_won: ; if the sum of stm and difficulty is even, return 10, else -10 mov eax, dword mm_stm add eax, mm_difficulty test eax, 0x1 jz mm_return_10 jmp mm_return_n10 mm_return_10: mov eax, 10 jmp mm_epilog mm_return_n10: mov eax, -10 jmp mm_epilog mm_epilog: pop ebx add esp, 8 pop ebp ret segment .data pb_f_beg db NL, NL, NL, NL, 0 pb_f_val db TAB, " %c | %c | %c", NL, 0 pb_f_sep db TAB, "------------", NL, 0 pb_f_end db NL, 0 segment .text global print_board ; FUNCTION void print_board(int *board, int player_symbol, int comp_symbol, int print_numbers) ; print the board to stdout in a human readable format ; PARAMETERS board ([ebp+8]) - the current board ; player_symbol ([ebp+12]) - the symbol used to represent the player ; comp_symbol ([ebp+16]) - the symbol used to represent the computer ; print_numbers ([ebp+20]) - boolean. whether numbers should be used for unoccupied squares ; RETURN none %define pb_board [ebp+8] %define pb_player_symbol [ebp+12] %define pb_comp_symbol [ebp+16] %define pb_print_numbers [ebp+20] %define pb_print_table [ebp-36] print_board: ;prolog push ebp mov ebp, esp sub esp, 36 push edi push esi lea edi, pb_print_table mov esi, pb_board mov ecx, 9 xor edx, edx pb_loop: cmp dword [esi + edx*4], UNOCCUPIED jne pb_loop_occupied cmp dword pb_print_numbers, 0 jne pb_loop_print_numbers mov dword [edi + edx*4], ' ' jmp pb_loop_continue pb_loop_print_numbers: mov dword [edi + edx*4], '1' add dword [edi + edx*4], edx jmp pb_loop_continue pb_loop_occupied: cmp dword [esi + edx*4], PLAYER jne pb_loop_comp mov eax, pb_player_symbol mov dword [edi + edx*4], eax jmp pb_loop_continue pb_loop_comp: mov eax, pb_comp_symbol mov dword [edi + edx*4], eax jmp pb_loop_continue pb_loop_continue: add edx, 1 loop pb_loop pb_loop_end: push pb_f_beg call printf push dword [edi + 8] push dword [edi + 4] push dword [edi + 0] push pb_f_val call printf push pb_f_sep call printf push dword [edi + 20] push dword [edi + 16] push dword [edi + 12] push pb_f_val call printf push pb_f_sep call printf push dword [edi + 32] push dword [edi + 28] push dword [edi + 24] push pb_f_val call printf push pb_f_end call printf add esp, 64 pop esi pop edi add esp, 36 pop ebp ret segment .data cs_cmd db "clear", 0 ;cs_cmd db "cls", 0 ; use the second one for Windows segment .text global clear_screen extern system ; FUNCTION void clear_screen() ; clear the screen using OS functions ; PARAMETERS none ; RETURN none clear_screen: ; prolog push ebp mov ebp, esp push cs_cmd call system pop ecx pop ebp ret