Kezdőlap / Kidolgozott tételek / DEIK Mérnökinformatikus BSC 2017 / 5. tétel

5. Tétel — Keresések ellenséges környezetben és elektronikai alapáramkörök

Frissítve: 2026-09-09

Ez a tétel két nagyobb témakört fed le: a mesterséges intelligencia ellenséges környezetben zajló kereséseit (Minimax, alfa-béta vágás), valamint az elektronika analóg és digitális alapáramköreit (MOS tranzisztor, CMOS logika, műveleti erősítő).

Témák

I. Témakör: Mesterséges intelligencia – Keresések ellenséges környezetben

• Ismertesse az ellenséges környezetben zajló kereséseket, és nyerő stratégia létezésének feltételeit!

II. Témakör: Elektronika és analóg/digitális áramkörök

• MOS tranzisztor felépítése és működése.
• Kapcsoló üzemmód.
• CMOS inverter, alapkapuk.
• Az erősítés fogalma.
• A műveleti erősítő.
• Negatív visszacsatolás.
• Alapkapcsolások.

I. Témakör: Mesterséges intelligencia – Keresések ellenséges környezetben

1. Az ellenséges környezet és a kétszemélyes játékok modellje

A mesterséges intelligencia egyik klasszikus és rendkívül fontos területe a döntéshozatal olyan környezetekben, ahol több, egymással versengő ágens (játékos) cselekszik. Ezeket nevezzük ellenséges (adversarial) környezeteknek. A célunk egy olyan optimális stratégia kidolgozása, amely maximalizálja a saját nyereségünket, miközben figyelembe vesszük, hogy az ellenfelünk is a saját nyereségének maximalizálására, és ezzel a miénk minimalizálására törekszik.

• Kétszemélyes: Két játékos (ágens) vesz részt a játékban.
• Zéró összegű: A rendszerben nincs külső nyereség vagy veszteség; az egyik játékos nyeresége pontosan megegyezik a másik veszteségével (szigorúan kompetitív környezet).
• Tökéletes információs: Mindkét játékos teljes és pontos rálátással bír a játéktábla aktuális állására; nincsenek rejtett változók vagy lapok (ellentétes a kártyajátékokkal).

A modell főbb jellemzői

• Többügynökös (Multi-agent) környezet: A szereplők (hagyományosan MAX és MIN néven emlegetve) egymás ellen dolgoznak.
• Konfliktus: A célok kölcsönösen kizárják egymást; az egyik optimalizálási iránya ellentétes a másikkal.
• Játékfa (Game tree): A lehetséges lépések és állapotok fahatású ábrázolása, ahol a csomópontok a játékállapotokat, az élek pedig a megtehető lépéseket jelölik.

2. Nyerő stratégia létezésének feltételei

Ahhoz, hogy egy ellenséges környezetben (játékban) elméletben garantáltan létezzen nyerő stratégia (vagy döntetlen kényszerítés), a rendszernek meg kell felelnie bizonyos alapvető feltételeknek. Ezeket a játékelmélet és a mesterséges intelligencia klasszikus elvei határozzák meg:

• Tökéletes információ: A játék minden pillanatában mindkét játékos pontosan és teljes körűen ismeri a teljes játékállapotot, a szabályokat és a lehetséges jövőbeli lépéseket. Nincsenek rejtett információk vagy rejtett lapok (mint például a kártyajátékokban).
• Determinista környezet: A játékmenetben nincsenek véletlen elemek (például kockadobás, kártyakeverés vagy szerencsefaktor). Minden egyes megvalósított lépés szigorúan és egyértelműen határozza meg a következő állapotot.
• Zéró összegű játék: A résztvevők nyeresége és vesztesége szigorúan kiegyenlíti egymást. Amit az egyik játékos nyer, azt a másik pontosan annyival elveszíti; a rendszerben a hasznosságok összege fix.
• Véges állapot- vagy lépéstér: A lehetséges játékállapotok száma véges, vagy a játék definíció szerint egy véges lépésszám után garantáltan véget ér (győzelemmel, vereséggel vagy döntetlennel).

3. A Minimax algoritmus

A Minimax algoritmus egy rekurzív, mélységi bejáráson alapuló keresőeljárás, amely az optimális lépést határozza meg a fent leírt játéktípusokban. Az algoritmus alapelve, hogy a legrosszabb esetet optimalizálja: azt a lépést választja, amely a lehető legjobb kimenetelt garantálja számunkra egy tökéletesen racionális, hibátlanul játszó ellenféllel szemben.

