2009. október 15., csütörtök

A Simple example of Artificial Intelligence using Delphi Array


Problem/Question/Abstract:

A Simple example of Artificial Intelligence using Delphi Array (Computer simulates learning process of human, learning by correcting mistakes !)

Answer:

Artificial Intelligence (AI) is an advance branch of science that studies the process of human thinking and attempts to apply the knowledge to simulate the same process in machines.  As computers are far ahead in the marathon of processing machines, AI is considered to be the branch of Computer Science than that of General Science.
There have been many research and development in the field of Artificial Intelligence. The area of research include speech and pattern recognition, natural language processing, learning from previous experiences (learning by making and correcting mistakes!), reasoning under the situations providing limited or incomplete information etc. AI is practically applied in the field of computer games, expert systems, neural networks, robotics and many other fields of science and technology.

In this article we will try to demonstrate a very simple practical example of artificial Intelligence programming in Delphi using Delphi arrays. I have chosen a Nepali game named "GATTA TIPNE KHEL" (meaning pebble picking game) for this purpose. We can see small children playing this game in the playground.

(By the way, Nepal, my nation, is a small Asian country between India and China. Recently Nepal was in the main highlight of media for the notorious Royal Massacre in which the whole family of the ruling king were cruelly killed.)

In this pebble picking game a pile of some pebbles is kept in the ground. One of the two players picks one, two or three pebbles at a time in his turn, leaving the pile for the other player to pick for his alternate turn. In this alternate picking process, the player who picks the last pebble(s) will be the loser and called to be a DOOM in Nepali.  
The main logic of the game is to leave the pile of pebbles with 13, 9, 5 or 1 pebble(s) for the opponent to pick.
In the program the starting number of pebbles are set to 17, 21, 25, 29 … etc. so that computer could win always if it does not make a mistake. But in the real play computer seems to be gradually learning by correcting mistakes of the previously played games. At last it finds all its mistakes and corrects them to become an unbeatable champion. It seems computer simulates the psychological learning process of animal, learning by correcting and not repeating the mistakes.
A multidimensional array of elements (1..4,1..3) is chosen as the instruction book for the computer to pick the pebbles. The instruction book contains four pages with three lines of instructions to pick pebbles. The first line instructs to pick a single pebble, the second line instructs to pick 2 and the third line instructs to pick 3 pebbles. At the beginning, computer chooses a random page and a random line of instruction to pick the pebble. When the game finishes, if computer looses the game, the last instruction is red-marked (erased) and the instruction will not be read in the future. After playing many games, all the instructions leading to a lost game will be red marked and there will be left only the instructions those lead to a win.  

Well, it is enough for the description of the game.
Let us jump directly to the code below:

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
  StdCtrls, ExtCtrls, Buttons;

type
  TForm1 = class(TForm)
    Panel1: TPanel;
    LabelPeb1: TLabel;
    LabelPeb2: TLabel;
    Panel2: TPanel;
    Panel3: TPanel;
    Panel4: TPanel;
    Label1: TLabel;
    ComboBox1: TComboBox;
    Label2: TLabel;
    Label3: TLabel;
    Label4: TLabel;
    Label5: TLabel;
    Label6: TLabel;
    LabelIWon: TLabel;
    LabelYouWon: TLabel;
    LabelTotPlayed: TLabel;
    ListBox1: TListBox;
    GroupBox1: TGroupBox;
    BitBtn1: TBitBtn;
    BitBtn2: TBitBtn;
    BitBtn3: TBitBtn;
    BitBtn5: TBitBtn;
    Panel5: TPanel;
    Labelbtn: TLabel;
    BitBtnResign: TBitBtn;
    Label7: TLabel;
    procedure FormCreate(Sender: TObject);
    procedure ComboBox1Change(Sender: TObject);
    procedure BitBtnResignClick(Sender: TObject);
    procedure LabelbtnClick(Sender: TObject);
    procedure BitBtn1Click(Sender: TObject);
  private
    { Private declarations }

    //Procedure to display remaining Pebbles
    procedure DispPebbles(const nPebs: integer);
    //Procedure to reset Variables and Labels after a game is finished
    procedure Finish;
    //Procedure to enable or Disable some controls;
    procedure ManageEnabling(lValue: Boolean);
    //Procedure to display winning or loosing messages
    procedure Messaging(const lost: Boolean; const resigning: Boolean);
    //Real Procedure for playing the game
    procedure LearnByMistakes;
  public
    { Public declarations }
  end;

