Implements an image recognition captcha.

"; break; case 'admin/modules#description': case 'admin/modules/textimage': case 'admin/textimage': $output = t('Implements an image recognition captcha.'); break; } return $output; } function textimage_captchachallenge(&$form) { $form['captcha_response'] = array ( '#type' => 'textfield', '#title' => t('Captcha Validation'), '#default_value' => '', '#required' => TRUE, '#validate' => array('_captcha_validate' => array()), '#description' => t('Please type in the letters/numbers that are shown in the image above.'), '#prefix' => 'Captcha Image: you will need to recognize the text in it.', ); return $form; } function textimage_captchavalidate(&$captcha_word, &$correct) { $captcha_word = drupal_strtolower($captcha_word); if (($_SESSION['captcha'] != '') && $captcha_word == $_SESSION['captcha']) { $correct = true; } else { $correct = false; form_set_error('captcha_response', t('The image verification code you entered is incorrect.')); } } /** * Implementation of hook_menu(). */ function textimage_menu($may_cache) { $items = array(); $suffix = ''; if (arg(2)!=null) $suffix='/'.arg(2); $items[] = array( 'path' => '_textimage/image'.$suffix, 'title' => t('textimage'), 'callback' => '_textimage_image', 'access' => user_access('access textimages'), 'type' => MENU_CALLBACK ); return $items; } function textimage_perm() { return array('access textimages'); } function textimage_settings() { $fonts_path = variable_get("textimage_fonts_path", ""); $images_path = variable_get("textimage_images_path", ""); //check for GD if (!function_exists(imagecreate)) drupal_set_message(t('Image library not available. Textimage needs the GD library extension to be installed. Please install GD.')); //check for TTF support elseif (!function_exists(imagettftext)) drupal_set_message(t('Your image library does not seem to have TrueType font support. Textimage will work, but will use the default inbuilt font.'),'status'); //check for valid font path elseif ($fonts_path!="" && !is_dir($fonts_path)) drupal_set_message(t('The current font path is invalid. The default font will be used.')); //check for valid image path if ($images_path!="" && !is_dir($images_path)) drupal_set_message(t('The current images path is invalid. No images will be used.')); //Fonts settings $form['fonts'] = array( '#type' => 'fieldset', '#title' => t('Fonts settings'), '#collapsible' => TRUE, '#collapsed' => FALSE ); $form['fonts']['textimage_use_only_upper'] = array( '#type' => 'checkbox', '#title' => t('Use only Uppercase'), '#default_value' => variable_get('textimage_use_only_upper',0) ); $form['fonts']['textimage_fonts_path'] = array( '#type' => 'textfield', '#title' => t('TrueType Fonts Path'), '#default_value' => $fonts_path, '#size' => 30, '#maxlength' => 255, '#description' => t('Location of the directory where the Truetype (.ttf) fonts are stored. If you do not provide any fonts, the module will use the default font for text. Relative paths will be resolved relative to the Drupal installation directory.'), ); $form['fonts']['textimage_font_size'] = array( '#type' => 'textfield', '#title' => t('Font Size'), '#default_value' => variable_get('textimage_font_size',24), '#size' => 5, '#maxlength' => 2, '#description' => t('Font size of Captcha text (in pixels).'), '#validate' => array("_textimage_number_validate" => array("textimage_font_size")), ); $form['fonts']['textimage_char_spacing_max'] = array( '#type' => 'textfield', '#title' => t('Character Spacing'), '#default_value' => variable_get('textimage_char_spacing_max',10), '#size' => 5, '#maxlength' => 4, '#description' => t('Sets the kerning between letters in Captcha. Higher numbers indicate more spacing.'), '#validate' => array("_textimage_number_validate" => array("textimage_char_spacing_max")), ); $form['fonts']['textimage_char_jiggle_amount'] = array( '#type' => 'textfield', '#title' => t('Character Jiggle'), '#default_value' => variable_get('textimage_char_jiggle_amount',5), '#size' => 5, '#maxlength' => 2, '#description' => t('Sets the amount of up and down movement in the Captcha letters. Higher numbers indicate more jiggling.'), '#validate' => array("_textimage_number_validate" => array("textimage_char_jiggle_amount")), ); $form['fonts']['textimage_char_rotate_amount'] = array( '#type' => 'textfield', '#title' => t('Character Rotation'), '#default_value' => variable_get('textimage_char_rotate_amount',5), '#size' => 5, '#maxlength' => 2, '#description' => t('Sets the amount of rotation in the Captcha letters (in degrees, only works with non-default fonts).'), '#validate' => array("_textimage_number_validate" => array("textimage_char_rotate_amount")), ); $form['fonts']['textimage_char_size_amount'] = array( '#type' => 'textfield', '#title' => t('Character Size Adjustment'), '#default_value' => variable_get('textimage_char_size_amount',2), '#size' => 5, '#maxlength' => 2, '#description' => t('Sets the amount of variation in size between the different letters in the Captcha (in pixels).'), '#validate' => array("_textimage_number_validate" => array("textimage_char_size_amount")), ); //Image settings $form['images'] = array( '#type' => 'fieldset', '#title' => t('Image settings'), '#collapsible' => TRUE, '#collapsed' => FALSE ); $form['images']['textimage_images_path'] = array( '#type' => 'textfield', '#title' => t('Background Images Path'), '#default_value' => $images_path, '#size' => 30, '#maxlength' => 255, '#description' => t('Location of the directory where the background images are stored. If you do not provide a directory, solid colors will be used. Relative paths will be resolved relative to the Drupal installation directory.'), ); $form['images']['textimage_image_noise'] = array( '#type' => 'textfield', '#title' => t('Image Noise (pixels)'), '#default_value' => variable_get('textimage_image_noise',4), '#size' => 5, '#maxlength' => 4, '#description' => t('Sets the amount of noise (random pixels) in the Captcha image. Higher numbers indicate more noise.'), '#validate' => array("_textimage_number_validate" => array("textimage_image_noise")), ); $form['images']['textimage_image_lines'] = array( '#type' => 'textfield', '#title' => t('Image Noise (lines)'), '#default_value' => variable_get('textimage_image_lines',4), '#size' => 5, '#maxlength' => 4, '#description' => t('Sets the amount of noise (random lines) in the Captcha image. Higher numbers indicate more noise.'), '#validate' => array("_textimage_number_validate" => array("textimage_image_lines")), ); $form['images']['textimage_image_margin'] = array( '#type' => 'textfield', '#title' => t('Image Margin'), '#default_value' => variable_get('textimage_image_margin',10), '#size' => 5, '#maxlength' => 4, '#description' => t('Set a distance between the Captcha letters and the edges of the image.'), '#validate' => array("_textimage_number_validate" => array("textimage_image_margin")), ); $form['info'] = array( '#type' => 'fieldset', '#title' => t('Image and font information'), '#collapsible' => TRUE, '#collapsed' => FALSE ); if (isset($fonts_path)) { $imagefontinfo .= t('Number of fonts found: ').count(_textimage_font_list()); } if (isset($images_path)) { $imagefontinfo .= '
'.t('Number of background images found: ').count(_textimage_image_list()); } $gdinfo = gd_info(); $imagefontinfo .= '
'.t('GD Version: ').$gdinfo["GD Version"]; $imagefontinfo .= '
'.t(' FreeType Support: '); $imagefontinfo .= ($gdinfo["FreeType Support"]==true) ? 'True' : 'False'; $imagefontinfo .= '
'; $form['info']['captcha_info'] = array ( '#type' => 'item', '#value' => $imagefontinfo, ); return $form; } function textimage_settings_form_validate ($form_id,$form) { //check for valid font path if ($form['textimage_fonts_path'] !="" && !is_dir($form['textimage_fonts_path'])) form_set_error('textimage_fonts_path', t('The entered font path is invalid')); //check for valid image path if ($form['textimage_images_path'] !="" && !is_dir($form['textimage_images_path'])) form_set_error('textimage_images_path', t('The entered image path is invalid')); } function _textimage_number_validate ($field,$fieldName) { if (!is_numeric($field['#value'])) { form_set_error($fieldName,t("The value for")." ".t($field['#title'])." ".t("must be a number")); } } /** * Prints an image containing a textimage code. */ function _textimage_image() { //if we don't have GD2 functions, we can't generate the image if (!function_exists('imagecreatetruecolor')) return; // Set headers header('Expires: Mon, 01 Jan 1997 05:00:00 GMT'); header('Cache-Control: no-store, no-cache, must-revalidate'); header('Cache-Control: post-check=0, pre-check=0', false); header('Pragma: no-cache'); header('Content-type: image/png'); $string = _textimage_code(); // Get truetype font list $fonts = _textimage_font_list(); // Get the background images list $images = _textimage_image_list(); // Randomization amounts: $charSpacingMax = variable_get('textimage_char_spacing_max',10); // Letter spacing max (pixels) $charSpacingMin = max($charSpacingMax*.5,0); // Letter spacing minimum (pixels) $charJiggleAmount = variable_get('textimage_char_jiggle_amount',5); // Up and down randomization (pixels) $charRotateAmount = variable_get('textimage_char_rotate_amount',5); // Character rotation amount (degrees) $charSizeAmount = variable_get('textimage_char_size_amount',2); // Character size amount (pixels) $imageRotateAmount = variable_get('captcha_image_rotate_amount',12); // Image rotation amount (degrees) // Static amounts: $charInitialSize = variable_get('textimage_font_size',24); // Initial Font $imageNoise = variable_get('textimage_image_noise',4); // Amount of noise added to image $imageLines = variable_get('textimage_image_lines',4); // Amount of noise added to image $imageMargin = variable_get('textimage_image_margin',10); // Margin around image (pixels) // write text using a truetype font if (function_exists(imagettftext) && count($fonts) > 0) { // Initialize variables for the loop $characterDetails = array(); // contains the final info about each character // Build a list of character settings for the captcha string for ($i=0;$i $charSize, "angle" => $charAngle, "x" => $x, "y" => $y, "color" => $foreground, "font" => $font, "char" => $char ); // Increment the image size $imageWidth = $x + $charWidth; $imageHeight = max($imageHeight,$y+$charJiggleAmount); } // Create the image based off the string length and margin if (count($images) > 0) { // We're going to be using an image, and need a tranparent background to start with $im = _textimage_create_transparent_image($imageWidth+2*$imageMargin, $imageHeight+2*$imageMargin); $noisecolor = imagecolorallocatealpha($im, 0, 0, 0, 127); } else { // Just make a plain-jane color brackground $im = imagecreatetruecolor($imageWidth+2*$imageMargin, $imageHeight+2*$imageMargin); $background = imagecolorallocate($im, rand(180, 250), rand(180, 250), rand(180, 250)); $noisecolor = $background; imagefill($im, 0, 0, $background); } // Specify colors to be used in the image $foreground = imagecolorallocate($im, rand(0, 80), rand(0, 80), rand(0, 80)); foreach($characterDetails as $char) { // draw character imagettftext($im,$char['size'],$char['angle'],$char['x']+$imageMargin,$char['y']+$imageMargin,$foreground,$char['font'],$char['char']); } } else { // write text using a built-in font $x = 0; $y = 0; $imageWidth = 60 + drupal_strlen($string)*$charSpacingMax*.35; $imageHeight = 30 + $charJiggleAmount; // Create the image if (count($images) > 0 && function_exists(imagecolorallocatealpha)) { // We're going to be using an image, and need a tranparent background to start with $im = _textimage_create_transparent_image($imageWidth, $imageHeight); $noisecolor = imagecolorallocatealpha($im, 0, 0, 0, 127); } else { // Just make a plain-jane color brackground $im = imagecreatetruecolor($imageWidth, $imageHeight); $background = imagecolorallocate($im, rand(180, 250), rand(180, 250), rand(180, 250)); $noisecolor = $background; imagefill($im, 0, 0, $background); } // Add the text for ($i=0;$i 0) { // Prepare a larger image with a background image $im2 = _textimage_create_transparent_image($imageWidth, $imageHeight); } else { // Prepare a larger image with a solid color $im2 = imagecreatetruecolor($imageWidth, $imageHeight); imagefill($im2, 0, 0, $background); } $result = imagecopyresampled ($im2, $im, $imageMargin, $imageMargin, 0, 0, $imageWidth, $imageHeight, imagesx($im), imagesy($im)); $im = $im2; } // strikethrough imageline($im, rand(0, 120), rand(0, 120), rand(0, 120), rand(0, 120), $foreground); // Add Noise for ($x=0; $x<$imageWidth; $x++) { for ($row=0; $row<$imageNoise;$row++) { $y = rand(0,$imageHeight); imagesetpixel($im, $x, $y, $noisecolor); } } // Add Lines and Ellipses for ($x=0; $x<$imageLines;$x++) { imageline($im, rand(0, $imageWidth), rand(0, $imageHeight), rand(0, $imageWidth), rand(0, $imageHeight), $noisecolor); imageellipse($im, rand(0, $imageWidth), rand(0, $imageHeight), rand(0, $imageWidth), rand(0, $imageHeight), $noisecolor); } // Fill image with a random background image if available if (count($images) > 0) { $image = $images[rand(0,count($images)-1)]; _textimage_apply_background_image($im,$image); } //output to browser imagepng($im); imagedestroy($im); } /** * Returns a random string for use in a captcha */ function _textimage_code() { $consts='bcdgjxvmnprst'; $vowels='aeiou'; for ($x=0; $x < 6; $x++) { mt_srand ((double) microtime() * 1000000); $const[$x] = drupal_substr($consts,mt_rand(0,drupal_strlen($consts)-1),1); $vow[$x] = drupal_substr($vowels,mt_rand(0,drupal_strlen($vowels)-1),1); } $string = $const[0] . $vow[0] .$const[2] . $const[1] . $vow[1] . $const[3] . $vow[3] . $const[4]; $string = drupal_substr($string,0,rand(4,6)); //everytime we create a new code, we write it to session $_SESSION['captcha'] = drupal_strtolower($string); if(variable_get('textimage_use_only_upper',0)) $string = drupal_strtoupper($string); return $string; } /** * Returns an array of files with TTF extensions in the specified directory. */ function _textimage_font_list() { $fontdir = variable_get("textimage_fonts_path", ""); $filelist = array(); if (is_dir($fontdir) && $handle = opendir($fontdir)) { while ($file = readdir($handle)) { if (preg_match("/\.ttf$/i",$file) == 1) $filelist[] = $fontdir.'/'.$file; } closedir($handle); } return $filelist; } /** * Returns an array of files with jpg, png, and gif extensions in the specified directory. */ function _textimage_image_list() { $imagesdir = variable_get("textimage_images_path", ""); $filelist = array(); if (is_dir($imagesdir) && $handle = opendir($imagesdir)) { while ($file = readdir($handle)) { if (preg_match("/\.gif|\.png|\.jpg$/i",$file) == 1) $filelist[] = $imagesdir.'/'.$file; } closedir($handle); } return $filelist; } /** * Overlays an image to the supplied image resource */ function _textimage_apply_background_image (&$imageResource,$imageFile) { $backgroundResource = image_gd_open($imageFile,substr($imageFile,-3)); // Copy the text onto the background $backX = imagesx($backgroundResource); $backY = imagesy($backgroundResource); $textX = imagesx($imageResource); $textY = imagesy($imageResource); $randomBackX = rand(0,$backX-$textX); $randomBackY = rand(0,$backY-$textY); // Place the text onto a random location of the background image imagecopyresampled($backgroundResource,$imageResource,$randomBackX,$randomBackY,0,0,$textX,$textY,$textX,$textY); // Crop the background image to the original image size imagecopyresampled($imageResource,$backgroundResource,0,0,$randomBackX,$randomBackY,$textX,$textY,$textX,$textY); } /** * Creates transparent image resources for images with graphic backgrounds */ function _textimage_create_transparent_image($x, $y) { $i = imagecreatetruecolor($x, $y); $b = imagecreatefromstring(base64_decode(_text_image_blankpng())); imagealphablending($i, false); imagesavealpha($i, true); imagecopyresized($i, $b ,0 ,0 ,0 ,0 ,$x, $y, imagesx($b), imagesy($b)); return $i; } function _text_image_blankpng() { $c = "iVBORw0KGgoAAAANSUhEUgAAACgAAAAoCAYAAACM/rhtAAAABGdBTUEAAK/INwWK6QAAABl0RVh0U29m"; $c .= "dHdhcmUAQWRvYmUgSW1hZ2VSZWFkeXHJZTwAAADqSURBVHjaYvz//z/DYAYAAcTEMMgBQAANegcCBNCg"; $c .= "dyBAAA16BwIE0KB3IEAADXoHAgTQoHcgQAANegcCBNCgdyBAAA16BwIE0KB3IEAADXoHAgTQoHcgQAAN"; $c .= "egcCBNCgdyBAAA16BwIE0KB3IEAADXoHAgTQoHcgQAANegcCBNCgdyBAAA16BwIE0KB3IEAADXoHAgTQ"; $c .= "oHcgQAANegcCBNCgdyBAAA16BwIE0KB3IEAADXoHAgTQoHcgQAANegcCBNCgdyBAAA16BwIE0KB3IEAA"; $c .= "DXoHAgTQoHcgQAANegcCBNCgdyBAgAEAMpcDTTQWJVEAAAAASUVORK5CYII="; return $c; } ?> Search |