Az algoritmus a játékfa leveleiből indul ki, és rekurzívan halad visszafelé a gyökér felé. A két játékost MAX-nak (aki maximalizálni akarja a hasznosságot) és MIN-nek (aki minimalizálni akarja azt) nevezzük.

• A MAX szinten lévő csomópontok értékét a gyermekeik értékének maximuma adja.
• A MIN szinten lévő csomópontok értékét a gyermekeik értékének minimuma adja.

A gyökércsomópont számított értéke lesz a játék Minimax-értéke. Ha ez az érték győzelmet jelent, akkor a MAX játékosnak létezik nyerő stratégiája, és az algoritmus által javasolt első lépés ennek a stratégiának a kezdete.

Jellemzői:

• Teljesség: Véges játékfa esetén garantáltan megtalálja a megoldást.
• Optimalitás: Optimális lépést ad egy optimálisan játszó ellenfél ellen.
• Időkomplexitás: O(b^m), ahol 'b' az elágazási tényező (egy csomópontból elérhető átlagos lépésszám), 'm' pedig a maximális keresési mélység. Ez a legfőbb hátránya, mivel a komplexitás exponenciális.
• Tárkomplexitás: O(b*m), mivel mélységi bejárást végez, és egyszerre csak egy utat tart a memóriában.

4. Az alfa-béta vágás (Alpha-Beta Pruning)

A tiszta Minimax algoritmus fő hátránya, hogy a keresési fa méretének növekedésével a számítási komplexitás is növekszik, ami a gyakorlatban gyorsan kezelhetetlenné válik.

Az alfa-béta vágás egy olyan optimalizációs eljárás, amely a keresés során semmilyen információt nem vesz el a Minimax algoritmus optimalitásából vagy teljességéből, mégis drasztikusan csökkenti a megvizsgált csomópontok számát. Az eljárás két értéket tart nyilván a keresés során:

• alfa: A MAX játékos által eddig garantáltan elérhető legmagasabb érték az aktuális útvonalon.
• béta: A MIN játékos által eddig garantáltan elérhető legalacsonyabb érték az aktuális útvonalon.

Ha egy részfa vizsgálata során kiderül, hogy az adott ág értéke rosszabb, mint az eddig bejárt alternatívák, akkor a részfa további bejárása felesleges, így azt levágjuk (pruning).

II. Témakör: Elektronika és analóg/digitális áramkörök

1. MOS tranzisztor felépítése és működése

A MOSFET (Metal-Oxide-Semiconductor Field-Effect Transistor, azaz fém-oxid-félvezető térvezérlésű tranzisztor) a digitális és analóg áramkörök legelterjedtebb aktív eszköze. Két fő típusa van: az nMOS (n-csatornás) és a pMOS (p-csatornás).

Fő szerkezeti elemei:

• Gate (G – Kapu): Fém vagy poliszilícium vezérlőelektróda, amelyet egy vékony szigetelőréteg (oxidréteg) választ el a félvezető aljzattól.
• Source (S – Forrás) és Drain (D – Nyelő): Erősen dópolt félvezető tartományok az aljzatban.
• Substrate / Bulk (B – Aljzat): A hordozó kristálytest.

Működési elv:

• Feszültségvezérelt működés: A tranzisztor állapotát nem vezérlő áram, hanem a kapu és a forrás közé kapcsolt feszültség által létrehozott elektromos mező szabályozza.
• Lezárt állapot: Amíg a kapufeszültség alacsonyabb egy meghatározott küszöbfeszültségnél, a csatorna nem alakul ki, így a forrás és a nyelő között megszakad az áramút.
• Csatorna kialakulása: Ha a kapufeszültség meghaladja a küszöbfeszültséget, az elektromos mező a felületre vonzza a töltéshordozókat, és létrehoz egy ideiglenes, vezető csatornát a szigetelőréteg alatt.
• Áramfolyás: A létrejött vezető csatornán keresztül – a nyelőre kapcsolt feszültség hatására – megindul az áram a forrás és a nyelő között.
• Galvanikus elszigeteltség: Mivel a kapu elektróda egy vékony szigetelőréteggel teljesen el van választva a félvezető testtől, a vezérlő oldalra nem folyik vezérlő áram, ami rendkívül alacsony energiafogyasztást eredményez.

2. Kapcsoló üzemmód és a CMOS inverter

A CMOS inverter kapcsolási sémája és működése:

A CMOS inverter és a logikai alapkapuk a modern digitális áramkörök (processzorok, memóriák) legkisebb építőkövei. A CMOS (Complementary Metal-Oxide-Semiconductor) technológia lényege, hogy a kapcsolásokat NMOS és PMOS tranzisztorok párosításával valósítják meg.

Felépítése:

