Artificial Intelligence and Perl

Introduction to Artificial Intelligence

Usually Artificial Intelligence is defined as:

  • An attempt to make computers "more intelligent"
  • An attempt to understand how humans think

Several approaches to AI

Should we concert reasoning or rather acting of computer systems? Should we take humans as a model or establish new guidelines?

 Systems that ReasonSystems that Act
Human model1. User Interface problems2. Turing Test problems
Neo rational3. Computationally complex problems4. Rational agents/bots

Approach 1. With this approach, it is not important to solve tasks correctly. It is important to solve tasks in the same way as humans. Applications of this approach include Man-Machine communication and user interfaces.

Approach 2. This approach is rare in AI, however it is the most popular, there are yearly Turing Test competitions.

Approach 3. This logical approach concerns laws of thought. Informal tasks (usually very computationally complex) should be described using a formalism. Applications include expert systems and games.

Approach 4. This approach describes rational agents. These act in the best way to achieve goals, based on their information about the world. The decisions should be taken even if this information is not sufficient. Applications include all kinds of bots.


AI applications - Linguistics

Natural languages

Any existing human language has the following properties: pretty rich, complex and inconsistent, with a lot of rules and a lot of exceptions. In short, human languages are extremely informal, just like our whole crazy world that these languages try to describe. Constant attempts however are made to teach computers to speak and understand natural languages.

CPAN modules

There are plenty of CPAN modules dealing with different linguistic problems:

Example problem

Smart matching of human names

Are "Mikhail Goihman" and "Mikhael (Migo) Goikhman" the same person?

How about "Bill Gates" and "William Gates III"? Or "Peggy Green" and "Green Mary-Ann"?

The problem is more complex than it sounds, because it is not quite formal. One aspect is name nicks and mutations, like:

Peggy -> Margareth -> Martha -> Mary -> Maryanne -> Anna -> Roseanne -> Rosalyn -> Linda -> Melinda

Some aspects may be solved by a database of names and their relations, but there is certainly a place for heuristics. The problem may be even worse in other languages.

Solving using Perl module

use Lingua::EN::MatchNames;

# 85% of certainty
if (name_eq("Leonardo Da Vinci", "Leonard d'Vinchi") >= 85) {
	print "Match\n";
}

AI applications - Games

Why games are important

Games are integral attribute of human beings. They are perfect for learning and fun, develop conscious reaction and satisfy human's thirst of knowledge and curiosity. So, if computers are going to mimic people they should be able to play games.

Game playing is search problem

Classical game rules are usually perfectly formalized. The optimal game play is a search of the best next state in the game space, defined by:

Game playing is characterized by:

Types of games

 DeterministicChance element
Complete information1. Chess, Checkers, Go2. Backgammon, monopoly
Incomplete information 3. Card games

The first type of games is the easiest to approach (but not certainly the easiest to solve). Other types may be approached similarly by adding chance probability nodes that split (multiply) an otherwise deterministic tree of states.

Tree of two-player, deterministic, turn-based games

Minimax

The perfect play for deterministic complete-information games: Choose move to position (one of the immediate tree nodes) with the highest minimax value, i.e. the best achievable payoff against the best opponent play.

It is possible to skip some subtrees using alpha-beta pruning algorithm:

Minimax algorithm:

Deterministic Games in Practice

In Chess, b (possible moves in typical position) is nearly 40, m (total game play moves) is nearly 100. Typical PC may play like the human master. Deep Blue defeated Garry Kasparov in 1997.

In Checkers on the 8x8 board, a computer program that uses a database of the perfect moves for all positions with 8 or less pieces on the board, is pretty much unbeatable since 1994. International Checkers take place on the 10x10 board. There are Checkers variants with 12x12 and 14x14 boards. The computers will not be able to solve these large boards for many years yet, but they may certainly win an experienced human player.

In Go, b is larger than 300, so the naive minimax approach is not optimal, the pattern based algorithms give better results. Unlike Chess and Checkers, the Go champions refuse to play with computers.


The Checkers Game

Introduction to the Checkers game

The Checkers rules (English and Russian variants)

Board

The regular checkerboard is comprised of 64 squares of contrasting colors, like black and white. The checker pieces may be red and white in color (or any combination of contrasting colors), usually grooved.

The black board squares are numbered either 1 to 32 or using the chess a1 to h8 notation. The diagram below shows the pieces set up for play, with Black occupying squares 1 to 12 (lines 6 to 8 in the chess notation) and White occupying squares 21 to 32 (lines 1 to 3 in the chess notation).

Chess notation:

In many countries (and with boards larger than 8x8) the numerical notation is used instead, all black board squares are numbered from 1 to 32.

Each player (White and Black) controls its own army of pieces. Pieces move only on dark squares which are numbered. The white pieces always move first in opening the game.

The goal

The goal in the checkers game is either to capture all of the opponent's pieces or to blockade them. If neither player can accomplish the above, the game is a draw.

Moves

Starting with White, the players take turns moving one of their own pieces. A piece means either a man (other name is pawn) - an ordinary single checker or a king which is what a man becomes if it reaches the last rank (see kings). A man may move one square diagonally only forward - that is, toward the opponent - onto an empty square.

Captures

Checkers rules state that captures or 'jumps' are mandatory. If a square diagonally in front of a man is occupied by an opponent's piece, and if the square beyond that piece in the same direction is empty, the man may 'jump' over the opponent's piece and land on the empty square. The opponent's piece is captured and removed from the board. Some variants allow only forward direction captures, others allow backward direction captures too.

If in the course of single or multiple jumps the man reaches the last rank, becoming a king, the turn shifts to the opponent. No further 'continuation' jump is possible in some variants of Checkers.

The kings

When a single piece reaches the last rank of the board by reason of a move, or as the completion of a 'jump', it becomes a king; and that completes the move, or 'jump'.

A king can move in any direction and 'jump' in any direction one or more pieces, as the limits of the board permit. The king can only jump diagonally over one adjacent piece at a time, in any of the four diagonal directions. Multiple jumps are possible.

Games::Checkers Perl implementation

Games::Checkers is a set of Perl classes and console scripts for automatic and interactive game plays with basic AI. Replay of the recorded games is supported too, and a database of numerous Checkers tournaments is included. Rules for several 8x8 Checkers variants supported. The classes are extendable for GUI.

This is a typical class diagram for board based games.

Automatic play, example script

use Games::Checkers::Constants;
use Games::Checkers::Board;
use Games::Checkers::BoardTree;

my $board = new Games::Checkers::Board;
my $color = White;
my $numMoves = 0;
print $board->dump;

while ($board->canColorMove($color)) {
        sleep(2);
        exit if $numMoves++ == 200;  # allow 100 moves for each player
        my $boardTree = new Games::Checkers::BoardTree
                ($board, $color, 2);  # think 2 steps ahead
        my $move = $boardTree->chooseBestMove;  # or: chooseRandomMove

        $board->transform($move);
        print $move->dump, "\n", $board->dump;
        $color = ($color == White)? Black: White;
}

print "\n", ["Black", "White"]->[$color == White? 0: 1], " won.\n";

AI and Perl - Conclusions

Perl may be effectivelly used to solve non-CPU intensive AI problems.

Perl is good for prototyping complex AI problems.

Perl is usually not the best choice for computationally complex AI problems.

References