var
  Form1: TForm1;

implementation

{$R *.DFM}

var
  PlayedGames, ComputerWon: Integer;
  totPebs, RemainPebs, nTurn: Integer;
  OldPageNum, OldLineNum: Integer;

  //18 possible permutations of 3 digits: 1,2 and 3
  //to determine the number of pebbles to take for the computer
  aPermutations: array[1..6, 1..3] of integer;
  // A book containing the instruction pages(4) and lines(3 in each page) to draw the pebbles for the computer
  aPages: array[1..4, 1..3] of integer;

procedure TForm1.FormCreate(Sender: TObject);
// Permutations of 1,2 and 3  in the group of 3s to fill the permutation Array
const
  cPermutations = '123132213231312321';
var
  x, y: Integer;
begin
  //Filling  Permutation Array
  for x := 1 to 6 do
    for y := 1 to 3 do
      aPermutations[x, y] := strtoInt(copy(cPermutations, (x - 1) * 3 + y, 1));
  //Filling the lines of all pages of the instruction Book (array aPages[1..4,1..3]).
  for x := 1 to 4 do
    for y := 1 to 3 do
      aPages[x, y] := y;
  ComboBox1.ItemIndex := 1;
  PlayedGames := 0;
  ComputerWon := 0;
  totPebs := 17; {Default to 17 pebbles}
  RemainPebs := 17; {All are intact up to Now}
end;

procedure TForm1.DispPebbles(const nPebs: integer);
begin
  LabelPeb1.Caption := intToStr(nPebs);
  LabelPeb2.Caption := LabelPeb1.Caption;
end;

procedure TForm1.ManageEnabling(lValue: Boolean);
begin
  BitBtn1.Enabled := lValue;
  BitBtn2.Enabled := lValue;
  BitBtn3.Enabled := lValue;
  Labelbtn.Enabled := lValue;
  BitBtnResign.Enabled := lValue;
  GroupBox1.Enabled := lValue;
  if (RemainPebs < 3) and (RemainPebs > 0) and lValue then
  begin
    if RemainPebs < 3 then
      BitBtn3.Enabled := False;
    if RemainPebs < 2 then
      BitBtn2.Enabled := False;
  end

end;

procedure TForm1.Finish;
begin
  LabelTotPlayed.caption := intToStr(PlayedGames);
  LabelIWon.caption := intToStr(ComputerWon);
  LabelYouWon.caption := intToStr(PlayedGames - ComputerWon);
  DispPebbles(strToInt(ComboBox1.Items[ComboBox1.ItemIndex]));
  totPebs := strtoint(LabelPeb1.Caption);
  RemainPebs := totPebs;
  ManageEnabling(True);
  ComboBox1.Enabled := True;
  Labelbtn.Enabled := False;
  BitBtnResign.Enabled := False;
end;

procedure TForm1.ComboBox1Change(Sender: TObject);
begin
  DispPebbles(strToInt(ComboBox1.Items[ComboBox1.ItemIndex]));
  totPebs := strtoint(LabelPeb1.Caption);
  RemainPebs := totPebs;
end;

procedure TForm1.Messaging(const lost: Boolean; const resigning: Boolean);
begin
  inc(PlayedGames);
  MESSAGEBEEP(0);
  if lost then
  begin
    if resigning then
      showmessage('I Resign ! You won the game again !!')
    else
      showmessage('Congratulations ! You won !! I acknowledges defeat !');
  end
  else
  begin
    inc(ComputerWon);
    showmessage('Hi !  You lost ! I WON THIS GAME !!');
  end;
  Finish;