• PMOS tranzisztor: A felső ágon helyezkedik el (a tápfeszültség felé).
• NMOS tranzisztor: Az alsó ágon helyezkedik el (a földelés, GND felé).
• A két tranzisztor kapuját összevezetik, ez a bemenet. A nyelőiket szintén összekötik, ez adja a kimenetet.

Működése:

• Ha a bemenet magas: Az NMOS tranzisztor kinyit (vezet), míg a PMOS tranzisztor lezár. A kimenet közvetlenül a földre kapcsolódik, így a kimeneti feszültség alacsony lesz.
• Ha a bemenet alacsony: A PMOS tranzisztor kinyit, az NMOS pedig lezár. A kimenet a tápfeszültségre kapcsolódik, így a kimeneti feszültség magas lesz.

Fő előny: Mivel a két tranzisztor közül stabil állapotban mindig az egyik le van zárva, a CMOS inverter statikus állapotban gyakorlatilag semmi energiát nem fogyaszt (csak az átkapcsolás pillanatában folyik áram).

3. CMOS alapkapuk (NAND, NOR)

Az inverter logikáját kiterjesztve komplexebb logikai kapuk is felépíthetők tranzisztor szinten:

• NAND kapu: Az nMOS tranzisztorok sorba, míg a pMOS tranzisztorok párhuzamosan kapcsolódnak. A kimenet csak akkor lesz alacsony, ha minden bemenet magas.
• NOR kapu: A pMOS tranzisztorok kapcsolódnak sorba, az nMOS tranzisztorok pedig párhuzamosan. A kimenet csak akkor lesz magas (1), ha minden bemenet alacsony (0).
• Összetettebb kapuk (AND, OR): Az AND és OR kapukat úgy kapják meg a gyakorlatban, hogy a fent említett NAND, illetve NOR kapuk kimenetére rákötnek egy hagyományos CMOS invertert, amely ismét megfordítja a jelet a helyes logikai eredmény eléréséhez.

4. Az erősítés fogalma és a műveleti erősítő

Az erősítés egy áramkör azon képessége, hogy a bemeneti jel (feszültség vagy áram) amplitúdóját megnövelve adja át a kimenetnek.

A műveleti erősítő (Operational Amplifier - OpAmp) egy nagyon nagy erősítésű, direkt csatolású differenciális erősítő, amely analóg számítások, jelformálások és erősítési feladatok alapköve.

Az ideális műveleti erősítő elméleti jellemzői:

• Végtelen nyílthurkú feszültségerősítés: A kimeneti feszültség visszacsatolás nélkül végtelenül nagy mértékben reagál a két bemenet közötti legkisebb feszültségkülönbségre is.
• Végtelen bemeneti impedancia: A bemenetek egyáltalán nem vesznek fel áramot a külső áramkörtől, így teljesen tehermentesítik a jelforrást.
• Nulla kimeneti impedancia: A kimenet tökéletes feszültségforrásként viselkedik, amelynek feszültségesését a rákapcsolt terhelés nem befolyásolja.
• Végtelen sávszélesség és nulla eltolási feszültség: Az erősítő minden frekvenciájú jelet késleltetés nélkül, bemeneti jel hiányában pedig pontosan nulla kimeneti feszültséggel kezel.

5. Negatív visszacsatolás és alapkapcsolások

Negatív visszacsatolás: Negatív visszacsatolásról akkor beszélünk, amikor a kimeneti jel egy részét ellentétes fázisban (vagyis a negatív / invertáló bemenetre visszavezetve) visszacsatoljuk a bemenetre.

Főbb előnyei:

• Stabilitás: Függetlenítést biztosít az erősítő elemek gyártási szórásától és a hőmérséklet-változásoktól.
• Torzítás csökkentése: Jelentősen javítja a kimeneti jel linearitását.
• Sávszélesség növelése: A visszacsatolás révén az áramkör átviteli sávszélessége megnő.
• Impedanciaviszonyok javítása: Növelheti a bemeneti impedanciát és csökkentheti a kimeneti impedanciát (közelítve az ideális állapothoz).

Főbb alapkapcsolások:

• Invertáló erősítő: A bemeneti jel ellenálláson keresztül csatlakozik az invertáló negatív bemenetre, a nem-invertáló pozitív bemenet pedig le van földelve. A kimenetről egy visszacsatoló ellenállás kapcsolódik vissza az invertáló bemenetre.
• Nem-invertáló erősítő: A bemeneti jel közvetlenül a nem-invertáló pozitív bemenetre kapcsolódik. Az invertáló negatív bemenet egy ellenálláson keresztül a földre, valamint egy visszacsatoló ellenálláson keresztül a kimenetre kötődik.