: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /var/www/oellermann/includes/ on line 291.

Modern game programs gain their power from extending the knowledge coded into their evaluation functions through tree search. This is where the machine's "intelligence" is located. Before we get into the mechanics of game trees, though, let us first discuss what they are.

Search Tree

The diagram above shows a portion of the game tree for Noughts and Crosses. In the diagram, the arrows indicate moves. At the top of the tree is the starting position. The next level contains the various possible moves for O (obviously some have been omitted for space reasons). The next level contains all possible replies by X, followed by possible replies by O, and so forth. Each level (or move by one player) is referred to as a ply, while the various positions in the tree are called nodes. A node in which the game is finished is called a leaf node.

Tree search generally works by assigning scores to the leaf nodes - perhaps 1 for a win by O, -1 for a win by X or 0 for a draw. One then backs up one ply, and considers the scores in the child nodes from the perspective of the side to move. Assuming that the side to move is playing to win, the score at the parent node is equal to the best child score from the perspective of the side to move at the parent node. In this way, the scores are "backed up" the tree to the root node. The computer will then make the move with the highest score from it's perspective at the root node. Given this kind of win/lose/draw evaluation at the leaf nodes of the full game tree, the computer can play perfectly.

It is obvious that in Noughts and Crosses, the entire game tree is only nine ply deep. In addition, the number of available moves ("branching factor") decrements with each additional ply. This makes the size of the game tree conveniently small - in fact, there are less than a million possible positions in the tree. However, in a game like Morabaraba the branching factor does not decrease, and in fact can increase in the mid-game (where captures may introduce significant branching) and the endgame (where "flying cows" introduce large amounts of branching). In addition, the game tree is considerably deeper - although I haven't done the analysis, 50 ply or more seems quite reasonable. Due to the astronomical number of nodes involved, therefore, it may be computationally infeasible to exhaustively analyse the tree to its full depth, even if you own a supercomputer - although note that the game tree for Nine Men's Morris has been solved by a combination of retrograde analysis and search. However, you certainly can't even come close in any reasonable period of time. For this reason, game programmers compromise by searching the tree only to a limited depth. Obviously, the nodes at this limited depth are much more difficult to score accurately, and in fact Morabaraba software will generally use an evaluation function which "guesses" to what extent White or Black has an advantage. This guess is based on heuristics programmed into the evaluation function.

