Subversion Repositories Games.Chess Giants

// chessengine.cpp

#include "common.h"

// global variables used in this module only

static wchar_t chessenginemodule_path[MAX_PATH];

static wchar_t chessenginemodule_pathname[MAX_PATH];

static wchar_t chessengineinitfile_pathname[MAX_PATH];

static PROCESS_INFORMATION PlayerEngine_pi;

static HANDLE hChessEngineStdinRd;

static HANDLE hChessEngineStdinWr;

static HANDLE hChessEngineStdoutRd;

static HANDLE hChessEngineStdoutWr;

static int current_obstinacy;

// prototypes of local functions

static void PlayerEngine_Recv (player_t *player);

static void PlayerEngine_Send (player_t *player);

static wchar_t *Move_BuildString (boardmove_t *move);

bool PlayerEngine_Init (player_t *player)

{

   // this function starts a chess engine as a child process. This process's stdin and

   // stdout are redirected to the handles we give it, so that we may read/write to it.

   wchar_t widechar_buffer[256];

   SYSTEM_INFO sysinfo;

   SECURITY_ATTRIBUTES saAttr;

   STARTUPINFO si;

   FILE *fp;

   // reset stuff first

   hChessEngineStdinRd = NULL;

   hChessEngineStdinWr = NULL;

   hChessEngineStdoutRd = NULL;

   hChessEngineStdoutWr = NULL;

   player->wants_hint = false;

   // build the chess engine module path and pathname

   swprintf_s (chessenginemodule_path, WCHAR_SIZEOF (chessenginemodule_path), L"%s/engines/%s", app_path, options.engine.program);

   swprintf_s (chessenginemodule_pathname, WCHAR_SIZEOF (chessenginemodule_pathname), L"%s/engines/%s/%s", app_path, options.engine.program, options.engine.cmdline);

   // prepare the pipes' security attributes

   saAttr.nLength = sizeof (SECURITY_ATTRIBUTES);

   saAttr.bInheritHandle = true; // set the bInheritHandle flag so pipe handles are inherited

   saAttr.lpSecurityDescriptor = NULL;

   // create a pipe for the child process's stdout

   CreatePipe (&hChessEngineStdoutRd, &hChessEngineStdoutWr, &saAttr, 0);

   SetHandleInformation (hChessEngineStdoutRd, HANDLE_FLAG_INHERIT, 0); // ensure the read handle to the pipe for STDOUT is not inherited

   // create a pipe for the child process's stdin

   CreatePipe (&hChessEngineStdinRd, &hChessEngineStdinWr, &saAttr, 0);

   SetHandleInformation (hChessEngineStdinWr, HANDLE_FLAG_INHERIT, 0); // ensure the write handle to the pipe for STDIN is not inherited. 

   // spawn the chess engine process with redirected input and output

   memset (&si, 0, sizeof (si));

   si.cb = sizeof (STARTUPINFOA);

   si.dwFlags = STARTF_USESTDHANDLES;

   si.hStdInput = hChessEngineStdinRd;

   si.hStdOutput = hChessEngineStdoutWr;

   si.hStdError = hChessEngineStdoutWr;

   if (!CreateProcess (chessenginemodule_pathname, // module pathname

                       options.engine.cmdline, // command line

                       NULL, NULL,

                       true, // handles are inherited

                       CREATE_NO_WINDOW | DETACHED_PROCESS | CREATE_NEW_PROCESS_GROUP,

                       NULL,

                       chessenginemodule_path, // process path

                       &si, // STARTUPINFO pointer

                       &PlayerEngine_pi)) // receives PROCESS_INFORMATION

   {

      messagebox.hWndParent = hMainWnd;

      wcscpy_s (messagebox.title, WCHAR_SIZEOF (messagebox.title), LOCALIZE (L"ImportantMessage"));

      wcscpy_s (messagebox.text, WCHAR_SIZEOF (messagebox.text), LOCALIZE (L"Error_ChessEngineInitializationFailed"));

      messagebox.flags = MB_ICONWARNING | MB_OK;

      DialogBox_Message (&messagebox); // display a modeless error message box

      PlayerEngine_Shutdown (player); // on error, shutdown the engine

      return (false);

   }

   // eventually initialize the debug log file

   Debug_Init (L"Chess engine output.txt");

   // build the init file full qualified path name and try to open it

   swprintf_s (chessengineinitfile_pathname, WCHAR_SIZEOF (chessengineinitfile_pathname), L"%s/engines/%s/init.txt", app_path, options.engine.program);

   _wfopen_s (&fp, chessengineinitfile_pathname, L"r");

   // could the init file be opened ?

   if (fp != NULL)

   {

      Debug_Log (L"===Found initialization file, parsing...===\n");

      // SMP HACK -- is our engine Crafty or GNU Chess ? if so, set the max CPUs to use to core max - 1

      // (the computer will look like hung if all CPU is taken)

      if ((wcsistr (options.engine.name, L"Crafty") != NULL) || (wcsistr (options.engine.name, L"GNU Chess") != NULL))

      {

         GetSystemInfo (&sysinfo); // get the number of cores and build the corresponding engine initialization order

         Player_SendBuffer_Add (player, 1000, L"mt %d\n", max (1, sysinfo.dwNumberOfProcessors - 1));

      }

      // read line per line

      while (fgetws (widechar_buffer, WCHAR_SIZEOF (widechar_buffer), fp) != NULL)

      {

         if ((widechar_buffer[0] == L'#') || (widechar_buffer[0] == L'\n'))

            continue; // skip comments and empty lines

         // new command line found, append it to the send buffer

         Player_SendBuffer_Add (player, 1000, widechar_buffer);

      }

      fclose (fp); // finished, close the file

   }

   // everything's okay, set engine name as the player's name

   wcscpy_s (player->name, WCHAR_SIZEOF (player->name), options.engine.name);

   return (true); // finished

}