end;

procedure TForm1.LearnByMistakes;
var
  x, PageNum, LineNum, nTemp, nTakes: integer;
begin
  if RemainPebs <= 0 then
  begin
    //Openent drew the last pebble(s) ! Computer won !!
    //DispPebbles(0);
    Messaging(False, False);
    exit;
  end;
  nTemp := random(6) + 1;
  PageNum := RemainPebs mod 4;
  if PageNum = 0 then
    PageNum := 4;
  for x := 1 to 3 do
  begin
    LineNum := aPermutations[nTemp, x];
    if (aPages[PageNum, LineNum] > 0) then
      break;
  end;
  if x > 3 then {No unmarked instructions remained ! All are redmarked !!}
  begin
    // The effect of this move was unknown previously. But it proved to be fatal this time !
    // RedMark This oldLineNum of this oldPageNum !
    aPages[OldPageNum, OldLineNum] := -99;
    // Lost with Resigning Message !
    ListBox1.Items.add(intTostr(nTurn) + '. I resigned ');
    DispPebbles(RemainPebs);
    Messaging(True, True);
    exit;
  end;
  nTakes := aPages[PageNum, LineNum];
  if nTakes >= RemainPebs then
  begin
    ListBox1.Items.add(intTostr(nTurn) + '. I (Computer): ' + intTostr(RemainPebs));
    //I am the last drawer and I lost !!
    // RedMark This LineNum of this PageNum !
    aPages[PageNum, LineNum] := -99;
    DispPebbles(0);
    Messaging(True, False);
    exit;
  end;
  ListBox1.Items.add(intTostr(nTurn) + '. I (Computer): ' + intTostr(nTakes));
  showmessage('I (Computer) take: ' + IntTostr(nTakes) +
    ' Pebble(s) for this turn !');
  OldPageNum := PageNum;
  oldLineNum := LineNum;
  RemainPebs := RemainPebs - nTakes;
  ManageEnabling(True);
  DispPebbles(RemainPebs);
end;

procedure TForm1.BitBtnResignClick(Sender: TObject);
begin
  inc(PlayedGames);
  inc(ComputerWon);
  inc(nTurn);
  ListBox1.Items.add(intTostr(nTurn) + '. You resigned');
  Finish;
end;

procedure TForm1.LabelbtnClick(Sender: TObject);
begin
  BitBtnResign.SetFocus;
  BitBtnResign.Click;
end;

procedure TForm1.BitBtn1Click(Sender: TObject);
var
  nTaken: Integer;
begin
  with Sender as TBitBtn do
    nTaken := Tag;
  ManageEnabling(False);
  if (RemainPebs = totPebs) then
  begin
    ComboBox1.Enabled := False;
    ListBox1.Clear;
    nTurn := 1;
  end
  else
    inc(nTurn);
  ListBox1.Items.add(intTostr(nTurn) + '. You: ' + intTostr(nTaken));
  RemainPebs := RemainPebs - nTaken;
  DispPebbles(RemainPebs);
  LearnByMistakes;
end;

end.

A zipped file game.zip contains all stuffs (forms, units and project file) of the running project of this game. This project was compiled and run with Delphi - 3.

At last for the interested friends:
I have programmed a game of strategic thinking using the principles of Artificial Intelligence.  The game is somehow like Chess.
The game was programmed using PowerBasic and Assembly Language. This game has won the First Prize in The First All Nepal Software Competition, SOFTWARE MEET 2000. The game can be downloaded at: http//:www.viewnepal.com/gamezip.exe (a self extracting pkzip file). I will be glad to provide a copy through e-mail if the download does not work.

For users, who are interessted in Artificical intelligence: You can find a Delphi component for ArtificialNeuronalNetworks under http://www.logiware.de/ann

Component Download: game.zip

Nincsenek megjegyzések:

Megjegyzés küldése