Even so, however, the game tree grows exponentially with each extra ply. It is therefore impossible with the limited storage available to build a game tree of any useful size in the computer's memory. That's where Minimax comes in. The Minimax algorithm is a piece of intense cuteness first described by Claude Shannon in 1950, which enables a program to navigate the game tree one "line" (series of moves) at a time, scoring the leaf nodes and backing the scores up the game tree as it goes. This is achieved by recursively calling itself for each child node up to a defined maximum depth. Negamax is a small modification, where each return value from a recursive call is negated. This simplifies choosing the best move from the side-to-move's perspective, as the largest value is always the best, whichever side is to move. Consider the following Negamax pseudocode:


Function Negamax(Depth as integer) as integer
If Depth = 0
Score = Evaluation of Position
Generate List of Moves
For each Move in the move list
Execute the Move
MoveScore = -Negamax(Depth -1)
If MoveScore > Score the Score = MoveScore
Undo the Move
End If
Return Score
End Function

By calling Negamax with some value for depth on each move available in the root node, you will obtain a score for each move - you simply need to make the move with the best score.

At this point I should mention some performance considerations. Your evaluation function is called for each leaf node - at the widest portion of the tree. It is therefore almost certain to be called a massive number of times, making speed critical in this area. It is generally true that a more accurate evaluation function will run slower, and some balance needs to be found. It is also true that a relatively simple evaluation function, applied to a tree of reasonable depth, can produce surprisingly sophisticated results. The process of searching the tree "enriches" the knowledge contained in the evaluation function. This is called artificial intelligence.