void PlayerEngine_Shutdown (player_t *player)

{

   // this function terminates the chess engine process and releases all handles attached to it

   unsigned long exit_code;

   unsigned long handle_flags;

   int attempt_index;

   // send the engine a quit command

   Player_SendBuffer_Add (player, 1000, options.engine.command_quit);

   Player_SendBuffer_Add (player, 1000, L"\n"); // since the format string was read from the options, don't forget to end it with a carriage return

   PlayerEngine_Send (player);

   // close the pipe handles

   if (hChessEngineStdinRd)

      CloseHandle (hChessEngineStdinRd);

   hChessEngineStdinRd = NULL;

   if (hChessEngineStdinWr)

      CloseHandle (hChessEngineStdinWr);

   hChessEngineStdinWr = NULL;

   if (hChessEngineStdoutRd)

      CloseHandle (hChessEngineStdoutRd);

   hChessEngineStdoutRd = NULL;

   if (hChessEngineStdoutWr)

      CloseHandle (hChessEngineStdoutWr);

   hChessEngineStdoutWr = NULL;

   // check 10 times if the engine process has ended cleanly

   for (attempt_index = 0; attempt_index < 10; attempt_index++)

   {

      if (GetExitCodeProcess (PlayerEngine_pi.hProcess, &exit_code) && (exit_code != STILL_ACTIVE))

         break; // break as soon as we've told the process exited cleanly

      Sleep (100); // else wait one tenth second

   }

   // has the engine NOT closen by itself yet ?

   if ((attempt_index == 10) && GetExitCodeProcess (PlayerEngine_pi.hProcess, &exit_code) && (exit_code == STILL_ACTIVE))

   {

      Debug_Log (L"===Engine not closen, terminating process manually===\n");

      // terminate the chess engine process using our smart technique ^^

      if (!SafeTerminateProcess (PlayerEngine_pi.hProcess, 0))

         TerminateProcess (PlayerEngine_pi.hProcess, 0); // if process doesn't want to shutdown, kill it

   }

   else

      Debug_Log (L"===Engine closed cleanly===\n");

   if (PlayerEngine_pi.hProcess)

      CloseHandle (PlayerEngine_pi.hProcess);

   PlayerEngine_pi.hProcess = NULL;

   if (GetHandleInformation (PlayerEngine_pi.hThread, &handle_flags))

      CloseHandle (PlayerEngine_pi.hThread);

   PlayerEngine_pi.hThread = NULL;

   // and finally reset the process information structure

   memset (&PlayerEngine_pi, 0, sizeof (PlayerEngine_pi));

   return; // finished

}

bool PlayerEngine_Think (player_t *player)

{

   // this function reads and writes any necessary data from and to the chess engine. Returns TRUE if scene needs to be updated.

   wchar_t line_buffer[256];

   wchar_t *line_pointer;

   wchar_t *move_string;

   int char_index;

   int length;

   boardmove_t move;

   player_t *current_player;

   player_t *opposite_player;

   bool do_update;

   bool is_hint;

   // don't update the scene until told otherwise

   do_update = false;

   // get current and opposite players

   current_player = Player_GetCurrent ();

   opposite_player = Player_GetOpposite ();

   // read from pipe (non-blocking)

   PlayerEngine_Recv (player);

   ////////////////

   // START PARSING

   // read line per line...

   line_pointer = player->recvbuffer; // start at the first character

   while ((line_pointer = ReadACompleteLine (line_buffer, WCHAR_SIZEOF (line_buffer), line_pointer)) != NULL)

   {

      // is it an empty line or engine noise ?

      if ((line_buffer[0] == 0) || iswspace (line_buffer[0]))

         continue; // skip empty lines and engine noise

      // is engine allowed to resign ? if so, check if it's a game results

      if (options.engine.obstinacy_level >= 0)

      {

         // is it a game result AND are we still in play ?

         if ((wcsstr (line_buffer, L"1-0") != NULL) && (the_board.game_state == STATE_PLAYING))

         {

            // have we NOT been obstinate enough ?

            if (current_obstinacy < options.engine.obstinacy_level)

               current_obstinacy++; // if so, discard this resign and go on

            else

            {

               Debug_Log (L"===Engine tells us that black resigns: white wins!===\n");

               // if opponent player is human, play the victory sound, else, play defeat sound

               Audio_PlaySound (opposite_player->type == PLAYER_HUMAN ? SOUNDTYPE_VICTORY : SOUNDTYPE_DEFEAT);

               // display the game over dialog box

               the_board.game_state = STATE_WHITEWIN_RESIGNORFORFEIT;

               DialogBox_EndGame ();

               do_update = true; // remember to update the 3D scene

            }

            continue; // we processed that line

         }

         else if ((wcsstr (line_buffer, L"0-1") != NULL) && (the_board.game_state == STATE_PLAYING))

         {

            // have we NOT been obstinate enough ?

            if (current_obstinacy < options.engine.obstinacy_level)

               current_obstinacy++; // if so, discard this resign and go on

            else

            {

               Debug_Log (L"===Engine tells us that white resigns: black wins!===\n");

               // if opponent player is human, play the victory sound, else, play defeat sound

               Audio_PlaySound (opposite_player->type == PLAYER_HUMAN ? SOUNDTYPE_VICTORY : SOUNDTYPE_DEFEAT);

               // display the game over dialog box

               the_board.game_state = STATE_BLACKWIN_RESIGNORFORFEIT;

               DialogBox_EndGame ();

               do_update = true; // remember to update the 3D scene

            }

            continue; // we processed that line

         }

      }

      // has the game ended already ?

      if (the_board.game_state > STATE_PLAYING)

         continue; // ignore all that the engine tells us. Game is over already.

      // is it a hint ?

      if ((move_string = wcsstr (line_buffer, options.engine.replystring_hint)) != NULL)

      {

         move_string += wcslen (options.engine.replystring_hint); // go to the parsable data

         is_hint = true;

      }

      // else is it a normal move ?

      else if ((move_string = wcsstr (line_buffer, options.engine.replystring_move)) != NULL)

      {

         move_string += wcslen (options.engine.replystring_move); // go to the parsable data

         is_hint = false;

      }

      // else it's any other sort of line

      else

         continue; // skip lines that don't contain any valid move data

      // now we are sure it's either a hint or a move (or some pondering)

      length = wcslen (move_string);

      if ((length < 2) || (length > 9))

         continue; // if string is too long to be a move, skip it

      // there must be valid move data on that line.

      // evaluate the engine move string

      memcpy (move.slots, the_board.moves[the_board.move_count - 1].slots, sizeof (move.slots));

      wcscpy_s (move.pgntext, WCHAR_SIZEOF (move.pgntext), move_string);

      if (!Move_SetupFromSAN (&the_board.moves[the_board.move_count - 1], &move, Board_ColorToMove (&the_board)))

      {

         Debug_Log (L"===Skipping line (invalid move syntax)===\n%s", move_string);

         continue; // so now, if there are NOT two digits AND it's not a kind of castle, it can't be a move so skip that line

      }

      // is it NOT a hint, are blunders allowed, should we do one now AND can we do one now ?

      if (!is_hint && (options.engine.blunder_chances > 0) && (rand () % 100 < options.engine.blunder_chances)

          && Move_FindRandomMove (&the_board.moves[the_board.move_count - 1], player->color, &move))

      {

         Player_SendBuffer_Add (player, 1000, options.engine.command_force, Move_BuildString (&move)); // send the blunderous move to the engine

         Player_SendBuffer_Add (player, 1000, L"\n"); // since the format string was read from the options, don't forget to end it with a carriage return

         if (wcscmp (options.engine.program, L"Crafty") == 0)

            Player_SendBuffer_Add (player, 1000, L"disp\n");

         Debug_Log (L"===Discarding engine move, forcing a blunderous move (%s) instead===\n", Move_BuildString (&move)); // blunder

      }

      // mark the engine's selected and hovered squares

      Board_SetSelectedAndHovered (&the_board, move.source[0], move.source[1], move.target[0], move.target[1]);

      // was it NOT a hint ?

      if (!is_hint)

      {

         Board_AppendMove (&the_board, the_board.selected_position[0], the_board.selected_position[1], the_board.hovered_position[0], the_board.hovered_position[1], move.promotion_type, NULL);

         the_board.has_playerchanged = true; // do the movement and switch players

         // forget the hovered and selected positions

         Board_SetSelectedAndHovered (&the_board, -1, -1, -1, -1);

         animation_endtime = current_time + ANIMATION_DURATION; // wait for animation time seconds

         sound_playtime = current_time + ANIMATION_DURATION - 0.1f; // play sound near the end of animation

      }

      // else it was a hint

      else

         highlight_endtime = current_time + 2.0f; // just highlight this part for a little more than one second

      the_scene.gui.central_text.disappear_time = current_time + 1.0f; // fade the "thinking" phrase out now (FIXME: ugly)

      the_scene.gui.want_spinwheel = false; // stop spinning wheel

      do_update = true; // remember to update the 3D scene

   }

   // now clean the input buffer of all the lines we parsed

   line_pointer = wcsrchr (player->recvbuffer, L'\n'); // reach the last carriage return

   if (line_pointer != NULL)

   {

      line_pointer++; // skip the carriage return

      length = wcslen (line_pointer); // get the remaining string length

      for (char_index = 0; char_index < length; char_index++)

         player->recvbuffer[char_index] = line_pointer[char_index]; // and recopy the remaining string at the beginning of the buffer

      player->recvbuffer[char_index] = 0; // finish the string ourselves

   }

   // END PARSING

   //////////////

   /////////////////////////////////

   // START NOTIFICATIONS PROCESSING

   // have we been notified that the board was just set up ?

   if (the_board.was_setup)

   {

      Debug_Log (L"===Got board setup notification from interface===\n");

      // send a new game command to the chess engine

      Player_SendBuffer_Add (player, 1000, options.engine.command_new);

      Player_SendBuffer_Add (player, 1000, L"\n"); // since the format string was read from the options, don't forget to end it with a carriage return

      // just set up the board from its Forsyth-Edwards notation

      Debug_Log (L"===setting up board using FEN string===\n");

      // instruct it about its allowed search depth BEFORE each table set (this ensures engine will be "ready" to handle the command)

      // then get the current game state in FEN format and feed it to the engine

      Player_SendBuffer_Add (player, 1000, options.engine.command_sd, options.engine.depth);

      Player_SendBuffer_Add (player, 1000, L"\n"); // since the format string was read from the options, don't forget to end it with a carriage return

      Player_SendBuffer_Add (player, 1000, options.engine.command_setboard, the_board.moves[the_board.move_count - 1].fen_string);

      Player_SendBuffer_Add (player, 1000, L"\n"); // since the format string was read from the options, don't forget to end it with a carriage return

      // and reset current obstinacy

      current_obstinacy = 0;

      if (wcscmp (options.engine.program, L"Crafty") == 0)

         Player_SendBuffer_Add (player, 1000, L"disp\n");

   }

   // have we been notified that players are swapping colors ? (N.B. when this happens in human vs. computer mode, it's always that the human player is *GIVING* his turn)

   if (the_board.want_playerswap)

   {

      Debug_Log (L"===Got player SWAP notification from interface===\n");

      Player_SendBuffer_Add (player, 1000, options.engine.command_go); // tell engine it's now the current player

      Player_SendBuffer_Add (player, 1000, L"\n"); // since the format string was read from the options, don't forget to end it with a carriage return

   }

   // have we been notified that the current player just changed ?

   if (the_board.has_playerchanged)

   {

      Debug_Log (L"===Got player change notification from interface===\n");

      // is the current player our color ? (meaning is it engine's turn to play) ?

      if (Board_ColorToMove (&the_board) == player->color)

      {

         // is it NOT a board setup AND has at least one move been played (meaning it was just the other's turn before) ?

         if (!the_board.was_setup && (the_board.move_count > 1))

         {

            Debug_Log (L"===Player just played, sending the chosen move to engine===\n");

            if (wcscmp (options.engine.program, L"Crafty") == 0)

               Player_SendBuffer_Add (player, 1000, L"disp\n");

            // instruct it about its allowed search depth BEFORE each move (this ensures engine will be "ready" to handle the command)

            // then build the move string, and send the move string to the engine

            Player_SendBuffer_Add (player, 1000, options.engine.command_sd, options.engine.depth);

            Player_SendBuffer_Add (player, 1000, L"\n"); // since the format string was read from the options, don't forget to end it with a carriage return

            Player_SendBuffer_Add (player, 1000, Move_BuildString (&the_board.moves[the_board.move_count - 1]));

            Player_SendBuffer_Add (player, 1000, L"\n"); // end the send buffer with a carriage return

         }

         // else game has not started yet, but it's our turn

         else

         {

            Player_SendBuffer_Add (player, 1000, options.engine.command_go); // so let's start the game

            Player_SendBuffer_Add (player, 1000, L"\n"); // since the format string was read from the options, don't forget to end it with a carriage return

         }

      }

   }

   // END NOTIFICATIONS PROCESSING

   ///////////////////////////////

   // is it NOT our turn ?

   if (current_player != player)

   {

      // does our opponent want a hint ?

      if (current_player->wants_hint)

      {

         current_player->wants_hint = false; // don't ask twice

         Debug_Log (L"===Hint requested, asking engine for it===\n");

         Player_SendBuffer_Add (player, 1000, options.engine.command_hint); // ask for a hint

         Player_SendBuffer_Add (player, 1000, L"\n"); // since the format string was read from the options, don't forget to end it with a carriage return

      }

      // does our opponent want to cancel a move ?

      if (current_player->wants_cancel)

      {

         current_player->wants_cancel = false; // don't ask twice (remember now before we switch players)

         Debug_Log (L"===Move cancellation requested, rebuilding board and telling engine to backup 2 moves===\n");

         // rewind game 2 moves back

         the_board.moves = (boardmove_t *) SAFE_realloc (the_board.moves, the_board.move_count, max (1, the_board.move_count - 2), sizeof (boardmove_t), false);

         the_board.move_count = max (1, the_board.move_count - 2); // figure out how many moves we have now

         the_board.viewed_move = the_board.move_count - 1; // take us back to the last move

         // just set up the board from its Forsyth-Edwards notation

         Debug_Log (L"===setting up board using FEN string===\n");

         // instruct it about its allowed search depth BEFORE each table set (this ensures engine will be "ready" to handle the command)

         // then get the current game state in FEN format and feed it to the engine

         Player_SendBuffer_Add (player, 1000, options.engine.command_sd, options.engine.depth);

         Player_SendBuffer_Add (player, 1000, L"\n"); // since the format string was read from the options, don't forget to end it with a carriage return

         Player_SendBuffer_Add (player, 1000, options.engine.command_setboard, the_board.moves[the_board.move_count - 1].fen_string);

         Player_SendBuffer_Add (player, 1000, L"\n"); // since the format string was read from the options, don't forget to end it with a carriage return

         if (wcscmp (options.engine.program, L"Crafty") == 0)

            Player_SendBuffer_Add (player, 1000, L"disp\n");

         do_update = true; // remember to update the 3D scene

      }

   }

   // write to pipe (when we're allowed to)

   if (!player->sendbuffer_locked && (animation_endtime + 1.0f < current_time))

      PlayerEngine_Send (player);

   return (do_update); // finished, return whether we should update the scene or not

}