Alpha-Beta Pruning
Alpha-beta pruning is a cunning device whereby the effective branching factor of the tree search is reduced, while guaranteeing the same result as a full Minimax search of the same depth. This is achieved by "pruning" (omitting) irrelevant portions of the game tree. Although it is generally considered difficult to wrap your brain around alpha-beta, it is definitely worthwhile: the experts say that when implemented properly, alpha-beta can double the depth of your search within the same time limits. Given equivalent evaluation functions, an eight-ply search will shred a four-ply search.

AlphaBeta Search

Imagine you're doing a minimax search of the tree given above. You've searched f, and found it's children's evaluations to be 11, 12, 7 and 9; at this level of search, it is the first player to move. We would expect him to choose the best of these values (12), and so the minimax value of f is 12.

Next, you start searching g. It's first child returns a value of 15. Whatever happens, therefore, you know that the value of g will be at least 15. However, you know the since f is only worth 12, at node b player 2 will always select f's score of 12 rather than going for a score of at least 15. In this way, we do not have to evaluate the rest of g's children; we can prune them, secure in the knowledge that we are not changing the ultimate evaluation. Now imagine that the pruned children of g in fact contain subtrees of their own - by pruning these, we have saved a considerable amount of labour. Consider the diagram below:

Deep Prune