static void PlayerEngine_Recv (player_t *player)

{

   // helper function to read data from the pipe communicating with the game engine process

   unsigned long amount_to_read;

   unsigned long read_count;

   int byte_index;

   int rewrite_index;

   int length;

   unsigned int initial_pos;

   // get reception buffer's initial end position

   initial_pos = wcslen (player->recvbuffer);

   // as long as the pipe reports us there is data to read...

   while (PeekNamedPipe (hChessEngineStdoutRd, NULL, 0, NULL, &amount_to_read, NULL) && (amount_to_read > 0))

   {

      if (!ReadFile (hChessEngineStdoutRd, player->ascii_recvbuffer, min (amount_to_read, (unsigned long) player->recvbuffer_size - 1), &read_count, NULL))

         break; // read the pipe; if it fails, stop trying

      // parse all received data and eradicate all carriage returns and percent signs

      rewrite_index = 0;

      for (byte_index = 0; byte_index < (int) read_count; byte_index++)

         if ((player->ascii_recvbuffer[byte_index] != '\r') && (player->ascii_recvbuffer[byte_index] != '%'))

         {

            player->ascii_recvbuffer[rewrite_index] = player->ascii_recvbuffer[byte_index];

            rewrite_index++;

         }

      player->ascii_recvbuffer[rewrite_index] = 0; // terminate the buffer ourselves

      // convert to wide char and append it to recvbuffer

      length = wcslen (player->recvbuffer);

      ConvertToWideChar (&player->recvbuffer[length], player->recvbuffer_size - length, player->ascii_recvbuffer);

   }

   // write what we received (if we received anything)

   if (wcslen (player->recvbuffer) > initial_pos)

      Debug_Log (L"===================================RECEIVED:===================================\n%s\n", &player->recvbuffer[initial_pos]);

   return; // finished

}

static void PlayerEngine_Send (player_t *player)

{

   // helper function to send data through the pipe communicating with the game engine process

   wchar_t widechar_buffer[256];

   wchar_t *line_pointer;

   char ascii_buffer[256];

   unsigned long amount_written;

   player->sendbuffer_locked = true; // lock the buffer

   // write what we're sending (if we're sending anything)

   if (player->sendbuffer[0] != 0)

      Debug_Log (L"====================================SENDING:===================================\n%s\n", player->sendbuffer);

   // now read line per line...

   line_pointer = player->sendbuffer; // start at the first character

   while ((line_pointer = wcsgets (widechar_buffer, WCHAR_SIZEOF (widechar_buffer), line_pointer)) != NULL)

   {

      wcscat_s (widechar_buffer, WCHAR_SIZEOF (widechar_buffer), L"\n"); // put the carriage return back

      ConvertTo7BitASCII (ascii_buffer, sizeof (ascii_buffer), widechar_buffer); // convert to ASCII

      WriteFile (hChessEngineStdinWr, ascii_buffer, strlen (ascii_buffer), &amount_written, NULL); // send data

   }

   player->sendbuffer[0] = 0; // what we had to send has been sent, reset the send buffer

   player->sendbuffer_locked = false; // and unlock it

   return; // finished

}

static wchar_t *Move_BuildString (boardmove_t *move)

{

   // helper function to build a move string to send to the engine from a particular board move. NOT THREAD SAFE.

   static wchar_t output_string[8];

   // construct the four first characters

   swprintf_s (output_string, WCHAR_SIZEOF (output_string), L"%c%c%c%c",

               L'a' + move->source[1], L'1' + move->source[0],

               L'a' + move->target[1], L'1' + move->target[0]);

   // append any eventual promotion

   if (move->promotion_type == PART_ROOK)

      wcscat_s  (output_string, WCHAR_SIZEOF (output_string), L"r");

   else if (move->promotion_type == PART_KNIGHT)

      wcscat_s  (output_string, WCHAR_SIZEOF (output_string), L"n");

   else if (move->promotion_type == PART_BISHOP)

      wcscat_s  (output_string, WCHAR_SIZEOF (output_string), L"b");

   else if (move->promotion_type == PART_QUEEN)

      wcscat_s  (output_string, WCHAR_SIZEOF (output_string), L"q");

   return (output_string); // finished, return the move string

}