Continuing from the previous example, we've found that g, h and I are all better than 12, so we know that the overall evaluation for b is 12. Now we search node c, and two levels down we see an evaluation of 10 at node n.

We can use a more complicated line of reasoning to prune again. We know that n will return 10 or smaller. We don't know whether this value of 10 or smaller will be returned at j as well, or whether one of j's other children will be better. If a value of 10 or smaller is returned from j to c, we can prune at c because it has a better sibling (b). So in this case, further exploration of n's children is pointless. In the other case, where one of j's other children returns a value better than 10, further exploration of n's children is also pointless. So we can safely prune n's other children as soon as we see 10.

In general, when a returned value is better than the value of a sibling an even number of levels up in the tree, we can return immediately. This is called a cutoff. If we pass the minimum value of any of these siblings in as a parameter beta to the search, we can do this pruning very efficiently. We also use another parameter alpha to keep track of the siblings at odd levels of the tree. As you will see in the pseudocode below, based on the negamax code given previously, we simply swap the values of alpha and beta as we recurse down the tree.


Function AlphaBeta(Depth as integer, Alpha as integer, Beta as integer) as integer

If (Depth = 0) or (game is over)
Score = Evaluation of Position
Generate List of Moves
Sort List of Moves
For each Move in the move list
Execute the Move
MoveScore = -AlphaBeta(Depth -1, -Beta, -Alpha)
Undo the Move
If MoveScore >= Beta return MoveScore
If MoveScore > Alpha then Alpha = MoveScore
End If
Return Alpha
End Function

Something which may be a little enigmatic in this pseudocode is the "sort list of moves" step. The idea here is that by considering the best moves first, we will get more cutoffs when considering weaker moves. In this way, the alpha-beta algorithm becomes most efficient. Unfortunately, though, we do not know which is the best move - that's why we're doing this search! The answer is of course to guess the value of each move. This can be done in several different ways; you could use your evaluation function to guess the value of each move, or you could use a shallow alpha-beta search to obtain a more accurate result. You should experiment with this to find the right performance balance. Often slowing things down a bit by ordering the move list properly can actually shorten the search because of the increased number of cutoffs.

Time Control
A critical question, with both MiniMax and alpha-beta, is this: how do I know how deep to search? Obviously, you want to go as deep as you can, in order to arrive at the best level of play. However, if your search exceeds the time control, you will forfeit the game. It is very difficult to know before starting the search how long a search of any given depth will take. The solution used by competitive AI programs is called iterative deepening. The idea is to start with a shallow search and increment the search depth and re-search the position until time runs out. In this case, when time does run out, you will have a good move to make - the result of the last completed search.

Most will immediately object that it's enormously wasteful to do a 2-ply, then a 3-ply, then a 4-ply, then an n-ply search, but it really isn't that bad. In the first instance, the last search will likely take more time than all of the previous searches together. The cost of doing the shallow searches is quite small, especially when weighed against the possibility of forfeiting the game. In the second instance, results of earlier searches can be used to sort the move list at the root node more accurately, thus obtaining more cutoffs in the deeper search. This may even reduce the overall search time.

A number of refinements have been suggested and tried. These include the killer and history heuristics, aspiration search, the null move, memory-enhanced test (MTD(f) ), NegaScout and others. These are usually a small modification of the alpha-beta algorithm which seeks to reduce the size of the tree searched. The utility and riskiness of many of them is still the subject of great contention, and therefore they are not discussed here. Should you wish to look into these, a great deal of material is available on the Internet.